백준 18870번 파이썬

 

18870번: 좌표 압축

문제는 입력받은 수들 중에서 자기 자신보다 작은 수 개수를 입력했던 값에 맞춰서 출력하면 되는 것으로 sort를 하고 난 뒤 그 index값이 곧 좌표 압축된 값임을 알 수 있다. 이를 알아차리고 금방 풀고 제출했지만 시간 초과가 떴다.

처음  풀이 -> 시간초과

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))

sortedArr = list(set(arr))
sortedArr.sort()

for i in range(len(arr)): 
    print(sortedArr.index(arr[i]),end=' ')

두번째 풀이 -> 성공

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))

sortedArr = list(set(arr))
sortedArr.sort()
dic = {sortedArr[i] : i for i in range(len(sortedArr))}

for i in range(len(arr)): 
    print(dic[arr[i]],end=' ')
    #index메소드는 시간복잡도가 N이다. ->  시간초과발생
    #print(sortedArr.index(arr[i]),end=' ')

알아보니 list.index 메소드는 시간복잡도가 O(N) 이었다. 그래서 마지막 for문에서 시간복잡도가 O(N^2)이 될 것이고, 입력개수 최대가 100만 이기 때문에 시간초과가 난 것이다.

1. 중복 제거를 위해 set메소드 사용

2. 중복이 제거된 상태에서 sort사용. (set 형태는 sort 메소드 기능이 없기 때문에 list로 다시 묶어준다.)

3. sort이후, sortedArr의 형태는 인덱스 값이 압축된 좌표 결과 값과 같다 ex) sortedArr[0] == - 10

4. dictionary를 이용해서 {입력값과 : 그 값의 인덱스 값} 을 key값과 value 쌍으로 만든다.

5. dic[key] 를 이용해서 value값을 출력한다.

dic[key] 는 시간 복잡도가 O(1)로, 시간 복잡도를 훨씬 줄일 수 있다.

 

참고자료

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