[Python] 백준 파이썬 18870 좌표 압축

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

18870번: 좌표 압축

• 첫 시도

# 백준 18870 좌표 압축
n = int(input())
x_list = input().split()
x_list_2 = []
for i in range(len(x_list)):
  k = 0
  for j in range(len(x_list)):
    if int(x_list[i]) > int(x_list[j]):
      k += 1
  x_list_2.append(str(k))

print(' '.join(x_list_2))

단순하게 첫 좌표를 리스트로 받아줍니다.

압축된 좌표가 들어갈 리스트를 생성해줍니다.(x_list_2)

반복문을 이용해서 크기 비교를 해주며 더 작은 값이 몇개 있는지 체크해서 추가해줬습니다.

이렇게 중복되는 999도 전부 카운팅 돼서 답이 맞지 않습니다.

아마 '크기'에만 신경을 써서 이렇게 된 듯하여 중복치 제거를 위해 set(집합)을 이용해 다시 풀어줍니다.

 

• 두 번째 시도

import sys
n = int(input())
# x_list = list(map(int, input().split()))
x_list = list(map(int, sys.stdin.readline().split())) # 1

x_set = set(x_list) # 2

x_unique_list = list(x_set) # 3

x_unique_list.sort() # 4

x_2 = {}

for i in range(len(x_unique_list)): # 5
  x_2[x_unique_list[i]] = i

for j in range(n): # 6
  x_prime = x_2[x_list[j]]
  print(x_prime, end=' ')

생각해보면 리스트에 수가 있을 때 자기보다 작은 수의 갯수라하면 

정렬된 리스트에서 자기 자신의 인덱스값 이라고 볼 수 있습니다.

그래서

1. 먼저 리스트로 좌표 받아줍니다.
2. 중복치 제거를 위해 set(x_list) 해줍니다.
3. 중복치가 제거된 애들을 다시 리스트로 바꿔줍니다 (x_unique_list)
4. 다시 정렬해줍니다. 이 리스트 안에있는 숫자가 가지는 인덱스값이 자기보다 작은 '서로 다른'수의 갯수입니다.
5. 딕셔너리를 하나 만들어주고 {좌표 : 인덱스값} 형식으로 되게 넣어줍니다.
6. 이제 제일 첫 좌표(x_list)에 해당하는 숫자들의 x_unique_list 에서의 인덱스 값을 x_prime에 할당 해주고, 공백을 기준으로 한 줄에 출력 해줍니다.