[Python] BOJ 10815 : 숫자 카드 [9.26 이후 다시 볼 게시물]

https://www.acmicpc.net/problem/10815

요구사항

1. 보여줄 숫자 카드가 상근이가 가지고 있는 지 없는 지 확인하는 문제이다.

설게

1. 비교할 리스트와 비교 당할 리스트를 만든다.
2. 비교 결과를 저장할 리스트를 만든 후 결과값을 담아 출력한다.

틀린 답안 예시

import sys
input = lambda: sys.stdin.readline().strip()

# 첫 번째 배열 입력 받기
N = int(input())
arr1 = list(map(int, input().split()))  # 1차원 리스트로 입력받음

# 두 번째 배열 입력 받기
M = int(input())
arr2 = list(map(int, input().split()))  # 1차원 리스트로 입력받음

# 결과를 저장할 리스트
result = []

# arr2의 각 원소가 arr1에 있는지 확인
for i in arr2:
    if i in arr1:
        result.append(1)
    else:
        result.append(0)

# 결과 출력
print(*result)

• 로직상으로 문제 없지만, 시간 초과 오류가 난다. 
• 그 이유는 아마 in 연산을 반복적으로 하기 때문이다. in 연산ㅈ는 리스트에서 값을 찾을 때 O(N)의 시간 복잡도를 갖는다. 따라서 arr2 의 각 요소에 대해 arr1에서 검색하는 데 이 경우 O(N x M) 의 시간 복잡도가 발생한다. 
• arr1 이 크게 되면 오래 걸릴 수 밖에 없다. 

정답 답안 예시 코드

import sys
input = lambda: sys.stdin.readline().strip()

# 첫 번째 배열 입력 받기
N = int(input())
arr1 = set(map(int, input().split()))  # 1차원 리스트로 입력받음

# 두 번째 배열 입력 받기
M = int(input())
arr2 = list(map(int, input().split()))  # 1차원 리스트로 입력받음

# 결과를 저장할 리스트
result = []

# arr2의 각 원소가 arr1에 있는지 확인
for i in arr2:
    if i in arr1:
        result.append(1)
    else:
        result.append(0)

# 결과 출력
print(*result)

• 탐색 시간을 줄이기 위해 자료구조를 개선해야 된다.
• 비교할 리스트를 set(집합) 으로 바꾸어 해결했다.
  • set은 in 연산이 평균적으로 O(1) 에 수행되기 때문에 시간 초과를 막을 수 있다. 

+ 2024.09.26 복습겸 달라진 코드 부분 설명

N = int(input())
arr1 = set(map(int, input().split()))
M = int(input())
arr2 = list(map(int, input().split()))

result = [0 for _ in range(M)]

for i in range(M):
    if arr2[i] in arr1:
        result[i] = 1
    else:
        result[i] = 0

print(*result)

• result 리스트를 초기화 해준건 똑같지만, 다르게 초기화 하였다. 그 이유는 BFS, DFS 를 하면서 방문 여부를 체크 하는 리스트를 많이 하다 보니깐 그렇게 된 거 같다. 추가로 얼마나 차이나는 지 알아보자.