[Silver II] 좌표 압축 - 18870

[Silver II] 좌표 압축 - 18870

문제 링크

성능 요약

메모리: 144340 KB, 시간: 1852 ms

분류

값 / 좌표 압축, 정렬

제출 일자

2024년 10월 29일 00:16:14

문제 설명

수직선 위에 N개의 좌표 X₁, X₂, ..., X_N이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

X_i를 좌표 압축한 결과 X'_i의 값은 X_i > X_j를 만족하는 서로 다른 좌표 X_j의 개수와 같아야 한다.

X₁, X₂, ..., X_N에 좌표 압축을 적용한 결과 X'₁, X'₂, ..., X'_N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X₁, X₂, ..., X_N이 주어진다.

출력

첫째 줄에 X'₁, X'₂, ..., X'_N을 공백 한 칸으로 구분해서 출력한다.

 

 

풀이

 

import sys

N = int(sys.stdin.readline())

m = list(map(int,sys.stdin.readline().rstrip().split()))
sort_m = sorted(set(m))
dic = {sort_m[i] : i for i in range(len(sort_m))} 

for i in m:
    print(dic[i], end=' ')

 

기본적으로 이중 for문을 적용하고 배열에서 .index() 함수를 이용하면 시간 초과가 발생하게 된다.

 

따라서 문제 풀이는 크게 다음과 같다.

 

1. 해당 input으로 받은 배열의 중복을 set으로 제거한다.

2. 중복을 제거한 리스트를 오름차순으로 정렬한다. -> sort_m

3. 이제 해당 리스트를 dict형태로 만든다. key는 sort_m의 각 원소들이며 value는 해당 원소의 index이다.

 

이후 한번의 for문과 hash에서 값을 찾아올 수 있기 때문에 시간 초과에서 벗어날 수 있다.