반응형
https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에
www.acmicpc.net
소스코드
풀이
★ 먼저 좌표 압축에 대해서 잘 이해가 안될수도 있는데, 문제에서 주어진 좌표 압축이란 만약 5,55,555,5555가 주어졌을 때, 좌표 압축을 한 결과는 각각 0,1,2,3이 되게 됩니다, 즉 가장 작은 수부터 차례대로 0,1,2, ... 가 부여되는 방식입니다 !
★ 입력받는 수들 중, 중복이 있을 수 있기 때문에 set 자료구조를 사용하여 중복을 제거해줍니다. 그 후 좌표 압축을 위해 배열을 오름차순 정렬해야 하는데, set 구조는 sort, sorted 함수를 사용할 수 없기 때문에 다시 list로 변경한 뒤 정렬을 진행해줍니다 !
★ 좌표 압축을 한 결과를 입력 받을 딕셔너리를 선언합니다. 정렬한 배열을 0부터 배열 길이만큼 돌면서 배열 값을 key, 인덱스를 value로 딕셔너리에 저장해줍니다.
★ 그 후 순서대로 출력해주시면 됩니다 :)
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1431번: 시리얼 번호 (Python) (1) | 2023.10.20 |
|---|---|
| [백준 알고리즘] 8979번: 올림픽 (Python) (0) | 2023.10.20 |
| [백준 알고리즘] 16928번: 뱀과 사다리 게임 (Python, BFS) (0) | 2023.10.18 |
| [백준 알고리즘] 13549번: 숨바꼭질 3 (Python, BFS) (0) | 2023.10.18 |
| [백준 알고리즘] 2346번: 풍선 터뜨리기 (Python) (0) | 2023.10.18 |