[백준-Python] 콘서트 : 16466번

🥉 Bronze1

https://www.acmicpc.net/problem/16466

 

✅ 정답풀이

import sys

input = sys.stdin.readline

N = int(input())
first_tickets = sorted(map(int, input().split()))  
isEnd=True

for i in range(N): #0 1 2 3 4
    if i+1!=first_tickets[i]:
        print(i+1)
        isEnd=False
        break

#1차에서 다팔린 경우
if isEnd:
    print(N+1)

 

메모리	실행시간
155528	340

 

처음에 list를 순회하면서 in연산자로 체크를 해보는 방식으로 풀었는데, 시간초과가 발생했다..

그래서 in 연산자가 모든 요소를 순차적으로 탐색하기 때문에 시간초과가 발생하는것 같아 단순한 정수비교로 바꿔줬더니 해결되었다.

 

 

set

팀원들 코드를 보니, 똑같은 로직으로 set으로 풀이한 경우가 있었다. 

 

오늘 문제들을 풀면서 알게된 사실인데,

순회를 하면서 search를 해야할때 list보다 set이 더 빠르다.

이 문제 또한, list로 풀이를 하면 시간초과가 발생한다고 한다. 

 

set 자료구조는 해시 테이블의 구조로 구현되기 때문에, 해시 함수로 해시값으로 변환되기 때문에  탐색, 삽입, 삭제에서 O(1)의 시간복잡도를 가진다고한다.

 

set으로 풀어보면 430ms의 실행시간인것을 확인할 수 있었다.