[BOJ][10815번] - 숫자카드 (python)

안녕하세요 Dibrary 입니다.

이번에는 사전형을 써야만 풀리는 문제를 정리해보고자 합니다.

 

 

먼저 제가 몇 번을 틀린 방식은 아래와 같습니다.

1. 문제에서 주어진 500000이라는 횟수의 비교를 너무 가벼이 생각했음.
2. list가지고 해결이 안 되길래, set을 이용했음. 그럼에도 안 됨.

 

우선 500000이라는 횟수는 생각보다 간단하네~ 라고 착각했던게 큰 오판이었습니다. 차례대로 비교를 해 나가야 하는 것이므로, 500000*500000 의 경우의 수가 있죠... ...

 

그래서 리스트로 접근했던 아래 코드는 시작도 못해보고 시간초과에 걸렸습니다. sys.stdin.readline 을 이용해서 입력을 받았음에도 말이죠.

 

그래서 set으로 담으면 괜찮을까? 싶어서 set으로 시도를 해보았는데, 역시나 시간초과에 걸렸습니다.

 

---

해법은 사전형이었습니다.

우선 500000 갯수만큼 해당되는 숫자를 찾는데 500000번의 시행착오를 겪지 않고, 곧바로 한 번만에 찾으면? 어떨까 하는 생각으로 dictionary를 사용해보자는 접근을 떠올리게 되었습니다.

먼저 담아둔 값은 table이라는 이름의 사전형으로 각각 key로 위치시키고 값은 그냥 1로 통일시켰습니다. 어차피 있느냐 없느냐만 확인하면 되고, 갯수는 중복되지 않는다고 문제에서 언급되었으니까요.

 

그 뒤에 table변수에 찾고자 하는 값이 key에 있는지를 for문으로 확인했습니다.

파이썬에서 dict( ) 자료형에서 key값을 찾는 방법은 O(1)의 시간이 걸립니다.

 

그래서 사전형을 사용함으로써 시간초과의 늪에서 벗어날 수 있었습니다.

혹시라도 리스트로 만들고 순회하면서 찾는데 시간초과가 걸린다면 사전형으로 할 수 있는지를 고려해보시는걸 추천합니다.