[BOJ] 18870. 좌표 압축

문제

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

• 처음에는 문제가 잘 이해가 안갔다
• 문제 예시를 보면 이해가 잘됨

• 2 4 -10 4 -9
  
  # 출력 : 2 3 0 3 1

• 좌표를 오름차순 정렬한 후 인덱스를 반환해주면 된다!

 

---

 

주요 아이디어

• 위에서 했던 문제 설명 그대로
• 좌표를 오름차순 정렬한 후 인덱스를 반환

 

---

 

코드 구현 (Python 3)

 

import sys

n = int(input())
coor = list(map(int,sys.stdin.readline().strip().split()))

sorted_coor = sorted(list(set(coor)))

for c in coor:
    print(sorted_coor.index(c), end=' ')

 

 

시간 초과...

---

 

실패 원인

• list.index() 메서드가 순차 탐색이기 때문에 시간이 오래 걸린다고 한다
• 딕셔너리 자료형으로 만들어보자!

 

---

 

코드 재구현 (Python 3)

import sys

n = int(input())
coor = list(map(int,sys.stdin.readline().strip().split()))

sorted_coor = sorted(list(set(coor)))

# 정렬 인덱스 딕셔너리 형태로 만들어주기
dictList = dict(zip(sorted_coor, list(range(len(sorted_coor)))))

for c in coor:
    print(dictList[c], end=' ')

 

---

 

제출 결과