[코테 연습] 가장 큰수

programmers.co.kr/learn/courses/30/lessons/42746#

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

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

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

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

 

---

 

1차 시도.. 

[모든 자리의 수를 더한 값, 자리수, 원래값] 으로 tuple을 만들어 sort 했다.

여기서 자리수를 넣은이유가 3과 30같은 경우인데 이 둘은 더해도 3, 30으로 해서 330이 더 큰데 자칫 303이 되버려서였다..

 

 

위와 같이 코딩을 진행하는 경우 (34, 5) 가 문제가 발생한다. 3+4 = 7 이고 5보다 크므로 534가 아니라 345가 만들어진다. 

자릿수를 맞춰야하는가?

 

• numbers의 원소는 0 이상 1,000 이하입니다.

위와 같은 조건이 있다.. 음 그럼 4자리로 모두 맞춰도 되지 않을까.. 

 

2차시도.. 자리 수를 맞춰주고 진행.. 여전히 통과하지 못한다. 

 

 

 

질문 목록을 보니 나와 같이 1~6번을 틀린분들이 많이계셨다.

programmers.co.kr/questions/12763

프로그래머스

이 분의 반례처럼 내 코드는 (40,403)의 입력값의 결과로 "40340"을 return하는 것을 확인할 수 있었다.

자리수를 맞추면 (4000,4030) 이기때문에 4030이 더 큰값으로 여겨져 40340이 결과가 된다. 

 

---

정답을 보다

오랜 시간이 흐른 뒤.. 결국 답을 봤다. 그냥 숫자를 3번 곱해서 비교하면되는 것이였다. 

그러면 위에 문제인

- 404040 

- 403403403

이런식으로 해서 문자열 비교이기때문에 자리별로 비교하므로 40이 더 큰 값이 된다. 

혹시나 해서 2번 곱했는데 그건 틀린다.1~6번까지 .. 아무튼 오늘 문자열 비교에 아주 획기적인 아이디어에 대해서 얻을 수 있었다. 

 

---

다른 사람의 코드

다른 사람의 코드도 발견했다.. 어머나.. 저렇게 한번에 곱해서 sort하는 방법이 있었다니.