[알고리즘] 백준18870 좌표압축 - 파이썬

오늘은 백준 단계별 풀기이고 뒤에서부터 풀어보려고 한다.

 

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

18870번: 좌표 압축

 

 

[풀이 코드]

 

- 첫번째 풀이

from sys import stdin

n = int(input())
a = list(map(int, stdin.readline().split()))
b = sorted(set(a)) # set으로 중복을 제거

# print(a)
# print(b)

for i in range(len(a)):
    for j in range(len(b)):
        if a[i] == b[j]:
            a[i] = j

print(a)

첫 번째 풀이는 시간 초과.. 이유는 2중 반복문을 써서 그런 것 같다. 먼저 풀이는 set을 활용해서 중복을 제거해주고 sorted로 정렬을 했다. 그리고 두배 열을 이중 반복문으로 돌면서 a원소와 일치하면 b의 인덱스로 교체해준 뒤 출력을 해주는 방식이었다. 

 

- 두번째 풀이

from sys import stdin

n = int(input())
a = list(map(int, stdin.readline().split()))
b = sorted(set(a)) # set으로 중복을 제거

b_dict = {b[i] : i for i in range(len(b))}

for i in a:
    print(b_dict[i], end= ' ')

두 번째 풀이에서는 딕셔너리를 활용해서 key에는 원소가 value에는 순서를 넣어줬고 for문을 돌면서 순서대로 a의 원소에 따른 딕셔너리의 value 값을 출력했다.