[백준 / BOJ] 18870번 좌표 압축 (C++, Python)

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

18870번: 좌표 압축

---

문제

---

문제 풀이

C++ 상세 풀이

그냥 find함수를 쓰면 시간 초과가 나므로 lower_bound를 활용하면 된다.

 

lower_bound에 대한 자세한 설명은 밑의 링크를 참고하면 좋을 것 같다.

 

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

Python 상세 풀이

dict 자료형을 사용하면 쉽게 풀 수 있다. arr에 선입력을 받고, arr2는 중복을 없앤 후 정렬해준다.

 

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

 

C++ 코드 전문

 

Python 코드 전문

 

소감