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

문제 설명

 

1. 과정

 

처음 문제를 읽고 잘 이해가 되지 않았다. 

문제에서

'Xi를 좌표 압축한 결과값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같다.' 라고 하였는데, 이걸 해석하고 이해하는데 좀 걸렸던 것 같다.

 

결과적으로 리스트 내에서 Xi보다 작은 값의 개수가 좌표 압축의 결과이다.

하지만 '서로 다른 좌표' 라고 했으므로 같은 값이 두 개라면 하나로 세어야 한다.

 

문제의 아이디어가 그렇게 어렵진 않은 것 같아서 그냥 생각없이 코드를 먼저 짜봤다.

 

import sys
input = sys.stdin.readline


n = int(input())

nums = list(map(int, input().split()))
nums_set = set(sorted(nums))

result = []

for num in nums:
    cnt = 0
    for i in nums_set:
        if num > i: cnt += 1
    result.append(cnt)

for i in result:
    print(i,end=" ")

 

당연히 테스트를 해보면 정상적으로 정답이 출력된다. 

하지만 ...

 

 

사실 풀면서 이중 for문을 적으며 이미 직감했다... 시간 초과가 될 것을 ...

시간을 줄이기 위해 이중 for문을 사용하지 않는 방법을 고민해야 했는데, 이 과정이 너무 힘들어 구글링을 해보았다.(디테일하게 코드를 보지 않고 먼저 아이디어만 대략적으로 파악함)

 

구글링을 하다 보니 대부분의 풀이에서 핵심 아이디어는 

중복을 제거하고 정렬해놓은 리스트에서의 인덱스가 해당 좌표의 압축한 결과값이 된다는 것이었다.

난 왜 이 아이디어를 떠올리지 못했을까... 듣고 보면 정말 간단한데 말이다. 

한 번 더 반성하고 다짐하게 되었다. 열심히 해야지.🥲

 

핵심 아이디어를 깨닫고 바로 작성한 코드이다.

 

import sys
input = sys.stdin.readline

n = int(input())

nums = list(map(int, input().split()))
nums_set = sorted(list(set(nums)))

for num in nums:
	print(nums_set.index(num), end = " ")

 

위 코드를 정답으로 제출한 결과이다.

 

결과를 믿을 수 없어 두 번 제출해 봤다.

 

왜일까?

문제는 result 딕셔너리 내부에 있었다.

List.index(i) 의 형태는 O(N)의 시간 복잡도를 가진다. 따라서 리스트에서 직접적으로 값을 통해 인덱스를 불러오는 방법을 사용해선 안된다.

각각의 숫자를 이용해 인덱스를 바로 불러올 수 있는 또 다른 방법은 딕셔너리를 사용하는 것이다.

중복을 제거해 나열한 리스트의 각 요소들이 key, 인덱스 값이 value이다. 

 

딕셔너리에서 key를 통해 value를 가져오는 연산의 시간복잡도는 O(1)이다.

 

 

---

 

2. 풀이

 

import sys
input = sys.stdin.readline


n = int(input())

nums = list(map(int, input().split()))
nums_set = sorted(list(set(nums)))

result = {nums_set[i]: i for i in range(len(nums_set))}


print(*[result[num] for num in nums], sep=' ')

 

마지막 출력 방식이 앞의 코드들과 좀 다른데, 그냥 다양하게 적어보고 싶어서 바꿔보았다.

나중에 한 번에 리스트, 딕셔너리 등에서 사용하는 여러 가지 연산들의 시간 복잡도를 따로 기록해 봐야겠다.