🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]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


해결할 방법을 생각해보자.💡

리스트 안에서 중복값을 없앤 뒤 오름차순으로 정렬해서 그 순위를 매겨 출력하는 문제다.(순위가 0순위부터임)

좌표의 개수 N을 받아주자.

import sys
N = int(sys.stdin.readline())

공백 한칸으로 구분된 값들을 받아주자.

A = list(map(int, sys.stdin.readline().split()))

그리고 이 값들의 중복값을 없애주고 오름차순으로 정렬해주어 다시 리스트로 만들어주자.

After_A = list(sorted(set(A)))
  1. 시간초과

사실 여기서 시간 초과가 났었다.

리스트.index()를 사용했었는데 제한을 보면 N의 개수가 1부터 1,000,000이고, index()같은 경우 시간복잡도가 빅오 표기법으로 O(N)이라고 한다.

for i in A:
  print(After_A.index(i), end= ' '')
  1. 이후 개선한 정답

딕셔너리를 사용하면 전체적으로 훑어볼 필요 없이 해당 값을 바로바로 뽑아내어 시간을 줄일 수 있다.

키값에는 오름차순으로 정렬한 순서대로 해당 값들이 들어가고, 밸류값으로는 그 값들의 인덱스가(길이로 측정해 0부터 시작해서) 들어간다.

A_dict = {After_A[i] : i for i in range(len(After_A))}

이제 A리스트 안의 요소들을 순서대로 반복시켜서 A_dict의 키값으로 넣어서 출력해주면 완료

for i in A:
  print(A_dict[i], end = ' ')

코드 💻

import sys

N = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split()))
After_A = list(sorted(set(A)))
A_dict = {After_A[i] : i for i in range(len(After_A))}
for i in A:
  print(A_dict[i], end = ' ')

해결 로그

문제 푼 날짜 체크
2022-07-09 ✔
   
   
   
   

2022

[web]jQuery 복습 3

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

13 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

14 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

5 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

10 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑