백준 25192번 python

입력값에 중복이 나오지 않는다면 count++를 해주고 "ENTER"가 나오면 list를 초기화해주면 된다.

다만 관건은 시간복잡도로, list를 이용하여 중복을 제거, (x not in lst), count, index 등을 이용한다면 시간복잡도는 O(n)이 된다. 거기다가 위에서 for문을 돌려야 하므로 결과적으로는 O(n^)이 된다.

즉, list가 아닌 시간복잡도 측면에서 우월한 ( x not in set의 값이 O(1)인) 집합(set) 또는 (사전)dictionary를 이용해야 한다.

 

---

풀이:

입력의 최대값은 100,000번 이므로 시간을 줄이기 위해 sys.stdin.readline()을 이용했다. 해당 구문을 사용하여 입력을 받으면 개행문자인 "\n"도 들어오므로 rstrip()을 통해 지워주어야 한다.

또한 if String == "ENTER": 구문이 먼저 실행되어야 하므로 not in 구문보다 먼저 적어준다.

import sys
input = sys.stdin.readline
N = int(input().rstrip())
lst = set()
count = 0
for i in range(N):
    String = input().rstrip()
    if String == "ENTER":
        lst = set()
        continue
    if String not in lst:
        lst.add(String)
        count += 1
print(count)

집합 (set)은 중복을 허용하지 않는다는 것을 활용한 구문으로 추가하기 전 set의 length를 저장하고 추가한 이후의 length를 비교하는 방식도 유효하다.

import sys
input = sys.stdin.readline
N = int(input().rstrip())
lst = set()
count = 0
for i in range(N):
    String = input().rstrip()
    if String == "ENTER":
        lst = set()
        continue

    pastLength = len(lst)

    lst.add(String)
    if len(lst) != pastLength:
        count += 1
        
print(count)