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

📌 문제

💯 정답

• 방법 1. 답은 나오지만 시간 초과..

import sys
input = sys.stdin.readline

n = int(input())
mark = [0] * n
dots = list(map(int, input().split()))
origin = dots[:]                        # [ 2 4 -10 4 -9 ]
dots.sort()                             # [ -10 -9 2 4 4 ]
# print("origin: ", origin)
# print("dots: ", dots)
for i in range(1, n):
    if dots[i] != dots[i-1]:
        mark[i] += mark[i-1] + 1
    else:
        mark[i] = mark[i-1]
# print("mark: ", mark)

for k in origin:
    for l in range(n):
        if k == dots[l]:
            print(mark[l], end=" ")
            break

• 방법 2. 딕셔너리 사용 정답!!

import sys
input = sys.stdin.readline

n = int(input())
dot = list(map(int, input().split()))
dot2 = sorted(list(set(dot)))
dic = {dot2[i] : i for i in range(len(dot2))}	# {-10:0, -9:1, 2:2, 4:3}
for j in dot:
    print(dic[j], end=" ")

📝 설명

• 방법 1.은 우선 입력받은 좌표 리스트 dots를 origin에 복사해놓고,
  순서를 체크할 mark 리스트를 모든 인덱스 값을 0으로 초기화한다.
  
  dots를 오름차순으로 정렬한 후 for문으로 dots의 인덱스 1부터 끝까지 비교하고,
  만약 현재 인덱스와 전 인덱스가 다르면 1을 증가시키고 같다면 전 인덱스의 값을 그대로 가지게 한다.
  
  즉, 만약 dots의 오름차순 정렬이 [ -10 -9 2 4 4 ]라면 mark는 [ 0 1 2 3 3 ]이 된다.
  
  그리고 dots와 origin을 비교하며 만약 origin의 값이 dots의 값에 있다면,
  해당 값의 인덱스와 동일한 mark의 인덱스에 해당하는 값을 출력시키게 했다.
  
  -> 하지만 이런 로직으로는 시간 초과가 떴다.

• 방법 2.는 딕셔너리를 사용해 쉽게 풀어냈다.

  입력받은 좌표를 리스트를 set을 이용해 중복을 제거한 상태로
  새로운 리스트 dot2에 오름차순으로 정렬해 저장한다.
  
  그리고 dot2의 값을 key로 가지고 인덱스를 value로 가지는 딕셔너리 dic을 만들었다.
  
  이후 입력받은 dot의 값이 딕셔너리 dic의 key값과 같으면 그 value값을 출력하도록 했다.

⭐️ 알고가기

👉 딕셔너리 설명 바로가기