[파이썬] 프로그래머스 커뮤러닝 1주차 큰 수 만들기

 

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

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

 

 

풀이계획

 - 탐욕법을 사용하여 답을 찾아내는 방법이 있음 -> 두개의 인자가 주어질때, 큰 숫자일때 문자형식으로 k숫자로 주어지게 된다.

 - number라는 숫자에서 k는 1이상 number를 자연수 미만으로 주어지게 됬다.

  - 가장 큰수를 뽑는 방법은 4개의 숫자중에서 가장 큰 숫자 9와 4를 뽑아서 94를 만드는게 가장 큰 숫자일 것이다.

  - 가장 큰 수를 뽑는 방법은 가장 작은 숫자에서 차례대로 뺀 1,2,1을 빼고 나머지 숫자를 3234를 만든다.

   -  3번째의 경우, 4개를 빼서 수를 어떤 것을 빼면 가장 큰 숫자가 되는지 알 수 있다. 이때, 맨 마지막에 1이 있지만, 이것을 빼는 것보단 앞에 있는 2를 빼는게 더큰 숫자가 될것이다. 이를 순차적인 알고리즘을 쓴다면 알 수 있을 것이다.

 

  - 앞 자리에서부터 하나씩 골라서 담되, 지금 담으려는 것보다 작은 것들은 도로 뺀다, 단 뺄 수 있는 수효에 도달 할 때 까지만 진행한다.

  - 큰 수가 앞자리에, 작은 수가 뒷 자리에 놓이도록 하지만 뺄 수 있는 숫자(k)는 제약이 있다.

  -  뺄 수 있을때 까지 작은것들은 빼고 뺄 수 있는 수를 다 빼고(위 문제인 4개) 다빼면 나머지는 그냥 붙이게 된다면 그게 가장 큰 수가 될 것이다.

   - 주의해야 될 것이 있다. 만약에 큰수가 앞으로 나왔을 경우에는 앞에서 빼는게 아니라, 뒤에있는 작은 숫자를 빼서 최대값으로 만들어 주는 형식으로 알고리즘을 구성해야 한다.

  - 알고리즘

    1) 주어진 숫자(number)로 부터 하나씩 꺼내어 모으되 이미 모아둔 것 중 작은것들은 빼낸다. 같거나 작은거만 등장하게 되므로 이를 k개 만큼만 빼면 된다.

    2) 이렇게 모은 숫자들은 자릿수를 맞추어 반환해야 한다. 아직 뺄 갯수를 채우지 못할 경우, 자릿수를 어떻게 계산해야 하는지 고민해야 한다.

  - 알고리즘 복잡도

    1) 가장 무식한 방법은 모든 경우의 수를 모두 나열하고 비교하는 방식은 조합의 수가 너무 많아져서 계산이 복잡해지게 됨

    2) 매 수를 더할때 하나씩 더할때 뺄거면 빼고 더할 때는 더해야 되니 O(n)으로 비례하게 되어 linear time 알고리즘이 되게 된다.

  - 앞자리의 수를 결정할때, 먼저나온 작은 것을 빼는게 그 뒤의 숫자에서 가장 빼고 싶은 숫자를 빼는것이 가장 최적의 해를 구하는데 영향을 주지 않는다. 이 알고리즘이 적용이 가능하다.

 

직접풀이

 -> 이문제는 풀지 못했다. 구글링으로 답을 봐도 잘 이해가지 않아 바로 해답으로 넘어간다.

 

해결풀이

def solution(number, k):
    collected = []
    for i, num in enumerate(number):
        while len(collected) > 0 and collected[-1] < num and k>0:
            collected.pop()
            k -= 1
        if k== 0:
            collected += list(number[i:])
            break

        collected.append(num)

    collected = collected[:-k] if k > 0 else collected
    answer = "".join(collected)
    return answer

 - 리스트는 imutable하고 문자열은 mutable 함으로 리스트에 값을 모으는게 효율이 좋음 따라서 문자열에 모음

 - for 문을 통해 number 에서 하나식 숫자를 꺼내며 , enumerate를 통해 인덱스와 숫자를 나타날 수 있도록 한다.

 

 - while 문에서 collectd에 원소가 1개 이상 있고, 마지막 원소가 지금 담으려는 글자보다 작고, k가 0보다 크면 지금의 글자가 마지막것보다 큰 숫자이므로 collected에서 pop을 이용해 숫자를 빼게 되고, k도 숫자를 1개씩 빼게 된다.

  1) 맨 마지막 글자만 비교해도 괜찮을까? 그렇다, 지금까지 쌓인 숫자들은 앞의 숫자보다 작거나 같기 때문에 지금

   2) collectd의 마지막 원소는 한글자의 문자열이다. 이를 정수로 변환하지 않아도 될까? 괜찮다 파이썬에서 숫자의 문자열 한자리 일때는 그 숫자크기가 같다. 2자리일때는 달라지므로 그때는 안됨

 

 - 그렇게 while문이 돌아가고 k가 0이 됬을때, number의 남은 숫자들을 인덱스를 통해서 접근하고 남은 숫자들을 collected에 붙여주게 된다. (이것을 위해서 i라는 인덱스를 만든 것임) 그리고 break로 while을 끝냄

 

 - if문이 없어도 while문의 k>0 조건에 의해 거짓이 되기 때문에 계속해서 한글자씩 붙이게 될것임 하지만 if문을 통해서 해야할 일을 다 했구나 해서 특수한 상황에서 코드의 효율을 높일 수 있다.

 

 - 이 조건문이 끝나면 collectd의 끝자리에 num을 붙이게 된다. 

 - k가 0보다 크면 collected 에서 -k를 이용해서 k개를 뺀 나머지 수들을 빼게 되고 아니면 그냥 collected를 표현하게 한다.

 - 마지막으로 collected의 숫자들을 .join을 통해 붙여주면 된다.