백준 - 정렬 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

예제 출력 1 복사

2 3 0 3 1

예제 입력 2 복사

6
1000 999 1000 999 1000 999

예제 출력 2 복사

1 0 1 0 1 0

처음에 문제 이해 자체를 못했다.

Xj가 대체 뭔 값이지? 구글링을 통해서 문제 해석을 보고 문제를 이해한 후 접근했다.

 

2 4 -10 4 -9에서

2보다 작은 값 -10, -9

4보다 작은 값 -10, -9, 2

-10보다 작은 값 x

4보다 작은 값 -10, -9, 2

-9보다 작은 값 -10

 

따라서 예제 출력 1 = > 2 3 0 3 1

요즘 백준을 풀면서 문제 이해를 못하는 경우가 종종있는데.. 책을 좀 더 많이 읽고 문제를 열심히 풀어야겠다..

 

= 처음 접한 풀이 = 

 

시간 초과로 실패.

시간 초과로 실패했다.

List를 빼고 StringBuilder를 사용해서 출력해도 똑같이 시간 초과로 실패.

그리고 0이 기본 값이기 때문에, 분명 예외 상황이 발생할 수 밖에 없다.

설계를 잘못했다.

 

0 0 1 1 이렇게 있으면 0 0 1 1이 정답인데 / 0 0 0 0이 출려된다. 실패..

중복값을 제거하기 위해 duplication을 사용했는데 이렇게 풀면 안 됨!

예외를 제거하고, 시간을 최대한 단축시킬 방법을 더 고민해보자!

 

= 두번째 접근 =

 

Set을 이용해서 중복 변수를 제거했지만 결과는 똑같이 시간 초과.

문제 의도를 잘못 파악한 것 같다.

 

= 세번째 접근 = ( 구글링 )

 

 

내가 지금까지 접근한 방법은, 첫번째 수를 이용해서 그것보다 작은 수가 몇 개가 있는지 다 count를 한 뒤, 그걸 저장하는 방식을 이용했다. 계속 시간제한 문제가 발생했기 때문에 해결하지 못하고 결국 다른 사람의 코드를 봤다.

 

https://st-lab.tistory.com/279 나보다 더 자세한 내용은 이 주소로 들어가서 보면 된다.

 

나처럼 작은 갯수를 count하는 방식이 아닌, 오름차순으로 정렬 후 중복을 제거하고 맨 앞 부터 0,1,2,3..... 순위를 정하는 방식으로 풀었다.

 

정말 생각하지도 못한 방식이였기 때문에 다른 사람의 코드를 보는게 시야가 넓어진다를 확실하게 느꼈다.

 

오름차순으로 정렬한 것을 map에 key(오름차순으로 정렬된 배열 -10, -9, 2, 4, 4), value(rank)로 저장를 한다.

key값이 중복이 된다면 저장하지 않고 rank++도 실행하지 않음

 

이러한 방식으로 맵에 key, value를 이용해서

 

내가 맨 처음 저장한 num[i]에 값을 get(num[i])를 통해 value를 뽑아낸다.

 

이렇게 좋은 방법이 있다는 거에 대해 놀랍고

 

시간 초과를 좀 더 생각하고 효율적인 방법을 생각할 수 있는 좋은 발판이 되었다.