티스토리 뷰
문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
numbers | return |
[6, 10, 2] | 6210 |
[3, 30, 34, 5, 9] | 9534330 |
문제 접근
처음에는 단순히 배열의 원소를 모두 문자열로 타입 캐스팅을 수행하고 사전식으로 오름차순 배열한 후 모두 연결하면 해결될 수 있을 것 같았다. 하지만 ['12', '121'] 의 경우 사전식 오름차순 정렬 후 연결하면 '12112'이 되며 이수는 '12121' 보다 작은 수가 된다.
이를 해결할 수 있는 방안으로 두 가지가 떠올랐다.
첫 번째, 순열 알고리즘을 통해 모든 가능한 수의 조합을 구하고 이중 가장 큰 수를 선택한다.
이 해결 방안은 충분히 가능한 방안이지만 시간 복잡도가 O(n^2)이다. 배열의 최대 길이가 100000 = 10 * 10^4 총 시간 복잡도는 10 * 10^8 약 10억번 연산이 수행되기 때문에 배제하였다.
두 번째, 두 수를 앞뒤, 뒤앞으로 조합한 수를 비교하여 오름차순 정렬한다.
가장 처음 생각했던 정렬 방식은 단순히 각 수를 비교하여 오름차순 정렬하기 때문에 ['12', '121']와 같은 반례가 존재한다. 그렇다면 앞뒤, 뒤앞(12121, 12112)한 형태 자체를 비교한다면 위와 같은 반례는 해결 될 것이다.
두 번째 해결책을 적용한 결과 마지막 테스트 케이스를 통과하지 못하였다. 다시 문제를 천천히 읽기 시작하였다.
배열의 원소는 0이상 1000이하, 배열의 크기는 1 이상 100,000이하이다. 여기서 간과한 점, 당연히 0은 가장 작은 양의 정수이기 때문에 절대로 맨 앞에 존재할 수 없다는 것. 하지만 모든 배열의 원소가 0이라면 0은 수 조합의 가장 앞에 존재할 수 있다.
[0, 0, 0, 0]은 어떤 수로 표현 되어야할까?
'0000'이 아닌 '0'으로 표현되어야할 것이다.
생성된 문자열의 맨 앞 Character가 0인 경우는 모든 원소가 0인 경우밖에 존재하지 않기 때문에, 이 경우 '0'을 반환하는 처리를 추가한다.
소스 코드
import java.util.*;
class Solution {
public String solution(int[] numbers) {
String[] strNums = new String[numbers.length];
for(int i=0;i<numbers.length;i++){
strNums[i] = String.valueOf(numbers[i]);
}
Arrays.sort(strNums, new Comparator<>(){
public int compare(String s1, String s2){
return (s2 + s1).compareTo(s1 + s2);
}
});
StringBuilder sb = new StringBuilder();
for(int i=0;i<strNums.length;i++){
sb.append(strNums[i]);
}
if(sb.charAt(0) == '0'){
return "0";
}
return sb.toString();
}
}
'PS > 프로그래머스' 카테고리의 다른 글
[프로그래머스 고득점 kit]탐욕법 Level2 큰 수 만들기 (0) | 2020.11.04 |
---|---|
[프로그래머스 고득점 kit]완전탐색 Level2 카펫 (0) | 2020.11.02 |
[프로그래머스 고득점 kit] 힙 Level3 디스크 컨트롤러 (0) | 2020.09.29 |
[프로그래머스 고득점 kit] 힙 Level2 더 맵게 (0) | 2020.09.25 |
[프로그래머스 고득점 kit] 스택/큐 Level2 프린터 (0) | 2020.09.25 |