Aidengoldkr – Tech Blog

백준 25192 번 문제는 간단히, input을 확인하여, ENTER 이후 새로 들어온사람은 res 값을 +1 해주면 되는 중복 검사 문제이다. 

아래 코드는 백준 25192번을 풀이하면서 처음 작성한 코드이다. 

n = int(input())
res = 0
user = []
flag = False

for i in range(n):
    inpp = input()
    if inpp == "ENTER":
        flag = True
        user = []
    elif flag and inpp not in user:
        res += 1
        user.append(inpp)
        
print(res)

방문한 사람의 정보를 user 라는 리스트 자료형에 저장후 not in 구문을 이용하여 판별하고 있다. 이 구문을 사용하면 시간복잡도가 O(n²)에 가까워져 시간 초과로 오답처리가 된다. 이에 대한 해결책은 List 대신 Set 자료형을 사용하는 것이다.

n = int(input())
res = 0
user = set()
flag = False

for i in range(n):
    inpp = input()
    if inpp == "ENTER":
        flag = True
        user.clear()
    elif flag and inpp not in user:
        res += 1
        user.add(inpp)
        
print(res)

간단하게 list 자료형을 set으로 변경해주면 정답처리된다. 여기에 쓰인 SET 자료형을 탐구해보자.

 

SET 자료형 - 중복을 허가하지 않는 자료형

부제에도 표현되어있는 듯이 set은 중복을 허가하지 않는 자료형이다. 그로 인해 가장 큰 특징 3가지가 있는데,

• 중복 자동 제거
• in 연산이 평균 O(1)
• 순서 없음

로, 시간복잡도가 압도적으로 낮아 PS에 자주 사용되기도 하는데, set은 내부적으로 해시 테이블을 쓰기 떄문이다. 문자열을 해시값으로 변환 후, 위치 바로 계산하여, 처음부터 끝까지 뒤질 필요 없기 떄문이다. 기본적인 사용법은 다음과 같다,

a = set([1,2,3])
b = set({1,2,3})
c = {1,2,3}
# a = b = c

s.add(4)
s.update([5, 6])
s.remove(4)
s.discard(10)
s.clear()

A = {1, 2, 3}
B = {3, 4, 5}

A | B   # {1,2,3,4,5}
A & B   # {3}
A - B   # {1,2}
A ^ B   # {1,2,4,5}

set은 집합으로도 해석되기에 위 예시의 하단 예시와 같이 연산자로 집합 연산 즉 비교도 가능하다.

 

+실전 PS에서 자주 쓰는 패턴

 

중복 제거

unique =set(arr)

 

빠른 방문 체크

visited =set()if xnotin visited:
    visited.add(x)

 

구간 리셋

s.clear()