[백준, python] 18870번 - 좌표 압축

백준 문제풀이 시작

---

문제

수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.

출력

첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.

---

풀이

풀이 확인하기

입력을 받은 뒤 리스트를 복사하고, 해당 리스트를 set으로 바꿔 중복되는 요소를 지우고, 다시 리스트로 바꾼 뒤 해당 리스트를 정렬해서 순서를 추출했다. 이후 기존 리스트와 순서를 비교하여 출력한다. 이때 비교를 하는 과정에서 그냥 반복문으로 비교하면 시간 초과가 발생하므로 이분 탐색으로 비교한다.

import sys
import copy
input = sys.stdin.readline


num = int(input())
lis = list(map(int, input().strip().split(" ")))

lis2 = copy.deepcopy(lis)
lis2 = list(set(lis2))
lis2.sort()

for i in range(0, len(lis)):
    left = 0
    right = len(lis2)-1
    while(left <= right):
        mid = (left+right)//2
        if (lis2[mid] == lis[i]):
            print(mid)
            break
        elif (lis2[mid]>lis[i]):
            right = mid-1
        else:
            left = mid+1

P.S. 지금 보니 복사 이후 set으로 바꾸고 다시 리스트로 바꾸는 과정이 매우 비효율적인 것 같다. 입력받는 과정에서 저장을 딕셔너리로 저장한 뒤 key값만 추출하면 조금 더 빠르게 할 수 있지 않을까 싶다.

• baekjoon
• python