[백준 16496번] 큰 수 만들기 - java

문제 설명

1. 음이 아닌 정수 N개가 들어있는 리스트가 주어진다.

2. 이걸로 만들 수 있는 가장 큰 수를 return한다.

3. 답이 0이면 무조건 0하나만 출력되어야 한다. 0이 아닌 모든 수는 0으로 시작하지 않는다.

풀이 과정

 1. 진짜 쉽게보고 풀었는데 생각보다 난이도가 있었다.. 또 다 풀어놓고 뻘짓해서 시간 엄청 보냈다. 문제의 내용을 잘 읽어봐야 할 것이다.

 2. 먼저 입력은 String으로 입력받는다. 이걸 사용하면 더 쉽게 풀 수 있다.

 3. 입력받은 String들을 배열로 만들고 내림차순으로 정렬한다. <- 이렇게 하면 int를 정렬하는 것과 다르게 사전순으로 정렬이 가능하다.

ex) int로 받았을 때에 [ 1 33 4 ] 을 입력받으면 내림차순 정렬 시 [ 33 4 1 ] 이렇게 된다.

     이걸 String으로   [ 1 33 4 ] 을 입력받으면 내림차순 정렬 시 [ 4 33 1 ] 이렇게 된다.

 4. 그리고 중요한 것이 [ 45 44 43 42 41 4 ] 이렇게 입력받은 경우 가장 큰 수를 만들면 다음과 같다.

-> 45,4,44,43,42,41

     그런데 위의 3까지만 진행하면 이렇게 정렬될 것이다.

-> 45,44,43,42,41,4

     이걸 해결하는 방법을 생각해 보았는데, '4'라는 자리수로 시작하는 경우 숫자 4는 그 자리수로 시작하는 숫자들 중 무조건 맨 뒤에 위치하게 된다.

     이런 식으로 생각하면 숫자 [ 434 4355 4322 43 ] 이렇게 있으면 당연히 43 맨뒤에 위치할 것이다.

     그러면 그냥 위의 43이라는 숫자 자체를 포함하는 숫자가 앞에 존재할 때, 어떤 숫자가 앞에 오는 것이 더 클지를 비교하여 넣으면 될 것이다.

43,4322는 4322,43보다 크다.

 5. 그렇게 숫자의 위치를 바꾸어 주고 만들어진 모든 ArrayList를 이어붙여 출력하면 된다. 참고로 0000이면 0이 나와야 한다.

 

코드