백준 18870번 좌표 압축 문제풀이, 파이썬

백준 18870번 : 좌표 압축 문제풀이 [파이썬] 

---

<문제>

 

18870번 문제의 내용은 아래와 같습니다. 

좌표 압축 

 

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 1 복사

5
2 4 -10 4 -9

예제 출력 1 복사

2 3 0 3 1

예제 입력 2 복사

6
1000 999 1000 999 1000 999

예제 출력 2 복사

1 0 1 0 1 0

---

 

 

<작성한 코드>

 

#좌표 압축
import sys
N = int(input())
arr = list(map(int, sys.stdin.readline().split()))
arr2 = list(set(arr))
arr2.sort()

arrdict = {}
for i in range(len(arr2)):
  arrdict[arr2[i]] = i

#줄 바꿈 없이 중간 한칸 공백으로 출력해야함
for i in arr:
  print(arrdict[i], end = ' ')

---

 

 

<코드 풀이>

우선 문제에서 요구한대로 

공백 한 칸으로 구분된 입력값들을 받아주기 위한 코드를 아래와 같이 작성해주었다. 

import sys
N = int(input())
arr = list(map(int, sys.stdin.readline().split()))

이때 문제 조건을 보니 주어지는 숫자의 범위가 꽤 커서

시간초과가 날 수도 있을것같아, import sys를 사용했다. 

 

 

우리가 결국 출력해야할 값은 해당 좌표의 크기보다 작으면서 서로 다른 좌표들의 개수이다. 

arr2 = list(set(arr))
arr2.sort()

따라서 중복을 제거해주기 위해 set()함수를 사용해주었고, 

좌표값들을 오름차순으로 정렬하였다. 

정렬을 한 이유는 결국 정렬한 리스트의 index 값이 우리가 출력해야할 값과 같은 값을 가지기 때문이다. 

ex) [2, 3, 5, 6] 과 같은 리스트가 있다면 첫번째 원소인 2는 가장 작은 좌표값으로 

2보다 작은 좌표는 없기에 0을 출력해야하는데, 이 값은 해당 원소의 index값과 같게 된다. 

 

 

 

arrdict = {}
for i in range(len(arr2)):
  arrdict[arr2[i]] = i

이때 단순히 해당 index값을 출력해주는 것이 아니라,

딕셔너리를 이용해 해당 값에 해당하는 index를 따로 저장해주었다. 

 

 

for i in arr:
  print(arrdict[i], end = ' ')

출력하는 부분은 위와 같이 코드를 작성해주었다.

출력 예제에 나온 것처럼 줄 바꿈 없이 중간에 한칸 공백을 가지고 출력해야하기 때문에

end = ' '를 넣어주었다.