프로그래머스 44일차 - 가장 큰 수

큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

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

 

해설

처음에 모든 요소의 순열을 구해서 리스트에 담고

리스트의 요소를 돌려서 해당 요소를 문자열로 바꿔서 하나로 합친다음 다시 리스트에 담아서

가장 큰 수를 문자열로 바꿔서 리턴했다.

 

근데 이게 시간초과가 떠버렸다.

그래서 다른사람 풀이를 봤다.

이 문제는 엄청 쉬운 대신에 시간초과라는 함정을 넣어둔 것이다.

그래서 순열을 사용 못하고 아스키코드의 문자열 비교를 사용해야한다.

 

 

문자열 길이를 3배로 늘린 후에 비교하는 방식 ( 원소가 1000이하이므로 ) - 핵심 아이디어 

• 문자열에서의 대소비교와 일반숫자의 대소비교가 다르기때문에 가능한 코드
• 예를들어 '121'과 '12'의 경우 12가 더 먼저와야 큰수를 만들 수 있는데,  문자열 비교에서 '121121121'과 '121212'가 더 큰수이기 때문이다.

이걸 알면 더 쉬워진다.

문자열의 길이를 곱해준다음 단순하게 비교해준다면 알아서 더 큰수를 리턴한다는 뜻이기 때문이다.

그래서 1000 이하이므로 3을 곱해서 문자열의 길이를 맞춰주는 것이다.

문자열이 3자리 999나 6자리 393939를 비교해도 아스키코드는 정수와 비교방식이 다르기 때문에 999가 더 크다고 sort해준다.

 

sort로 리스트로 만들어서 문자열을합쳐서 리턴한다.

 

그럼 마지막에 str(int())작업은 왜하느냐 하면

위처럼 하면 테스트 11번에 테스트 케이스가 [0,0,0]이라 000을 리턴하기 때문에 이는 0으로 리턴하게 만들기 위함이다.

 

그래서str(int(''.join(numbers)))처럼 리턴한다.