백준 2812번: 크게 만들기

문제

• acmicpc.net/problem/2812
• 스택을 이용해 탐색 과정에서 불필요한 정보 제거하기

기록 포인트

• 스택을 통해 탐색 범위를 줄이는 과정 이해하기
  • 처음에는 분할정복으로 재귀적으로 접근했으나 시간 초과 및 오류 발생
  • 다음으로 스택을 활용하여 탐색 범위를 줄임
    • 반복의 다음 회차에서 고려할 필요 없는 정보를 제거하는 방식
• 탐색 방식을 구성한 뒤에 비효율이 발생하는 최악의 상황을 생각해보기
  • 반복된 비교가 발생하지는 않는지
  • 만약 그렇다면 이를 어떻게 줄일 수 있을지

접근 방식

• 스택에는 반복의 다음 회차에서 확인할 필요가 있는 값만 남김
• [코드 구성]
  • 최종적으로 만들 숫자열의 길이(M) 확인
  • 스택 생성
  • 숫자열의 각 숫자(c)에 대하여
    • 스택에 고려할 숫자가 남아 있는 동안
      • 제외시킬 숫자의 개수(K)가 0이면 스택 탐색 종료
      • 스택에서 가장 최신값(v) pop
        • v가 c보다 작다면
          • v 대신 c를 남기는 것이 좋으므로 제외시킴
          • K 를 1 감소
        • v가 c보다 크거나 같다면
          • v 를 남기는 편이 더 좋으므로 스택에 v 다시 추가
          • (K 조정 없음)
          • v 보다 작은 값들은 스택에 남아 있지 않으므로 스택 탐색 종료
    • 현재 스택의 길이가 M보다 작은 경우
      • 스택에 c 추가

제출 답안

스택 활용

import sys
N, K = list(map(int, sys.stdin.readline().split()))
numbers = [int(c) for c in sys.stdin.readline().rstrip()]
M = N - K
stack = []
for c in numbers:
    while stack and K > 0:
        v = stack.pop()
        K -= 1
        if v >= c:
            stack.append(v)
            K += 1
            break
    if len(stack) < M:
        stack.append(c)

print("".join((str(c) for c in stack)))

(참고) 분할정복 활용

• [코드 구성]
  • 베이스 케이스
    • K가 0인 경우
      • 더 이상 뺄 숫자가 없으므로, 결과 배열 뒤에 남은 배열 추가하여 리턴
    • 숫자열의 길이와 K가 동일한 경우
      • 남은 숫자열을 모두 빼야하므로, 결과 배열 리턴
  • 분할 및 결합
    • 숫자열의 앞에서부터 K+1개의 숫자 중 가장 큰 숫자(A)를 찾아 결과 배열에 추가
    • A의 앞에 있는 숫자들은 고려할 필요 없으므로 숫자열에서 제외
    • 제외된 숫자 개수만큼 K 개수 축소
    • 결과 배열에 A를 추가
    • 남은 문자열과 조정된 K로 다시 재귀 함수 실행
• 시간 초과 발생 원인
  • 숫자열에서 큰 수가 앞에 나와 숫자열 축소가 잘 되지 않으면, 숫자 간 크기 비교가 반복됨
  • 대표 사례
    • N, K = 8, 4
    • numbers = "89654321"
    • 진행 과정
      • 1 회차에 8,9,6,5,4를 비교해 9을 저장, K = 3 축소
      • 2 회차에 6,5,4,3을 비교해 6을 저장, K = 3 유지
      • 3 회차에 5,4,3,2를 비교해 5을 저장, K = 3 유지
      • 4 회차에 4,3,2,1을 비교해 4를 저장, K = 3 유지
      • 5 회차에 3,2,1의 길이와 K 가 동일하므로, 종료
    • 결과 분석
      • 동일한 값들 간의 비교를 반복하게 됨

import sys
N, K = list(map(int, sys.stdin.readline().split()))
numbers = [int(c) for c in sys.stdin.readline().rstrip()]

def parse(K, results):
    global numbers
    # 더 이상 뺄 숫자가 없으면 종료
    if K == 0:
        return results + numbers
    # 남은 숫자를 모두 빼야하면 종료
    if len(numbers) == K:
        return results 
    # 앞에서부터 K+1개 중에 가장 큰 숫자의 위치 찾기
    max_idx, max_num = 0, numbers[0]
    for i in range(1, K+1):
        num = numbers[i]
        if num > max_num:
            max_idx, max_num = i, num
    # 결과 배열에 숫자 추가
    results.append(max_num)
    # 해당 숫자 앞의 숫자들 제거
    numbers = numbers[max_idx+1:]
    # 뺄 수 있는 숫자 개수 조정
    K = K - max_idx
    return parse(K, results)

results = parse(K, [])
print("".join((str(c) for c in results)))