백준 알고리즘: 10815번 숫자 카드 (Python)

문제 정보

---

 

10815번: 숫자 카드

 

 

핵심

---

이제 가장먼저, 입력 허용 범위와 개수부터 파악을 하고 들어가는 습관을 가지게 되었다!

N의 개수가 많지 않으므로 Sorting Algorithm에 대해서 큰 생각을 하지 않아도 되고(최악의 경우가 아니라면)
값의 숫자의 범위가 넓으므로 배열을 통한 비교도 효율적이지 않을 것이라 생각하였다

따라서 그냥 먼저 정석적으로 이분 탐색을 사용하여 풀이해 보았다

 

풀이

---

 

import sys
from bisect import bisect_left, bisect_right

N = sys.stdin.readline()
Ns = list(map(int, sys.stdin.readline().split()))
# system
M = sys.stdin.readline()
Ms = list(map(int, sys.stdin.readline().split()))
# user input
Ns.sort()

def binary(array, target):
    return bisect_right(array, target) - bisect_left(array, target)
    
for i in Ms:
    if binary(Ns, i) > 0:
        print(1, end=' ')
    else:
        print(0, end=' ')

문제에서 상근이가 가지고 있는 숫자 카드 배열인 N을 정렬하고, bisect 라이브러리를 통하여 이분탐색을 실시하였다

N과 M은 사실상 버리는 값이고, readline()으로 한 줄을 읽어와서 split()을 통하여 스페이스 간격으로 split 하였다

 

 

고찰

---

변수 명을 사용하지 않는 경우

# 기존
N = sys.stdin.readline()
M = sys.stdin.readline()

# 이후
_ = sys.stdin.readline()
_ = sys.stdin.readline()

변수명을 사용하지 않는 경우 _(더미 변수)를 사용하여 해당 변수 값이 사용되지 않음을 명시할 수 있다

 

맞았지만 아쉬운 시간

뭔가 이렇게 마무리하기에는 얻어가는 것이 별로 없기에, 고수들의 풀이를 보며 나를 스펙업 해보도록 하였다

시간이 약 1/4 배 차이가 난다

_ = input()
N_set = set(input().split())
_ = input()
print(' '.join(['1' if i in N_set else '0' for i in input().split()]))
# 출처 https://www.acmicpc.net/source/54267395

상근이가 가지고 있는 숫자 카드들(Ns)은 중복인 경우가 없고, 따라서 개수를 셀 경우도 없기 때문에 대부분의 상위 시간을 차지하는 분들은 set을 사용하여 풀이하였다

set 자료형의 경우 내부적으로 해시 테이블을 사용하여 요소를 저장하므로, 해당 요소가 상근이가 가지고 있는 숫자 카드인지 판별하는 시간복잡도는 평균적으로 O(1)에 수렴한다 (list의 경우 O(n))

 

따라서 상근이가 가지고 있는 숫자 카드들을 Set 자료형에 집어넣고 in 키워드를 통하여 해당 요소가 집합에 포함되어 있는지를 판별하면 되는 알고보면 쉬운 내용이었던 것이다

' '.join의 경우 '구분자'.join([리스트]) 로 사용되는데, 리스트에 있는 요소 사이에 구분자를 넣어 하나의 문자열로 합쳐주는 함수이다

위 코드에서 print(' '.join(['1' if i in N_set else '0' for i in input().split()])) 는 N_set에 각 요소가 들어있으면 1 없다면 0을 구분자인 공백(' ') 을 통하여 구분하고, 하나의 문자열로 합쳐서 최종적으로 print 해주는 것이다

 

Set 자료형에 대한 정리

https://dduneon.tistory.com/39

를 참고하면 될 것 같다