백준 10815번 : 숫자 카드 풀이 (파이썬 python)

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1 

1 0 0 1 1 0 0 1

 

 

---

풀이

 

<나의 풀이>

n = int(input())
arr1 = list(map(int,input().split()))

m = int(input())
arr2 = list(map(int,input().split()))

for i in arr2:
    if i in arr1:
        print(1, end=' ')
    else:
        print(0, end=' ')

 

이렇게 코드를 작성했더니 시간초과가 발생했다.

 

 

<해결 방법>

import sys
input = sys.stdin.read

# 입력 줄 단위로 나누기
data = input().splitlines()

# data[0]=> 상근이가 가진 카드 개수 N
N = int(data[0])

# data[1]=> 상근이가 가진 카드 번호들
# 공백으로 구분된 숫자를 정수로 변환해 집합으로 만든다.
card = set(map(int, data[1].split()))

# data[2]=> 확인할 카드 개수 M
M = int(data[2])

# data[3]=> 확인할 카드 번호들
# 공백으로 구분된 숫자를 정수로 변환해 리스트로 만든다.
query = list(map(int,input().split()))

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

for q in query:
  if q in card:
    results.append('1')
  else:
    results.append('0')

print(' '.join(results))

 

GPT에게 물어봤을 때 알려준 코드이다.

왜 코드에서 집합(set)과 리스트(list)를 혼합해서 사용했는지 물어봤더니,

 

코드에서 집합과 리스트를 혼합하여 사용하는 이유

1. 상근이의 카드 처리:
   • 집합을 사용하는 이유: 상근이의 카드 번호를 집합으로 변환하는 것은 카드가 존재하는지 여부를 매우 빠르게 확인할 수 있게 하기 위함입니다. 집합은 평균적으로 O(1) 시간 복잡도로 원소의 존재 여부를 확인할 수 있어, 많은 카드와 쿼리를 처리할 때 성능이 뛰어납니다.
   • 예를 들어, 상근이가 가진 카드가 500,000개일 때, 집합을 사용하면 각 카드의 존재 여부를 빠르게 확인할 수 있습니다.
2. 쿼리 카드 처리:
   • 리스트를 사용하는 이유: 쿼리 카드 번호는 순서가 필요하지 않으며, 각 쿼리 카드가 상근이의 카드 집합에 있는지 확인해야 하기 때문입니다. 이 단계에서는 쿼리 리스트를 순회하면서 집합에 해당 카드가 있는지 확인하기만 하면 됩니다.

둘 다 집합으로 만들거나 둘 다 리스트로 만들면?

• 둘 다 집합으로 만들 경우:
  • 쿼리 카드 목록을 집합으로 변환하면, 카드가 존재하는지 확인하는 부분은 매우 빠릅니다 (O(1) 시간 복잡도).
  • 그러나, 집합은 순서가 없으므로 결과를 출력할 때 순서가 보장되지 않습니다. 또한, 메모리 사용량이 약간 증가할 수 있습니다.
• 둘 다 리스트로 만들 경우:
  • 카드의 존재 여부를 확인하기 위해서는 리스트를 순회해야 하므로, 평균적으로 O(n) 시간 복잡도가 걸립니다. 쿼리가 많을 경우, 이 방법은 비효율적입니다.
  • 리스트는 순서가 유지되므로, 결과를 출력할 때 원래 순서를 유지할 수 있습니다.

결론

• 상근이의 카드는 집합으로 만들어 빠르게 검색할 수 있도록 하고,
• 쿼리 카드는 리스트로 만들어 순서대로 처리하여 검색 결과를 출력할 때 순서를 유지하도록 합니다.

 

즉, 리스트랑 집합을 조합해서 코드를 작성한 이유는 메모리 사용량, 검색 효율성에 균형을 맞추기 위함이었다.

 

 

또한, results.append('1')와 같이 문자열로 저장한 이유에 대해서도 궁금했다.

출력을 문자가 아닌 숫자로 해도 되는 것이 아닌가?

 

숫자 1, 0을 사용하는 방법도 가능하지만, print(' '.join(results))를 통해

결과를 공백으로 구분된 문자열로 쉽게 출력하기 위함이었다.

join()으로 연결하면 공백으로 구분된 문자열이 만들어지기 때문이다.

 

물론, results 리스트에 숫자형 1과 0을 저장하고 싶다면 results.append(1)과 같이 할 수 있다.

하지만, 이렇게 저장된 숫자 리스트를 출력하기 위해서는

리스트를 문자열로 변환해야하는 과정이 추가로 필요하다.

 

문자열로 저장하는 것이 간단하고, 코드가 간결해지기 때문에 대부분의 경우에 추천된다고 한다! 

 

1) 문자열로 저장하는 경우

# 결과를 문자열로 저장
results = []
results.append('1')
results.append('0')

# 결과를 공백으로 구분된 문자열로 변환하여 출력
print(' '.join(results))

 

2) 숫자로 저장하는 경우

# 결과를 숫자로 저장
results = []
results.append(1)
results.append(0)

# 숫자 리스트를 문자열로 변환
results_str = map(str, results)  # 숫자 리스트를 문자열로 변환
print(' '.join(results_str))