[Baekjoon] - 18870. 좌표 압축 (S2)

오동훈·2022년 3월 9일
0

Baekjoon

목록 보기
55/58
post-thumbnail

1. Problem 📃

📚 출처 - 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

입출력 예

예제 입력예제 출력
5
2 4 -10 4 -9
2 3 0 3 1
6
1000 999 1000 999 1000 999
1 0 1 0 1 0

2. Logic 👨‍🏫

Logic
1. set을 이용해 중복되는 값을 제거해준 후, set은 sort를 적용시킬 수 없으므로 list로 변경 후 sort를 통해 정렬
2. 앞서 전체를 순회하려면 O(N)의 시간 복잡도가 소요되지만, dict을 이용하면 O(1)의 시간 복잡도로 이용할 수 있다. 그 점을 이용해 dict을 생성해주면 이 문제는 간단히 해결할 수 있다.

3. Code 💻

1. 내가 푼 코드 😁 (시간 초과)

import sys
input = sys.stdin.readline

N = int(input())
coordinates = list(map(int, input().split()))
compare = sorted(list(set(coordinates)))

for i in range(len(coordinates)):
    coordinates[i] = compare.index(coordinates[i])

for i in coordinates:
    print(i, end = " ")

2. 내가 푼 코드 😁 (성공)

import sys
input = sys.stdin.readline

N = int(input())
coordinates = list(map(int, input().split()))
compare = sorted(list(set(coordinates)))

dic = {compare[i] : i for i in range(len(compare))}

for i in coordinates:
    print(dic[i], end = " ")
profile
삽질의 기록들🐥

0개의 댓글