[Python] 백준 온라인 저지 18870 좌표 압축

목차

문제

---

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

18870번: 좌표 압축

 

설계&풀이

---

좌표 압축이란, 주어진 좌표를 크기순으로 정렬하는 행위를 말한다.
예를들어 다음과 같은 리스트(좌표) 가 주어졌다고 가정하면..

tempList = [1, 3, 4, 2, 4]

# 좌표압축 실행 후

print(tempList)

# 결과
'''
[0, 2, 3, 1, 2]
'''

이런식으로, 오름차순 정렬 기준으로 1은 0번째 수, 2는 1번째 수, 3은 2번째 수, 4는 3번째 수 가 된다.
이 때 중복값을 제거해줘야 하므로 set() 을 사용했다.

처음엔 딕셔너리를 사용하지 않고 set으로 풀었다. 그러더니 시간초과가 나더라

이유는 N이 1,000,000이라서 O(N)이라 그렇다.
짱구를 좀 굴려봤는데, 보통 이런 문제들은 딕셔너리를 사용하면 쉽게 풀렸다. O(1) 이라서.

좌표압축이라는 개념 자체를 이해하는데 시간이 좀 오래걸렸다;; 문제 자체는 쉬운편.

코드 GIT 주소

---

https://github.com/kkkapuq/AlgorithmStudy/blob/d0f706ce7b5c468bd6d99f3fad35c09beefc451d/Python/220728_BOJ_18870_%EC%A2%8C%ED%91%9C%20%EC%95%95%EC%B6%95/1.py

GitHub - kkkapuq/AlgorithmStudy: 알고리즘 문제풀이

 

코드

---

'''
1. 좌표압축 = 작은순서부터 인덱싱 해주는것
2. 입력된 좌표 리스트를 정렬해준다음... 순서대로 딕셔너리에 넣어주면 될듯?
'''
n = int(input())

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

# set으로 중복 제거 및 정렬
setList = list(set(numList))
setList.sort()
answerDic = {}

for i in range(len(setList)):
    answerDic[setList[i]] = i

for i in range(len(numList)):
    print(answerDic[numList[i]], end=' ')

 

결과

---

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡