(파이썬) 백준 알고리즘 - 18870번

좌표압축

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

18870번: 좌표 압축

 

좌표 압축이라는 것이 자신의 좌표값보다 큰 서로 다른 좌표의 개수라고 한다.

예제 입력 2를 확인하면 알 수 있듯이, 999의 경우 1000이 3개가 있지만 출력에서는 1로 표시되어야 한다.

그래서 처음엔 입력받은 자료들에서 중복된 값을 제거한 후 정렬해서

입력받은 수 보다 큰 숫자가 몇 개 있는지 세는 방법으로 구했다.

(시간초과한 코드)

N = int(input())
coords = list(map(int, input().split()))
set_coords = set(coords)
for coord in coords:
    count = 0
    for set in set_coords:
        if coord > set:
            count += 1
    print(count, end=' ')

그런데 시간초과가 나와서 index로 순서를 확인하는 쪽으로 수정했는데 그것도 시간초과였다.

(시간초과한 코드)

N = int(input())
coords = list(map(int, input().split()))
set_coords = list(set(coords))
set_coords.sort()
for coord in coords:
    print(set_coords.index(coord), end=' ')

 

방법을 찾지 못해서 인터넷 검색으로 해결했다.

(성공)

N = int(input())
coords = list(map(int, input().split()))
sort_coords = sorted(list(set(coords)))
dic = {sort_coords[i] : i for i in range(len(sort_coords))}
for i in coords:
    print(dic[i], end=' ')

위의 두 경우는, coords의 개수만큼 set_coords에서 for문을 실행하거나, index()를 실행해야 했다.

아래의 통과한 경우는, dict형에 { '숫자' : index } 형태로 저장해 dic[숫자]를 통해 index를 출력하는 방법이다.

실제 저장된 형태를 보면 다음과 같다.

sort_coords.index('숫자')에서 index값을 찾는 것과, dic에서 값을 찾는 것이 크게 다르지 않다고 느껴졌는데 시간복잡도를 찾아보니 달랐다.

list.index()의 경우, 시간복잡도가 O(N)이다.

dictionary의 경우 탐색 연산에 O(1)의 시간복잡도를 가지기 때문에 많은 수를 탐색할 경우 dict로 탐색하는 것이 훨씬 빠르다.

 

list도 list[x]와 같이 인덱스에 따른 값을 찾는데는 시간이 많이 걸리지 않지만 위의 문제에서는 거꾸로 값의 인덱스를 찾는 거라서 시간이 오래걸렸다.

 

 

참고한 페이지

https://gudwns1243.tistory.com/52

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

 

https://hyun-am-coding.tistory.com/entry/Python-list-%EC%97%B0%EC%82%B0%EC%97%90-%EB%94%B0%EB%A5%B8-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

Python list 연산에 따른 시간 복잡도

 

https://chancoding.tistory.com/43

[Python] 파이썬 자료형 및 연산자의 시간 복잡도(Big-O) 총 정리