[백준] 18870 좌표 압축

avatar
2025.03.07
·
2 min read

3739

🔗 문제 링크

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

💻 코드

제출 코드

import sys
input = sys.stdin.readline 

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

for i in range(n):
    coordinate.append([i,nums[i]]) # 1- 좌표와 인덱스 추가

coordinate.sort(key=lambda x:x[1]) # 2- 뒤 숫자(좌표) 기준 정렬


# 3- 좌표값을 0부터 반복문으로 변경
result = [[coordinate[0][0], 0]]
for i in range(1,n):
    if coordinate[i-1][1] == coordinate[i][1]:
        result.append([coordinate[i][0],result[-1][1]])
    else:
        result.append([coordinate[i][0],result[-1][1]+1])

# 4 - 인덱스 기준 다시 정렬
result.sort(key=lambda x:x[0])

for _,i in result:
    print(i, end=' ')
    

참고 코드

import sys
input = sys.stdin.readline 

n = int(input())
nums = list(map(int,input().split()))
print(nums)
arr = sorted(set(nums))
print(arr)

dic = {arr[i]:i for i in range(len(arr))}
print(dic)

for i in nums:
    print(dic[i], end=" ")

🤷‍♂ 풀이

  • 너무 코드를 더럽게 짜서 다른 사람의 풀이를 보고 얻어가야겠다.

  • arr = sorted(set(num))

    • 입력받은 좌표는 중복을 제거하기 위해 set형으로 바꾸자.

  • dic = {arr[i]:i for i in range(len(arr))}

    • dictionary를 사용해 시간복잡도를 줄인다.

    • 작은값부터 시작해서 0부터 인덱스를 부여한다.

    • arr[i] key에 i란 인덱스를 넣는 것

  • 딕셔너리에서 키에 input에 해당하는 값을 출력한다.

  • for i in nums:

    • 기존 좌표들이 들어있는 nums에서 해당 값 i를 key로 가지는 dic[i]의 value를 출력하면 된다.

교훈

  • 문제를 간결하게 생각하는 흐름을 익히자.







- 컬렉션 아티클