백준 18870 - 좌표압축

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

 

나의 풀이 ==> 시간 초과 발생

사실상 for문 2번을 사용해서 풀면 답이 쉽게 나오는 문제이지만, 

시간을 고려하지 않아 백준에서는 시간초과로 오답처리가 된다.

for문을 2번 사용하면 O(n^2) 시간 복잡도를 갖으므로 리스트가 아닌 딕셔너리를 통해 문제를 해결해야한다.

 

다른 사람의 풀이를 참고하여 코드를 작성하였다.

문제 해결 순서는 다음과 같다.

 

1. 입력받은 숫자들이 들어있는 리스트를 set()으로 만들어 중복을 제거한다.

2. 중복을 제거하여 만든 리스트를 정렬한다.

3. for문을 사용하여 정렬한 리스트의 처음 인덱스부터 마지막 인덱스까지 접근한다.

빈 딕셔너리의 key값으로 리스트의 원소를 넣고 value값으로는 순위를 넣는다.

==> 입력받은 숫자들이 들어있는 리스트에 중복이 있어도 해당 숫자가 key값으로 들어가므로

어차피 동일한 value값이 나온다.

4. 마지막으로, 입력받은 숫자들이 들어있는 리스트를 돌면서 해당 숫자를 딕셔너리의 key값으로 넣어

순위인 value값을 출력한다.

 

import sys
l=[]
n=int(input())
l=list(map(int, sys.stdin.readline().split()))
s=list(set(l))
s.sort()
dict={}

for i in range(len(s)):
    dict[s[i]]=i
for i in l:
    print(dict[i], end=' ')