[python] 18870번 - 좌표 압축

문제

문제 풀이

자신보다 작은 수의 개수를 출력하는 문제이다.

크기 순대로 정렬하면 자신의 인덱스 번호가 자신보다 앞에 있는 원소의 수가 된다.

이를 이용하여 문제를 풀면 될 것 같으나, 신경 써야 할 점이 두 가지가 있다.

1. 중복된 숫자의 경우 그대로 인덱스를 출력하면 같은 중복 횟수만큼 인덱스가 커져 자신보다 작은 원소의 수가 아니게 된다. 따라서 중복된 원소 처리를 신경 써야 한다.
2. 리스트를 정렬 시 기존 리스트의 순서를 보존해야 출력 시 알맞게 출력할 수 있다.

1번의 경우 중복이 허용되지 않는 자료형인 집합 자료형을 이용하여 중복을 제거하였고,

2번의 경우 sorted를 이용하여 기존 리스트는 보존하고 정렬하여 새로운 변수에 저장하였다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())

arr = list(map(int, input().split()))

arr2 = sorted(list(set(arr)))
dic = {arr2[i] : i for i in range(len(arr2))}
for i in arr:
    print(dic[i], end = ' ')

set자료형을 적용하여 중복을 제거한 후 정렬을 진행하였다.

그렇게 되면 인덱스는 앞에서 말한 것과 같이 주어진 숫자 중 해당 숫자가 몇 번째 숫자인지를 의미하게 된다.

이제 딕셔너리를 사용하여 key에는 압축한 결괏값을 집어넣고, value값에는 for range를 이용하여 해당 숫자의 인덱스 값을 넣어 주었다.

출력할 때는 for문을 통해 기존 리스트를 돌면서 리스트 원소를 key값으로 가지는 value값(해당 키의 인덱스 값)을 딕셔너리 검색 연산을 통해 빠르게 반환하였다.

 

list, set, dict 각각의 특징에 대해 잘 알고 있으면 해결 가능한 문제였다.