[백준/Python] 18870번: 좌표 압축

1. 문제 

18870번: 좌표 압축

글만 읽어봤을 땐 이게 뭔말인고 .. 싶었다. 그래서 예제를 적어보고 스스로 답을 찾아보는 과정에서 알고리즘에 대해서 떠올랐다. 

브론즈에서는 그냥 무작정 코드를 짜면 풀리는 문제가 많았는데 실버단계 문제부터는 이해가 중요한 문제가 많이 나오는 것 같다. 

스스로 예제에 대한 답을 내려보는 과정을 습관들여야겠다. 

 

 

2. 해결

해결방법을 떠올리는 것은 어렵지 않다. X1, X2, ... 을 배열로 두고 

** 중복을 조심해야한다 ! 

** 시간복잡도에 유의해야 한다 ! 

 

알고리즘 

- X1, X2, X3, .. Xn을 nums list에 넣는다. 

- 중복 체크를 위해 check list에 set함수를 통해 nums에서 중복되는 수를 삭제한다. 

- Xi보다 작은 Xj의 수를 출력해야한다 = 오름차순 정렬 시 index와 동일함 , sort를 통해 정렬해준다. 

- nums 배열의 num원소를 하나씩 확인하며 num에 일치하는 check인덱스를 출력해주어야한다 ->dict활용 ! 

- dic에 check배열 속 원소 하나씩 인덱스를 부여해준다. 

 

3. 코드 

n = int(input())
nums = list(map(int,input().split()))
check = sorted(set(nums))

dic = {check[i] : i for i in range(len(check))}
for i in nums:
    print(dic[i], end = ' ')

알고리즘에서 dictionary를 활용하는데 아직 익숙하지 못했던 것 같다. 

잊지말자 딕셔너리 활용 ! 

4. 오답  

처음엔 dic을 활용하지 못하고 하나하나 돌면서 check배열에서 탐색하는 원소보다 작은 원소들의 개수를 세었다.. 하지만 역시나 시간 복잡도에서 걸렸다.. !