[BOJ] 백준 16496 큰 수 만들기 (JAVA)

📑 문제

백준 16496 큰 수 만들기

---

🌱 아이디어

숫자 정렬이 아닌 사전순(문자열) 정렬을 사용하자

 

"큰 수"의 기준이 아닌 사전순 정렬을 사용한다. 9, 30 두 숫자가 있다. 두 수를 조합하여 만들 수 있는 가장 큰 수는

930이다. 즉 문자열 정렬을 통해 가장 뒤서는 순(30, 9)부터 숫자를 합치며 풀면 된다.

 

하지만 하나의 반례가 있다. 3,30 두 숫자가 있다. 두 수를 조합하여 만들 수 있는 가장 큰 수는 330이다.

하지만 문자열 정렬 시 가장 뒤서는 번호가 30이 된다 (3,30) 위처럼 출력 시 303이라는 숫자가 만들어진다.

 

이미 정렬된 문자열에서 앞의 숫자 '3', '3'0 같을 경우 330, 303이 큰지 판단하고, 결괏값에 따라 

문자열을 서로 변경해 주는 형식으로 풀면 된다.

 

입력 값으로 1,000,000,000까지 들어온다. 만약 두 문자열을 이어 붙여서 정수형으로 변환 시

int타입은 물론이고 long타입도 overflow가 발생한다. BigInteger타입을 사용해야 한다.

---

🌱 코드 및 풀이

 

---

🌱 느낀 점

플레 문제 중에서도 쉬운 편에 속하는 것 같다.

가장 어려웠던 점은 반례를 처리할 때 어떻게 비교를 할까였다. N이 작기도 해서 문자열을 합치고 숫자로 비교했다.

O(N^2)의 알고리즘으로 풀었지만 더 좋은 방법이 있을 것 같다 나중에 리팩토링을 해봐야겠다 끝!