42746: 가장 큰 수[정렬]

Link : programmers.co.kr/learn/courses/30/lessons/42746

---

1. 문제

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

 

---

2. 문제의 조건

• 1 <= length <= 100,000
• 0 <= number <= 1,000
• 문자열로 return

 

---

3. 문제 접근

• 시간 복잡도
  
  만약 완전탐색으로 진행을 하게되면 O(N!)이므로 엄청나게 시간초과가 생깁니다. 완전 탐색이 아닌 문제에서 주어진 정렬로 해결해야합니다.

 

• 아이디어
  
  처음엔 감도 못잡아서 검색을 좀 많이 하였습니다.
  그 결과 "문자열의 길이를 맞추자"라는 큰 힌트를 얻게 되었습니다.
  제일 중요한 케이스인 [40, 404]를 보며 4글자로 4000 4040으로 맞추게되면 40440이 되지만, 
  10 100이 되어버리면 같은 값이 되기떄문에 해결할 수 없었습니다. 그래서 문자열을 반복하자는 생각을 하였습니다.
  4040 4044의 경우도 해결되고 10 100도 1010 1001이 되어서 10100으로 해결되었습니다.
  하지만, 100 1001의 경우 또 같은 값이 되어서 곤란하였습니다. 그래서 4글자가 아닌 5글자로 맞추었습니다. number의 길이는 총 4자리 0~9999까지 이므로 5자리를 넘어 설 일이 없어서 100, 1001 같은경우도 10010과 10011로 해결되여 1001100를 표시할 수 있게 되었습니다.
  
  범위를 보면 0도 포함힙니다. [0, 0, 0]과 같은 0만 있을경우 000 으로 표시하는데 이를 000으로 반환하면 오답이 됩니다. 그래서 int로 변환 후 그 값을 다시 str로 변환 해주어야 합니다.

 

---

4. 풀이 방법

• 모든 숫자를 문자열로 변환합니다.
• 모든 길이를 반복하며 5글자로 맞추어줍니다.
• lambda식으로 real_value이아닌 5글자로 맞춘 value에 대해서 정렬을 내림차순으로 수행합니다.
• 값을 숫자 -> 문자로 변경하여 다시 출력합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/118

 

---

 

cjw.git@gmail.com