백준 18870번 - 좌표 압축

좌표 압축 문제 바로 가기

풀이 날짜: 2026-01-13

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

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

numset = set(data)
a = list(numset)
a.sort()

numdict = {}
for i in range(len(a)):
    numdict[a[i]] = i
for i in data:
    print(numdict[i], end=" ")

문제 접근

이 문제를 처음 봤을 때는 크게 어렵다고 느끼지 않았다. 각 숫자보다 작은 숫자가 몇 개인지를 구하는 문제였기 때문에, 자연스럽게 모든 숫자를 하나씩 비교하면서 세면 되겠다고 생각했다.

그래서 가장 직관적인 방식으로 이중 반복문을 사용해 풀이를 시작했다. 기준이 되는 숫자 하나를 잡고, 나머지 모든 숫자와 비교하면서 작으면 카운트를 증가시키는 방식이었다.

논리적으로는 전혀 문제가 없어 보였고, 실제로 작은 입력에서는 정답도 잘 나왔다.

시간 초과 발생

하지만 제출하자마자 시간 초과가 발생했다. 처음에는 “뭔가 코드가 비효율적인가?” 정도로만 생각했고, 어디를 고쳐야 할지 바로 감이 오지 않았다.

그때 깨달은 건

‘정답을 구하는 방식’과 ‘제한 시간 안에 구하는 방식’은 다르다 는 점이었다.

이중 반복문 자체가 문제라는 사실을 인식하지 못하고, 조건문이나 변수 사용 같은 사소한 부분만 계속 의심하고 있었다.

딕셔너리 사용

정렬된 숫자 배열에서 각 숫자의 위치(index)를 미리 기록해 두면, 나중에는 그 값을 바로 꺼내 쓰기만 하면 된다.

중복 제거
정렬
숫자를 key로, 위치를 value로 하는 딕셔너리 생성

처음에는 dict[key] = value 라는 문법조차 직관적으로 와닿지 않아 많이 헷갈렸지만,