프로그래머스 lv.2 큰 수 만들기

프로그래머스 lv.2 큰 수 만들기

 

처음 문제를 봤을 때 내 문제 접근 방법

1-1. count = 문자열 수 - 제거 개수

2-1. 만들 수 있는 조합을 다 찾음

3-1. 조합 중 max값을 return

 

1-2. 숫자 정렬 

2-2. 가장 큰 숫자부터 제거 개수 전까지 리스트에 추가

 

→ 문제점: 메모리 할당량 초과 (만 자릿수 넘어감) / 정답값과 일치하지 않음 (문제 이해 부족) 

숫자가 123123 이렇게 들어있다고 하여 332가 정답이 아님. 

 

문제 접근 방식 

 

>>> 앞자리에 큰 수가 오도록 <<< 

스택 + 그리디 사용 

 

1. for문 사용

2. while 조건(스택이 비어있지 않고, 이전 스택보다 더 크고, 제거 횟수가 남아있다면) 부합 시 스택 제거 

3. 현재 글자 char 스택에 추가

4. """제일 중요""" 모든 숫자가 동일한 경우가 있을 수 있음. 이럴 땐 제거가 안되어있기 때문에 맨 뒤에서부터 제거 횟수만큼 잘라냄 

 

내 코드

 

def solution(number, k):
    stack = []
    count = 0
    for char in number:
        while stack and char > stack[-1] and count < k:
            stack.pop()
            count += 1
        stack.append(char)
    if count < k:
            stack = stack[:-(k-count)]
    return ''.join(stack)

 

 

이와 유사한 문제를 만났을 때 접근 방식

 

🎯 [패턴 기반 사고법]

 

📌 Step 1. “최적의 결과를 만들라”는 말이 있으면 → 그리디 의심

→ 자릿수, 경로, 순서 최적화 → 대부분 그리디

 

📌 Step 2. “앞에서부터 하나씩 보면서 판단한다” → 스택 활용 여부 고려

→ 이전 값과 비교하면서 제거/유지 → LIFO 구조 = 스택

 

📌 Step 3. 반복해서 작은 값을 제거하고 큰 값을 남겨야 할 때 → while 사용

→ while stack and 현재 > stack [-1] and 조건: 형태

 

📌 Step 4. “k번만 제거할 수 있다” → 횟수 제한 처리 필요

→ k -= 1 또는 count < k 체크 필수

 

📌 Step 5. “순서를 바꾸지 않고” → 정렬 ❌

→ 정렬 쓰는 순간 틀림 → 반드시 제거 방식으로 해결