[프로그래머스 - Python] 큰 수 만들기 (그리디)

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

프로그래머스

 

코드

def solution(number, k):
    numbers = number
    
    idx = 0
    while idx < len(numbers) - 1 and k > 0:
        if numbers[idx] < numbers[idx+1]:
            numbers = numbers[:idx] + numbers[idx+1:]
            k -= 1
            if idx > 0:
                idx -= 2
            else:
                idx -= 1
        idx += 1
    
    if k >0:
        numbers = numbers[:len(numbers)-k]
    
    return numbers

 

처음에는 작은 수부터 큰 수 순서로 제거하면 되겠다고 생각했다.

하지만 그렇게 한다면 입출력 예시 3번에서 마지막 1이 지워지고 정답값과 다름을 깨달았다.

입출력 예시 3번에서 중간의 2들이 맨 뒤의 1보다 우선적으로 제거되는 이유가 무엇일지 고민해봤다.

 

제거되는 숫자들은 주어진 문자열에서 바로 뒤의 숫자보다 작은 경우에 제거됨을 발견했고

해당 아이디어로 구현을 하였다.

전체 문자열을 다 돌고도 k만큼의 횟수를 채우지 못했다면

뒤에서 남은 k만큼의 숫자를 제거해주었다.

 

"987654321"과 k=4가 입력으로 들어오는 경우를 생각해보면

왜 뒤에서 남은 k만큼의 숫자를 제거해 주어야 하는지 이해할 수 있다.

 

아이디어는 생각해 냈지만 구현에서 디버깅을 못하겠어서,

나와 비슷한 아이디어로 해결을 하신 분의 코드를 참고했다.

https://school.programmers.co.kr/questions/30941

이 분 코드를 보면서 내가 어떤 부분에서 잘못 하고 있었는지 보였다.

def solution(number, k):
    numbers = list(number)
    idxList = []

    # 앞에서부터 탐색
    # 현재 탐색하고 있는 숫자가, 그 다음 숫자보다 작을 경우에
    # 현재 탐색하고 있는 숫자 제거

    flag = 0
    for idx, n in enumerate(numbers):
        if k == 0:
            flag = 1
            break
        if idx != len(numbers) - 1:
            if numbers[idx] < numbers[idx + 1]:
                k -= 1
                idxList.append(idx)

    idxList.sort(reverse=True)
    for i in idxList:
        del numbers[i]
    if k > 0:
        numbers = numbers[:len(numbers)-k]

    answer = ''.join(numbers)

    return answer

 

위의 코드는 내 코드인데,

이 코드의 문제점은

제거를 한 후에 서로 새롭게 연달은 수가 되는 경우에 대해서

왼쪽 수가 오른쪽 수가 작은 경우를 제거하지 않아서 통과가 되지 않는 것이었다.

 

 

.

.

.

 

 

항상 while 반복문을 사용할 때에는,

while True로 무한 반복문을 돌리거나 조건을 하나만 적는 방식으로 사용해 왔는데,

and로 조건을 2개 거는 방식을 보니까 신선했다.

(왜 이 생각을 못했지? 남의 코드도 봐야 하는 이유...)

 while에 조건을 상세하게 걸면,

반복문 내부 코드가 더 간결해진다

 

나는 문자열로 들어온 number 값을 리스트로 변환해서

del 키워드로 삭제하는 방식으로 구현하려고 했는데,

그렇게 구현하려고 하니, 리스트에 값을 삭제를 하게 되면

반복문 내에서 인덱스 값이 달라진다는 점이 문제가 되었다.

 

문자열로 입력이 주어지면,

문자열 형태로 자르고 붙이는 방법을 활용해서

문제를 해결할 수는 없는 지 고민해봐야겠다.

 

그리고 문자열에서 어떤 문자를 제거해야 한다면,

그 문자만 잘라내고 나머지를 + 연산으로 붙일 수 있음을 기억해야겠다.

 

 

.

.

.

 

 

프로그래머스에서 가장 많은 형태로 제출된 코드는 다음과 같다.

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0: # 파이써닉 : stack and stack[-1] < num and k
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

 

스택을 활용한 풀이로,

인덱스로 복잡하게 조정할 필요가 없는 코드다.

 

스택 자료구조가 갖는 장점과 특징들을 잘 염두해두고

이러한 활용 예시들을 데이터로 잘 쌓아두어야

비슷한 활용 상황이 왔을 때, 실제로 활용을 해낼 수 있을 것 같다.

 

아래 사진을 보면,

스택을 활용한 풀이를 단계별로 이해하는데 도움을 받을 수 있다.

 

 

 

참고 자료

https://velog.io/@soo5717/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%81%B0-%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC