[programmers] 정렬, 가장 큰 수

코딩테스트 연습 - 가장 큰 수

 

문제

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

해결

key point, numbers의 원소 길이를 맞춰 정렬한다.

1. numbers의 원소 길이를 맞추기 위해 numbers[i]를 3번씩 반복한다.
   • numbers의 원소는 1,000 이하이므로 최소 3번만 반복하면 됨.
   • 더 커지는 경우에 대해서는 정렬에 영향을 주지 않으므로 가능한 방법이다.
2. 길이를 맞춘 문자열로 내림차순 정렬을 한다.
3. 0번째 인덱스부터 순차적으로 조회하며 원본 numbers로 answer를 구성한다.
4. 전부 "0000000"과 같은 문자열이 될 때는 0을 return하고
5. 그 외의 경우에는 answer을 리턴하며 종료한다.

 

stoi 의 한계

if(!stoi(answer)) answer = "0"; return answer;

마지막 부분을 위와 같이 작성하고 제출했을 때는 11번 테스트케이스만 맞고, 나머지 테스트는 전부 틀린거로 나왔다.

분명 '실행'으로 테스트케이스 돌렸을 때는 맞아서 제출을 했는데 틀려서 당황..

알고보니 stoi에는 문자열길이에 제한이 있다.

"0"이 아닌 다른 문자를 11개 이상(10개 초과) 포함하는 문자열에 대해서는 stoi를 통해 int형으로 변환하지 못하고 오류를 발생시킨다.

이러한 문제점을 찾았고, 해결하기 위해서 아래 코드에 작성된 것처럼 answer문자열의 첫 번째 문자가 0인지 판단해서 답을 출력하는 코드로 바꿔서 정답을 맞을 수 있었다.

 

코드