[python] 프로그래머스 - 가장 큰 수

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42746

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

 

아니 이거 혹시 정렬 문제가 아니라 테스트 케이스 다 잡아내는게 목적인 문젠가요

아니 그것도 실력이긴 한데 너무 어려웡

 

 

첫 번째 풀이 : 망함ㅋ

 

def solution(numbers):
    #정렬 기준을 잡는 문제
    #어떻게 해야 최댓값이 나올까?
    #최댓값이 나오려면 글자 자체가 앞이 큰 수부터 정렬하면 된다.
    #3 34 30이 문제.
    #전부 다 마지막 글자로 총 4글자로 padding으로 채우고 정렬
    #채운 값과 원래 값을 동시에 저장하면 해결?
    #key값을 바꿀거냐 value 값을 바꿀거냐
    #key에 원래 값, value에 채운 값
    
    numbers = list(map(str, numbers))
    number_dict = []
    
    for number in numbers:
        number_dict.append([number, number])
    
    for index in range(len(numbers)):
        while len(number_dict[index][1]) < 4 :
            number_dict[index][1] += number_dict[index][1][-1]
            
    number_dict = sorted(number_dict, key=lambda x: (x[1], len(x[0]) if x[1][-1] < x[1][-2] else -len(x[0]) or null), reverse=True)
    
    print(number_dict)
        
    answer = ''
    for item in number_dict:
        answer += item[0]
    
    return answer

 

일단 고군분투의 흔적이다.

아이디어 싸움 같은데 나는 그런 거에 약하기 때문에 하ㅏㅎ....

처음보고 아 뭐야 글자로 비교하면 되겠네 하핳 하고 쉬울 줄 알았는데 너무 어렵다.......

로직은 아니고 나의 풀이 흐름은 다음과 같다.

 

● 글자가 큰 순으로 오면 되므로 문자열로 바꾼 후 역사전식으로 정렬한다.

       => 문제 3 34 30의 경우 34 3 30으로 배열되어야하나 34 30 3으로 배열됨.

● [key, value] 형태의 리스트로 만들어서 value의 마지막 글자를 추가해 4글자로 만들어 value를 기준으로 역사전식 정렬

     입력값의 범위가 1이상 1000이하기 때문에 4글자로 만들면 3444 3333 3000으로 34 3 30로 배열됨.

       => 4글자로 강제로 통일하였기 때문에 [1, 10, 100, 1000]과 같은 경우 구분이 안됨.

● 1, 10, 100, 1000은 1 10 100 1000으로 배열되어야하고, 12, 122의 경우는 122, 12로 배열되어야함.

     문제는 문자열의 패턴이 ab, abb와 같은 패턴으로 이루어져서 발생한다.

     이를 해결하기 위해 두 번째 정렬 조건으로 a>b일때와 a<b일 때를 구분하여

     a>b라면 길이가 짧은 것이 먼저 오도록하고, a<b라면 길이가 긴 것이 먼저 오도록 정렬해주면 되겠다.

       => 이게 말이냐.

 

진짜 주식 가격부터 너네 나한테 왜 이러니.

 

두 번째 풀이 : 참고하기 슬쩍, 물론 실패

 

def solution(numbers):
    numbers = list(map(str, numbers))
    number_dict = []
    
    for number in numbers:
        number_dict.append([number, number])
    
    for index in range(len(numbers)):
        while len(number_dict[index][1]) < 4 :
            number_dict[index][1] += number_dict[index][1][-1]
            
    number_dict = sorted(number_dict, key=lambda x: (x[1], -len(x[0]) if len(x[0])  > 1 and x[0][0] > x[0][1] else len(x[0])), reverse=True)
        
    answer = ''
    for item in number_dict:
        answer += item[0]
    
    return answer

 

참고하기를 슬쩍 봤더니 일단 4글자로 통일하는 것까지는 방향을 잘 잡은 듯해서(놀라워) 그 다음을 안보고 다시 나왔다.

그러면 지금 문제는 

 

● 1, 10, 100, 1000은 1 10 100 1000으로 배열되어야하고, 12, 122의 경우는 122, 12로 배열되어야함.

     문제는 문자열의 패턴이 ab, abb와 같은 패턴으로 이루어져서 발생한다.

     이를 해결하기 위해 두 번째 정렬 조건으로 a>b일때와 a<b일 때를 구분하여

     a>b라면 key의 길이가 짧은 것이 먼저 오도록하고, a<b라면 key의 길이가 긴 것이 먼저 오도록 정렬해주면 되겠다.

 

위에서 꼬였던 생각을 다시 정리하면서 코드를 정리하였다. 그래서 했는데도!

[6, 10, 2], [3, 30, 34, 5, 9], [1, 1000, 10, 100], [12, 122], [21, 211]와 같은 테스트 케이스를 다 통과했는데도!

돌리니까 실패했다 ㅎ 여기서 포기함 ㅋ

 

세 번째 풀이 : 아니 이게 뭐야

 

def solution(numbers):
    numbers = list(map(str, numbers))
    number_dict = []
    
    for number in numbers:
        number_dict.append([number, number])
    
    for index in range(len(numbers)):
        count = 0
        while len(number_dict[index][1]) < 4 :
            number_dict[index][1] += number_dict[index][1][count]
            count += 1
            
    number_dict.sort(key=lambda x: x[1], reverse=True)
            
    answer = ''
    for item in number_dict:
        answer += item[0]
    
    return str(int(answer))

 

살짝 전화번호 목록이 떠오르는 상황인데 큰 방향은 맞았는데 방향의 세부사항이 틀린......그런........하........

일단 4글자로 통일한다는 방향까지는 잘 갔는데 거기서 정답을 보니

마지막 글자를 계속 넣어서 4글자를 만드는 것이 아닌 전체 글자를 반복해서 4글자를 만들더라.

그렇게 만들면 10, 100, 1000은 1010, 1001, 1000이 되어 101001000이 되고

12, 122는 1212, 1221이 되어 12212가 된다.

나는 이게 왜 되는지 아직도 이해가 안돼. 그냥 결과론적으로 이렇게 해보니까 되더라 아닌가?

라는 생각이 들어서 한 번 정리를 해보았다.

 

만약 ab, abb라면

 

ab    : abababb : abba

 

즉, ab와 ba로 대소비교를 하게 되는데 a>b라면 ab>ba고 역정렬이니깐 abab abba로 정렬되어 ababb가 되고

a<b라면ba>ab고 abba abab로 정렬되어서 abbab가 되는 것이다.

정말........놀라워........하............

---

 

시간 복잡도

 

for문이 다 O(N)인데 sort 함수를 사용해서 O(NlogN)이다.

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

아이디어 싸움인 문제다.

이런 문제는 머리가 디게 좋거나 머리가 엄청 좋거나 문제를 많이 풀어본 경우가 아니면 쉽게 떠올려서 풀긴 힘든 듯.

4글자까지 접근했다는거에 만족한다. 하........ㅋ