[백준 파이썬] # 18870 좌표 압축

Silver II

# 18870 좌표 압축

링크 : https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

풀이

# 해시 사용 : 정답__O(1)
N = int(input())
X = list(map(int, input().split()))
S = list(sorted(set(X)))

dic = {}

for i in range(len(S)):
    dic[S[i]] = i

for i in X:
    print(dic[i], end=' ')

# 이진 탐색 사용 : 오답__시간초과: O(n)
N = int(input())
X = list(map(int, input().split()))
S = list(sorted(set(X)))

def bs(arr, target):
    start = 0
    end = len(arr)-1

    while start<= end:
        mid = (start+end)//2

        if arr[mid] == target:
            return arr.index(target)
        if arr[mid] < target:
            start = mid + 1
        if arr[mid] > target:
            end = mid - 1

for i in X:
    print(bs(S, i), end = ' ')

 

후기

• 일반적인 풀이를 시도했을 때 시간 초과 문제가 발생했었다.
  
  
• 탐색과정이 문제라고 생각해서 이진탐색을 이용해봤지만 여전히 시간초과가 발생했다.
  
  
• 문제 질문코너를 통해 list.index('a')로 인해 문제가 발생한다는 점을 알 수 있었다.
  list.index('a')의 경우 O(n)의 시간복잡도를 갖는다고 한다.
  
  
• O(n)보다 시간 복잡도를 줄일 수 있는 해시(딕셔너리)를 이용해서 풀 수 있었다.
  cf. 딕셔너리의 시간복잡도는 O(1)이라 한다.
  
  
• 정렬과 관련된 문항은 딕셔너리를 우선으로 시도해보는것이 좋을듯 하다.