[BOJ][⚪2][백준#18870] 좌표 압축

문제 출처

BAEKJOON Online Judge #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

출력

2 3 0 3 1

예제 2

입력

6
1000 999 1000 999 1000 999

출력

1 0 1 0 1 0

My Sol

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
dictA = {}

for a in arr:
    dictA[a] = 1

sumV = 0
dictB = {}
for k in sorted(list(dictA.keys())):
    dictB[k] = sumV
    sumV += 1

for a in arr:
    print(dictB[a], end=' ')

딕셔너리의 해싱을 이용해서 문제를 풀었다. 입력되는 배열의 값을 각각 key로 하여 1을 보관한 뒤, keys() 메서드를 이용하여 key를 리스트로 변환하였다. 이를 크기순으로 오름차순 정렬하여 각 key들을 다시 key로 하는 dictB를 만들어 순서를 누적해 값으로 저장해준다. 이후 다시 처음의 arr 각각을 key로 하여 dictB에서 조회해 출력하면 되겠다.

결과

맞았습니다!!

모범답안

출처

from sys import stdin

n = int(input())
arr = list(map(int, stdin.readline().split()))
dic = {}
result = sorted(list(set(arr)))
for i in range(len(result)):
    dic[result[i]] = i


print(' '.join(str(dic[i]) for i in arr))

연산 시간 측면에서 2배 이상 효율적인 코드였다.

처음부터 arr을 set으로 형변환하여 중복을 제거한 뒤, 이를 list로 형 변환, sort한 것을 result로 저장한다. 이 크기만큼 for문으로 값으로 지정하여 dict에 저장하고, 공백 간격을 주고 join하여 출력한다.

set으로 중복을 제거해 정렬한 것이 시간을 단축에 큰 요인이 되었을 것이고, for문의 index를 이용해 dict에 값을 넣어준 것도 좋은 방식인 것 같다.

join 함수 내에 for문이 들어갈 수 있다는 것을 처음 알았다. 효과적인 것 같다.