프로그래머스 - 좌석 구매

1. 문제

출처 : 프로그래머스

2. 소스코드 (Python3)

def solution(seat):     answer = len(seat)     Set = {}     for s in seat:         index = 100000*s[0] + s[1]         if index in Set:             answer -= 1         else:             Set.add(index)       return answer

3. 고찰

1) 알고리즘

모든 seat에 대해서 set에 넣고, 이미 해당 좌석이 set에 들어있다면 정답에서 한 명씩 빼는 알고리즘.

이때 좌석은 100000 * 100000 크기로 2차원이므로 좌석의 좌표는 x좌표 * 100000 + y좌표로 계산하였다.

 

2) 시간복잡도

모든 seat의 원소에 대해서 for loop -> O(N)

    Set에 해당 좌표(index)가 있는지 확인 -> O(N)

    Set에 새로운 원소 삽입 -> O(1)

따라서 위 코드의 시간 복잡도는 O(N^2)이다.