파이썬 알고리즘 126번 | [백준 18870번] 좌표 압축

Yunny.Log ·2022년 2월 25일

Algorithm

목록 보기

129/318

126. 좌표 압축

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

제한
1 ≤ N ≤ 1,000,000
-109 ≤ Xi ≤ 109
예제 입력 1
5
2 4 -10 4 -9
예제 출력 1
2 3 0 3 1
예제 입력 2
6
1000 999 1000 999 1000 999
예제 출력 2
1 0 1 0 1 0

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

사전에 값:인덱스값 저장
사전으로 키값 빼오는 것으로 인덱스 추출


import sys
n = int(sys.stdin.readline())
arr=[]
rank=[]
arr=list(map(int,sys.stdin.readline().split()))
rank=arr
rank=sorted(list(set(rank)))

rank2={}
for i in range(len(rank)):
    rank2[rank[i]]=i


for i in arr :
    print(rank2[i],end=" ")

<다른 분의 풀이 or 내 틀린 풀이, 문제점>

시간초과 코드


n=int(input())
arr=[]
rank=[]

arr=list(map(int,input().split()))
rank=arr
rank=sorted(rank)
rank=list(set(rank))
total=[]

for i in arr :
    for j in range(len(rank)) : 
        if i==rank[j]:
            print(j, end=" ")
            break

=> 이중 for문을 없앨래
=> 근데 여기서 sorted는 -10, -9를 양수 뒤에 배치, sort()를 해야만 바르게 나옴; 그래서 아래와 같이 수정하겟삼

import sys
n = int(sys.stdin.readline())
arr=[]
rank=[]
arr=list(map(int,sys.stdin.readline().split()))
rank=arr
rank=list(set(rank))


for i in arr :
    rank.sort()
    for j in range(len(rank)) : 
        if i==rank[j]:
            print(j, end=" ")
            break