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

문제

문제 링크

문제 해결 접근

[1] 문제 출제 포인트

• 그리디 알고리즘 : 부분의 최적해가 전체의 최적해가 되도록 푼다.
• 이 문제에서는 최대한 앞자리에 큰 수가 오게 해야 한다. 즉, 앞에 있는 작은 숫자를 제거해야 한다!
• 문제 조건 : 문자열의 길이가 아주 기니까 완전 탐색을 할 수는 없다. 효율성에 초점을 맞춰서 문제를 풀어야 한다.
• 생각해봐야 하는 테스트 케이스 : 모든 숫자가 다 동일한 케이스가 있을 수 있다. 그 경우에도 동작할 수 있게 코드를 짜야 한다.

[2] 내가 막혔던 부분 (생각해봤던 접근법)

• 단순히 작은 수를 정렬해서 빼도 안 된다..
• top_k에 해당하는 큰 수만 남기고 나머지를 순차적으로 지우는 것도 안 되고 (이것은 시간 복잡도가 너무 컸다)...
• 투 포인터를 사용해서 인덱스 i와 i+1를 비교하며 나아가거나, 처음과 끝을 비교해가며 가는 등등...
• 내가 그리디 알고리즘에서 막힐 때의 특징인 것 같기도 한데, 뭔가 풀 수 있을 거 같으면서도!! 안 풀렸다. 😂

[3] 문제 해결 포인트

• "큰 수가 최대한 앞에 오면 좋다."
• "앞에 있는 작은 숫자들을 지워나가는 것이 필요하다."
• "이것을 스택을 통해서 해결하자!" -> 지금의 숫자보다 앞에 작은 숫자들이 있다면 계속해서 지워나간다.

코드 구현

알고리즘 설명

• 스택을 만들어준다. (파이썬 리스트로 구현)
• number들에 있는 숫자들을 for문으로 하나씩 탐색한다. (for num in numbers: )
• 각 numbers에 대하여,
  - while 1) 스택이 있고 2) 스택의 마지막 숫자가 num보다 작고 3) k>0인 동안 -> stack에서 pop하고 k-=1을 해준다.
  - 해당하지 않으면 num을 스택에 append한다.
• 또한, 모든 숫자가 다 동일한 케이스에는 앞의 숫자를 len(number)-k 만큼 남기도록 해준다.

정답 코드

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) 
        
    if len(stack) > len(number)-k: ## 모두 다 같은 숫자로 이루어져 있는 경우 
        stack = stack[:len(number)-k]
    
    return ''.join(stack)

느낀 점

• 그리디는 항상 짜고 나면 코드는 짧은데 문제 생각 발상이 안 떠오르기 시작하면 해결이 어렵다.
• 반대로 생각하면 문제 발상만 잘 떠올릴 수 있으면 잘 해결할 수 있다. 여러 유형을 많이 접하며 익숙해져야겠다.