파이썬_고득점키트_문제풀이(4)_탐욕법

4. 탐욕법 대표 문제 풀이 : 가장 큰 수

큰 수 만들기
어떤 숫자에서 k개의 수를 제거했을 때, 얻을 수 있는 가장 큰 숫자를 구하려고 한다
숫자 1924에서 수 두 개를 제거하면 [19,12,14,92,94,24]를 만들 수 있다. 이 중 가장 큰 숫자는 94이다.
문자열 형식으로 수가 주어진다. number. k는 제거할 수의 개수를 말한다.
제한조건
number는 1자리 이상, 1,000,000자리 이하인 숫자다
k는 1이상 numbers의 자리수 미만인 자연수다
입출력 예제

큰 수 만들기 - 원칙

앞 자리에 큰 수가 오는 것이 전체를 크게 만든다.
- 따라서 큰 것을 우선해서 앞에서 부터 골라서 담고 싶다.

예제 살펴보기(1)

1924 -> k:2/ 1과 2를 빼는 것.
1231234 -> k:3 / 12 1빼야한다.
3177252841 -> 4개를 빼라. 4122를 빼야 한다.
앞에 작은 것들이 나오면 배는데, 맨 뒤의 1은 빼지 않는다. 작은 것을 빼되, 앞에서 빼는게 이득이 된다.
뺄 수 있는 수의 개수가 네개 밖에 안되기 때문에, 앞자리에 큰 걸 두기 위해서, 앞 쪽의 작은 수를 빼내고, 775841을 남기는게 답이다.

큰 수 만들기 - 방법

앞 자리에서부터 하나씩 골라서 담되,
지금 담으려는 것보다 작은 것들은 도로 뺀다.
단, 뺄 수있는 수효에 도달할 때까지만
큰 수가 앞 자리에, 작은 수가 뒷 자리에 놓이도록
(제약조건) 뺄 수 있는 수의 개수
예제 다시 살펴보기
number = “4177252841”, k = 4
4 1 을 담는다. 다음 7이 나왔는데, 우선 1을 빼고, 하나뺐다는 기록을 한다.
4도 빼고, 7이 4봐 크니까 4도 빼고, 하나 뺐다는 기록을 한다.
7 이 들어와있고, 다음 7을 이어 붙인 뒤,2를 붙인다.
5가 나왔는데, 이 때는 5가 그 앞 자리에 들어갔던 2보다 크고, 아직 뺄 수 있는 갯수가 남아 있으므로 2를 빼고 5를 당겨 붙인다.
5는 7보다 작으므로, 더이상 볼 필요가 없다.
2를 붙인다.
그 다음 8이 등장한다. 8이 2를 쓰는 것보다 앞 쪽에 쓰기 유리하기에,7758이 된다.
여기서 5도 빼고 싶지만, 뺄 수 있는 개수를 다 소모하였기 때문에 더 뺄 수 없고, 나머지 4, 1을 갖다 붙이면 답이 된다.

주의할 점

98765의 경우, k는 2로 주어져 있어서 2개를 뺄 수 있지만,
98765가 이미 큰거대로 모아져있기 때문에, 다 모아놓고 보면 ,98765가 된다.
이 경우는 뒤에꺼 2개를 빼고 987을 출력해야 한다.

알고리즘 설계 -> 구현

주어진 숫자 (number)로 부터 하나씩 꺼내어 모으되
- 이 때 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼낸다.
- 이것은 어디서 어떻게 살펴보아야 ?
이렇게 모은 숫자들을 자릿수 맞추어 반환한다.
- 아직 뺄 개수 k를 다 채우지 못한 경우
- 자릿수는 어떻게 계산하는가 ?

알고리즘의 복잡도

가장 단순(무식?)한 방법은 어떤 것일까?
- 가능한 모든 조합을 나열하고, 그 중에 제일 큰 것을 고르는거다.
우리가 설계한 알고리즘의 복잡도는 ?
- O(n^2)이 아니라 O(n)이다.
- 모든 자리의 수는 넘버 자리수가 n일 때, 각각 한개 한개씩은 더해지는게 1번이고, 빠지는 것도 기껏해야 한번이다.
- 한번 들어갔다 한번 나올 수만 있기 때문에. n의 2배에 가까울 수 있지만, 어쨌든 주어진 수의 길이에 비례하는 알고리즘이다.

탐욕법

이 문제의 분류가 탐욕법이 통하는 문제이기 때문에 이 방법이 사용가능
앞 단계에서의 선택(앞 자리에 큰수!)이 이후 단계에서의 동작에 의한 해(solution)의 최적성(optimality)에 영향을 주지 않음

코딩 테스트 연습

def solution(number, k):
    collected = []  # 숫자를 모아서 큰 수를 만들 때 쓰일 배열
    # 문자열에도 모을 수 있지만 문자열은 immutable(값이 변하지 않는)특성을 가지기에 코드 효율은 리스트(mutable)다 더 좋다
    # call by value , call by reference와 동일한 개념
    for i, num in enumerate(number):
        # k개 만큼의 숫자를 빼냈을 때, i의 인덱스를 기억하기 위해서 i를 사용
        while len(collected) > 0 and collected[-1] < num and k > 0:
            # 1. 맨 마지막 문자만 비교를 하면 될까? -> 그렇다. 지금까지 원칙을 지켜서 쌓아 왔다면 지금까지 쌓인 숫자들은 내림차순으로 되어있다.
            # 2. collected의 마지막 원소는 한 문자로 이루어진 문자열이다. num 또한 한 글자 짜리 문자열이다. 이걸 정수로 변환하지 않고,
            # 두개의 문자열에 대해서 대소관계를 이용해도 괜찮은가? -> 괜찮다. 알파벳 순서에 따르면 0은 1보다 작고, 3은 2보다 크고, 수의 크기 대소관계와 같다.
            # ※ 길이가 2 이상이라면, 사전에 나타난 숫자가 되겠지만, 지금은 한글자 짜리기 때문에 정수 변환이 필요없다.
            collected.pop()  # 리스트이 맨 끝에 있는 원소 하나를 없앤다.
            k -= 1
        if k == 0:
            collected += list(number[i:])
            break
        collected.append(num)
    collected = collected[:-k] if k > 0 else collected
    # k가 0 이면 빈 리스트가 되기 때문에 if를 이용해서 조건을 걸어준다.
    answer = ''.join(collected)
    return answer

n에 비례하는 linear time
3행에서 시작하는 for 순환문이 solution 함수의 복잡도를 결정하는 가장 바깥의 loop이다.
number라는 문자열에서 한문자씩 꺼내는 동작을 한다.
그 안에 4행에서 시작하는 while 순환문이 또 들어있다. 이중 순환문
이 while을 얼만큼 실행되는냐에 따라 복잡도가 결정된다.
n^2 혹은 n^2/2에 비례한다고 잘못 생각할 수도 있지만, 이 알고리즘은 number라는 문자열에서 한 글자씩 꺼냈을 때, collected에 추가되는 횟수도 한번, 추가되었다고 도로 빠져나왔다고 해도 기껏해야 한번 나가기 때문에,
전체 솔루션 함수 전체를 이루는 for 순환문은 반복하는 횟수는, 그에 따른 알고리즘의 복잡도는 O(N)이 된다.
앞에서 행위를 결정하는 것이, 끝났을 때의 최적성에 영향을 미치지 않음이 보장되는 경우.
이 문제에서는 그게 왜 보장되냐하면, 큰 수를 앞에 놓는 것이 무조건 유리하기 때문이다.
이러한 경우에는, 지금 본 것처럼 모든 조합을 다 조사하지 않고도, 한 단계 단계 마다, 그리디 하게 풀 수 있다.

참고자료 [프로그래머스]https://programmers.co.kr/learn/courses/9877