[algorithm] 백준 18870 - 좌표 압축

[algorithm] 백준 18870 - 좌표 압축

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 18870번 문제 - 좌표 압축 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 18870

 

백준 18870번 좌표 압축 문제 보러가기

 

반응형

 

문제 해석

 

문제에서 주어지는 좌표들을 오름차순으로 정렬했을 때 제일 작은 숫자부터 0으로 생각하고 순서대로 1씩

올려주면서 좌표를 압축하는 문제입니다.

힌트 : 짝을 지어줄 땐 키와 값이 존재하는 자료형을 사용하면 좋겠죠??

 

풀이

 

# 18870 좌표 압축

n = input()

dict = {}

pos_list = list(map(int, input().split()))
tmp = sorted(list(set(pos_list)))

for i in range(len(tmp)):
    dict[tmp[i]] = i

for i in pos_list:
    print(dict[i], end=' ')

 

풀이 해석 및 팁

 

코드의 실행시간을 줄이려면 딕셔너리를 사용하는 것이 아주 효과적인 문제입니다.

처음에 입력값을 받아올 때 숫자간의 순서가 문제 해결에 있어 신경써야하는 부분이므로

tmp 변수처럼 다른 변수를 만들어 중복을 없애고 오름차순 정렬을 한 리스트를 저장해줍니다.

그 후에 딕셔너리에 키값으로 tmp 리스트의 요소를 사용하고 그 요소의 순서를 값으로 저장해줍니다.

마지막으로 문제에서 원하는 출력 형식으로 for 반복문을 사용해서 문제를 해결하였습니다.

---

여기까지 백준 18870번 좌표 압축 문제 풀이였습니다.

 

이번 문제의 정답률은 39% 정도입니다.

 

파이썬의 리스트, 집합, 딕셔너리를 잘 활용하면 큰 어려움 없이 해결이 가능한 문제였습니다.

 

궁금하신 점이 있으시다면 댓글로 남겨주세요.

 

감사합니다.