(다시 풀어볼 문제)[백준] 18870 좌표 압축 - python

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

18870번: 좌표 압축

 

(티스토리야 반갑다... 카카오 서버가 터지는 사태 이후로 티스토리 접속이 원활하지 않아서 지난주 금요일 이후로 오랜만에 접속해서 TIL을 올리는 것 같다!)

 

이 문제는 사실 꽤 정답까지 근접했던 것 같은데 마지막 한방이 부족했다. 순간순간에 어떤 자료구조를 쓰는게 효율적인지 아직 손에 익지 않은 탓이겠지.

 

문제에서 원하는 좌표 압축이란 i번째 수보다 작은 서로 다른 좌표의 개수를 Xi`에 저장하는 것이다. 즉 중복을 허용하지 않는 본인보다 작은 요소의 개수를 세어주면 된다.

 

• 중복 허용 X -> set() 으로 변환하여 중복 제거
• 본인보다 작은 요소의 개수 : sorted()하여 정렬한다. 이때 인덱스값이 해당 요소보다 작은 값의 개수이다.

 

여기까지는 어렵지 않게 떠올렸다. 다만 인덱스값과 해당 데이터를 매번 입력받은 data를 돌면서 index() 함수로 찾았다는게 문제였다..^^ 이럴 필요가 전혀 하등! 없다. 그러나 머리가 왜인지 안 돌아가서... 살짝 구글링했다. 아쉽다... 

 

dictionary 자료구조를 사용하여 (key:value) - (값 : 인덱스) 형태로 저장해준 뒤 data를 돌면서 해당 자료를 dictionary에서 찾으면 된다. 그래야 정답을 출력할 때 시간초과가 안 난다. 

 

코드는 다음과 같다. 마지막은 띄어쓰기 때문에 한칸 빼고 출력해줬다.

import sys

input = sys.stdin.readline

N = int(input())

data = list(map(int, input().split(" ")))

sorted_data = sorted((set(data)))

dictionary = {sorted_data[i]: i for i in range(len(sorted_data))}

answer = ""
for d in data:
    answer += str(dictionary[d]) + " "

print(answer[:-1])

index()함수 썼다가 dictionary로 트니까 바로 정답..!

 

 

---

그 순간에 적합한 자료구조와 로직을 떠올리는 건 연습으로 얼마든지 해낼 수 있다고 믿는다. 꾸준히 꾸준히!