[프로그래머스] 코딩테스트 연습 : 가장 큰 수 - PYTHON[파이썬]

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

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

---

⊙ 문제

⊙ 제한사항

⊙ 입출력 예

 

---

 

⊙ 문제 접근 과정

 

총 4번의 도전.

 

- 첫 번째 풀이 -

조합 (시간 초과)

from itertools import permutations

def solution(numbers):
    comNumbers = list(permutations(numbers, len(numbers)))
    
    comNumberList = []
    
    for c in comNumbers:
        temp=list(map(str, c))
        comNumberList.append(''.join(temp))
        
    return str(max(comNumberList))

첫 번째는 조합을 사용해풀어봤어요.

numbers에 들어오는 모든 값들을 조합하여 그중 가장 큰 값을 반환한다! 가 제 생각이었습니다.

그렇지만 실패했죠.

 

제한 사항을 볼까요?

 

numbers의 길이는 100,000개일 수도 있어요.

100,000개를 순서를 고려하여 조합하면 과연... 몇 개일까요? ㅎㅎ 무섭네요...

 

첫 번째 풀이 결론 : 테스트 케이스는 길이가 짧아서 성공했지만 길이가 긴 것은 시간 초과

 

---

 

- 두 번째 풀이 -

문자열 정렬 (부분 통과)

def solution(numbers):
    strNumbers = list(map(str, numbers))
    strNumbers.sort(reverse=True)
    return ''.join(strNumbers)

이 방법을 첫 번째로 생각했어야 했는데 아쉽네요.

파이썬 문자열을 정렬하면 아스키코드 값을 기준으로 정렬해요.

 

첫 번째 문자가 가장 큰 순서로 붙여줘야 가장 큰 수가 만들어지니 이 방법을 생각했어요.

 

그렇지만 테스트 케이스 2번에서 틀렸습니다.

30과 3을 비교할 때, 30을 더 크게 비교하기 때문이었어요.

 

그렇게 되면 어떻게 되냐? "30" + "3" = "303"이 나옵니다.

우리가 원하는 값은 "3" + "30" = "330"이죠.

303보다 330이 더 크니까요.

 

두 번째 풀이 결론 : 글자 수가 다르면 크기 비교가 제대로 이루어지지 않음

 

---

 

- 세 번째 풀이 -

문자열 정렬 - 글자수 맞춰주기 (통과 - 스페셜 케이스 제외)

def solution(numbers):
    strNumbers = list(map(str, numbers))
    strNumbers.sort(key=lambda x: x*3, reverse=True)
    return ''.join(strNumbers)

 

결국 구글의 힘을 빌렸습니다.

배열을 곱해주어서 정렬을 하면 두 번째 풀이의 문제를 해결할 수 있었어요.

 

3을 곱한 이유는 원소는 1,000 이하이기 때문입니다. ㅎㅎ

출처: https://huidea.tistory.com/4

3을 곱하면 위 사진과 같은 일이 벌어집니다.

 

따라서 두 번째에서 언급한 문제.

그렇게 되면 어떻게 되냐? "30" + "3" = "303"이 나옵니다.
우리가 원하는 값은 "3" + "30" = "330"이죠.
303보다 330이 더 크니까요.

[30, 3]에서 [3, 30]으로 정렬이 됩니다.

 

이제 문제를 다 해결한 것 같았어요.

ㅋㅋㅋ 근데 하나가 통과가 안 됩니다. 스페셜 케이스가 있던 것이죠.

 

세 번째 풀이 결론 : 히든 케이스 고려 X

 

---

 

- 마지막 풀이 -

문자열 정렬 - 글자 수 맞춰주기 [스페셜 케이스 고려] (통과)

def ZeroCase(hidden):
    if len(hidden) == hidden.count(0):
        return True
    return False

def solution(numbers):
    if ZeroCase(numbers):
        return "0"
    
    strNumbers = list(map(str, numbers))
    strNumbers.sort(key=lambda x: x*3, reverse=True)
    return ''.join(strNumbers)

 

모든 수가 0으로 들어오면 값이 이상하게 나왔어요.

 

예를 들어 numbers가 [0, 0, 0]으로 주어지면 return을 "000"으로 합니다.

이 경우를 따로 빼주었어요. ZeroCase라는 함수를 만들어서요.

 

ZeroCase는 모든 원소가 0이면 True를 return 해요.

그러면 첫 번째 조건문에서 early return, 함수가 바로 종료됩니다.

 

 

*히든 케이스 모듈화 안 한 풀이

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

사실 이렇게 빼면 코드 줄이 더 짧아져요.

int로 변환 후 str로 변환해주면, 00은 0으로 바뀌죠?

 

그렇지만 저는 위 코드는 가독성이 좋지 않다고 생각하여, 히든 케이스를 따로 모듈화 해주었어요.

 

고수분들과 다르게 저 같은 초보는 위 코드를 보면, 왜 str -> int -> str을 해줬지?

그냥 str로 해야겠다~라고 생각하지 히든 케이스를 고려하여 코드를 짰구나~라고 생각하지 못해서요 ㅠㅠ

 

 

---

 

⊙ 문제 풀이

 

def ZeroCase(hidden):
    if len(hidden) == hidden.count(0):
        return True
    return False

def solution(numbers):
    if ZeroCase(numbers):
        return "0"
    
    strNumbers = list(map(str, numbers))
    strNumbers.sort(key=lambda x: x*3, reverse=True)
    return ''.join(strNumbers)

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!