(python) 백준18870 - 좌표 압축

백준 18870

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

18870번: 좌표 압축

 

1. 문제 설명

 

수들을 입력받아서 자신보다 작은 수가 몇개 있는지 카운팅하는 문제 (수의 중복은 허용하지 않는다.)

 

2. 문제 풀이

 

먼저, 이 문제는 중첩반복문으로 풀게 되면 시간초과가 나오게 된다.

 

그러므로 다른 접근 방법으로 풀어야 한다.

 

잘 생각해보면 자신보다 작은 다른 수들이 몇개 있는지 카운트하는 것은 결국 오름차순으로 정렬된 리스트의 인덱스 값과 같다.

 

ex) 입력 받은 수: 2, 4, -10, 4, -9 -> 중복 재거후 오름차순 정렬: -10, -9, 2, 4

-> -10의 값: 0, -9의 값: 1, 2의 값: 2, 4의 값: 3

 

#입력 구간
arr = list(map(int, input().split()))
#중복 제거
arr2 = list(set(arr))
#오름차순 정렬
arr2.sort()

 

여기서 .index()를 이용하여 출력하려고 하겠지만 이 또한 시간초과가 나온다.

 

그래서 각 수를 key, 인덱스를 value로 하는 딕셔너리에 저장한다.

 

dic = {}
#각 수에 해당하는 인덱스 저장
for i in range(len(arr2)):
    dic[arr2[i]] = i

 

마지막으로 초기 배열을 돌면서 딕셔너리에서 그 수에 해당하는 value를 출력한다.

 

for v in arr:
    print(dic[v], end=' ')

 

3. 전체 코드

 

#입력 구간
n = int(input())
arr = list(map(int, input().split()))
#중복 제거
arr2 = list(set(arr))
#오름차순 정렬
arr2.sort()
dic = {}
#각 수에 해당하는 인덱스 저장
for i in range(len(arr2)):
    dic[arr2[i]] = i
#출력 구간
for v in arr:
    print(dic[v], end=' ')