[programmers python] 42746 가장 큰 수

 

programmers.co.kr/learn/courses/30/lessons/42746?language=python3

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

 

 

<problem>

 

 

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

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

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

 

 

<constraint>

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

 

---

 

<example>

 

---

 

<solution ①> 

 

입력받은 배열 numbers의 모든 값을 str으로 변환하고, 다시 list 형태로 만들어줌

  : 값 비교 위해 이 방법 선택

    : 연결하였을 때 가장 큰 수가 되기 위해서는 앞쪽에 큰 수가 계속해서 나와야하기 때문에 앞부터 비교하는 문자열 비교 방법 선택

 

그 다음 정렬 방법을 고민하는 데에 오랜 시간 소요됨

for문을 통해 비교할지 하나씩 비교하여 정렬할까 생각해보기도 하고,   그렇다면, 예를 들어 90 91 이렇게 나왔을때, 다음 수는 또 for문을 돌려야 하기 때문에 시간초과가 될 것으로 판단됨.

그냥 정렬을 하게 되면, 우리가 원하는 결과가 아니라 예를 들어 3과 30을 비교하면 당연히 30이 더 크다고 나올 것이기 때문에, 

  이 부분이 안되는 이유는 330과 303 연결 시 330이 더 큰 것 확인 가능

고민하다 결국 방법을 찾지 못해 다른 풀이를 찾아보다 참고하게 됨

 

<참고링크>

sinsomi.tistory.com/entry/프로그래머스-Python-가장-큰-수-초코더

 

lambda 함수를 사용하여 정렬 수행

  : 제한조건을 보면, 각 수는 1000이하이므로 각 수를 3번씩 반복하여 최소 3자리 수를 만들어주어 비교 수행하여 정렬

  sort(key = lambda x: x*3, reverse=True)

 

마지막으로 문자열을 연결하여 출력해주도록 join함수 사용하여 작성

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

---

 

ⓣ ⓔ ⓢ ⓣ

 

---

테스트는 통과 했지만, 정확성 테스트에서는 실패 발생

생각해보니, 모두 0이 들어온 경우는 현재 str으로 이루어진 배열이므로 

예를 들어, ['0', '0', '0']라면, 000으로 출력될 것이기 때문에 틀린 것 파악

 

따라서 다시 numbers 배열을 int형으로 변환하여 연결한 후 다시 출력을 위해 str타입으로 변환시켜줌

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

---

 

ⓣ ⓔ ⓢ ⓣ

 

---

 

---

 

다른 코드를 참고해보았을 때, 

이 방법이 가장 적합하다고 생각되어 final code로 제출

 

ⓕ ⓘ ⓝ ⓐ ⓛ    ⓒ ⓞ ⓓ ⓔ