[#알고리듬] 큰 수 만들기

RookieAND·2022년 10월 7일

그리디 스택 코테 프로그래머스

BaekJoon

목록 보기

31/42

❓ Question

https://school.programmers.co.kr/learn/courses/30/lessons/42883

본 문제는 3학년 2학기 알고리즘 소모임 알고리듬 활동으로 풀이한 문제입니다.

📖 Before Start

스택을 활용하여 그리디 알고리즘을 구현해야 하는 문제였다.

이번 문제는 스택을 활용하여 그리디 알고리즘을 구현해야 하는 문제였다.
오랜만에 코테 문제를 푸니 감각이 많이 무뎌졌다. 공모전에 너무 몰두해서 그런가..

✒️ Design Algorithm

스택을 응용하면서, 어떤 수를 제거할지 순차적으로 탐색해나간다.

숫자로 이루어진 문자열 number 와 제거해야 할 숫자의 수량인 k 가 주어진다.
이때, number 내 숫자들 중에서 k 개를 제거했을 경우 가장 큰 수가 나와야 한다.
따라서 나는 앞의 세 숫자를 기준으로 어떤 수를 제거할지 정하는 방식을 생각했다.

💻 Making Own Code

❌ Wrong Code

def solution(number, k):
    if len(number) == 2:
        return max(int(number[0]), int(number[1]))

    start = 0
    while k > 0:
        first, second, third = map(int, number[start:start + 3])
        if first < second:
            number, start = number[:start] + number[start + 1:], 0
            k -= 1
            continue
        if second < third:
            number, start = number[:start + 1] + number[start + 2:], 0
            k -= 1
            continue
        start += 2
    return number

코드를 쓰면서도 이건 아닌데... 라는 생각이 든다면 정답이다. 오답이었다.

나는 처음 세 숫자를 기준으로 아래와 같은 소거 규칙을 정했다.

첫 번째 숫자가 두 번째 숫자보다 작다면 무조건 첫번째 수를 없앤다.
1번이 아닐 경우, 두 번째 숫자가 세 번째 숫자보다 작다면 두번째 수를 없앤다.
2번이 아닐 경우, 세 수는 내림차순 이므로 탐색 기준 인덱스를 2만큼 늘린다.

하지만 해당 규칙은 모든 수가 내림차순 으로 이루어진 경우 어김없이 오류를 뿜었다.

✅ Correct Code

def solution(number, k):
    stack = []
    for num in number:
        while stack and stack[-1] < num and k > 0:
            stack.pop()
            k -= 1
        stack.append(num)
    return "".join(stack[:len(stack) - k])

역시 스택만큼 활용도가 높은 알고리즘이 없다. 스택 만만세.

number 문자열에서 걸러낸 숫자를 담을 리스트인 stack 을 함수 내부에 선언한다.
이후 문자열을 순차적으로 탐색하여 아래와 같은 규칙을 통해 stack 에 값을 추가한다.

만약 stack 이 비어있다면 무조건 해당 값을 stack 에 추가해야 한다.
stack 에 값이 있다면, 현재 숫자와 가장 마지막으로 저장된 값을 비교한다.
2-1. 가장 마지막으로 저장된 값이 현재 숫자보다 클 때까지 stack 에서 값을 제거한다.
2-2. 만약 k가 0일 경우 더 이상 값을 제거할 수 없으므로, 반복을 중단해야 한다.
2-3. 만약 stack 이 비게 된다면 값을 제거할 수 없으므로, 반복을 중단해야 한다.

위와 같이 규칙을 설계하고 문제를 풀었더니, 곧바로 정답 처리를 내려주셨다 (...)
진짜 스택은 어디에서든 도입할 수 있는 알고리즘인지라 더더욱 신경써야겠다.