문제 링크
문제
- 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
- 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
- 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
👀 풀이
- 주어지는 배열의 숫자들을 조합해서 숫자를 만들다 보면 정수 자료형의 범위를 초과할 수 있다.
- 그래서 조합을 시도할 땐 정수를 문자열로 바꾸어야 한다. 여기까지는 맞는 접근…
1차 시도
- 배열의 모든 원소를 조합해서 숫자를 만들어봐야 하기 때문에 순열문제라고 생각했다. 그래서 순열 만드는 함수를 만들어 모든 순열을 구한 다음에 그걸 정렬해서 가장 큰 수를 리턴하는 방식으로 했다.
- 테스트 케이스는 통과했지만 막상 제출하니까 시간초과가 뜨면서 실패했다…ㅎ
- 나중에 풀이를 보니까 접근 방법 자체가 달라서 통과할 수 없는 알고리즘이었다. 순열을 구하는 메서드에서 시간초과가 발생했거나 무한루프가 돈 것으로 예상되었다.
2차 시도
- 풀이 영상을 보고 처음에 생각했던 접근방법이 틀렸다는 걸 알게 되었다.
- 이 문제를 시간 안에 통과하기 위한 접근법은 숫자를 -> 문자로 바꾸고 -> 내림차순으로 정렬해서 -> 문자열로 조합 이었다.
- 하지만 무작정 내림차순으로 정렬하면 테스트 케이스 1처럼
6, 10인 경우에는 610이 큰 수지만 단순 내림차순으로 정렬해 버린 후 조합하면 10, 6이 되어 106이라는 결과를 얻게 된다. 그렇기 때문에 두 수를 조합한 결과가 큰 순서대로 내림차순 정렬될 수 있도록 해야한다.
- 이를 위해
compareTo() 메서드를 사용해 정렬 대상이 되는 앞뒤 원소 두 개를 조합한 결과에 따라 내림차순 정렬이 될 수 있도록 했다.
- 주 언어가 자바지만 정작 코테 준비는
C++이나 파이썬으로 많이 했었기 때문에 자바의 컬렉션에 좀 약했는데 풀이 강의는 자바 사용에 대한 팁도 많이 줘서 좋았다. 이것 하나로 수강료가 아깝지 않았다.
- 프로그래머스 [Java/문제풀이] 코딩테스트 광탈 방지 Kit: Java편 왕추천!!
코드
