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

✔ 문제

---

✔ 풀이

🙄 틀린 코드 (시간 초과)

n = int(input())
nums = list(map(int, input().split()))
res = [0] * n

for i in range(len(nums)):
    c = 0
    for j in range(len(nums)):
        if nums[i] > nums[j]:
            c += 1
    res[i] = c

print(res)

이중 for문 돌면서 해당 nums[i]보다 작은 수를 count 해서 res 배열에 저장했는데 입력받을 수 있는 수의 범위가 굉장히 크다보니 이중 for문은 시간 초과가 되는 것 같다.

 

😎 정답 코드

import sys
input = sys.stdin.readline

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

nums2 = list(set(nums))
nums2.sort()
numdic = {}

for i in range(len(nums2)):
    numdic[nums2[i]] = i

for i in nums:
    print(numdic[i], end=' ')

---

✔ 설명

일단 빠른 입력 처리를 위해 sys를 사용했다.

내가 풀었던 로직과 유사한데 조금 더 생각하면 답이 나온다.

 

1. 먼저 num2에 set, list를 사용해 nums 리스트의 중복 수를 제거한다.

2. nums2를 오름차순 정렬을 한 후 numdic이라는 dict를 정의한다.

    ㄴ ex) [2, 4, -10, 4, -9] 라면 nums2 = [-10, -9, 2, 4] 가 될 것이다.

3. { numdic[값] : 값의 index } 형태가 될 수 있도록 for문을 돌려 저장한다.

   ㄴ ex) numdic[-10] : 0, numdic[2]: 2 형식으로 저장된다. 

4. nums의 i 값을 numdic의 key로 넣어 value를 출력하면 된다.

    ㄴ 이 단계를 통해 값을 출력하기 때문에 nums, nums2가 각각 필요하다.