파이썬 알고리즘 288번 | [백준 2812] 크게 만들기 - 스택, 그리디

Yunny.Log ·2023년 1월 4일

Algorithm

목록 보기

293/318

288. 크게 만들기

1) 어떤 전략(알고리즘)으로 해결?

스택, 그리디

2) 코딩 설명

내가 들어가려 할 때 내 이전엔 나보다 작은 애들은 있을 수 없다.
그림처럼 꺾이는 순간이 발생하면 안되기 때문이다.
근데 예외처리 해주어야 하는 부분은 맨 마지막 요소이다.
- 맨 마지막 요소 앞에는 이미 걸러진 애들만 있어서 자신보다 작은 애들이 없을 수도 있다.
- 이 상황에서 cnt (삭제한 갯수) 가 k (삭제해야 하는 갯수) 보다 작으면 이 마지막 요소를 없애줘야 함
  - 이 마지막 요소가 삭제 안된 것은 나보다 앞에 애들이 이미 커서 (나보다 작은 애들이 없기 때문 ) 가 이유이다.
  - 이 말인 즉슨 마지막 요소가 가장 작은 요소이므로 끝까지 다 돌았는데도 cnt<k 인 상황이라면 스택에 맨 마지막으로 들어간 애 제거해주면 됨
```
  # k개만큼 제거 안됐을 시엔 k개만큼 뒤에서부터 제거
while cnt<k : 
   stack.pop()
   cnt+=1
```

<내 풀이>


import heapq
import sys

n,k = map(int,sys.stdin.readline().rstrip().split())
lis=list(map(int,sys.stdin.readline().rstrip()))
stack = []
cnt = 0

for i in range(n) : 
    while stack : 
        if cnt<k and stack[-1] < lis[i]: 
            # 내가 스택 마지막 애보다 크면 스택 마지막 애 제거 
            # ( 내 이전 애들은 나보다 커야하므로 )
            stack.pop()
            cnt+=1
        else : break
    stack.append(lis[i])

# k개만큼 제거 안됐을 시엔 k개만큼 뒤에서부터 제거
while cnt<k : 
    stack.pop()
    cnt+=1

for j in stack :  
    print(j,end="")

< 내 틀렸던 풀이, 문제점>

1. 시간초과


import sys
import heapq
n,k = map(int,sys.stdin.readline().rstrip().split())
# N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수
lis=list(map(int,sys.stdin.readline().rstrip()))
lis_heap = lis.copy()
heapq.heapify(lis_heap)
for i in range(k) :
    target = heapq.heappop(lis_heap)
    lis.remove(target)
for l in lis : 
    print(l,end="")

(2) 5프로에서 틀린 풀이

from collections import deque
import sys

n,k = map(int,sys.stdin.readline().rstrip().split())
lis=list(map(int,sys.stdin.readline().rstrip()))
target_lis = [0 for _ in range(500001)]
lis_heap = lis.copy()
lis_heap.sort()
lis_heap = deque(lis_heap)

for j in range(k) : 
    target_lis[lis_heap.popleft()]+=1
    
for j in range(n) :  
    if target_lis[lis[j]]>0:
        target_lis[lis[j]]-=1
    else : 
        print(lis[j],end="")

그냥 단순하게 작은 것 두개 뽑아서 지우는 것이 아니었음 ( 어쩐지 그렇게 쉬울리 없음 )

(ex)

작은거 네개 지우면 1 두개랑 2 두개 지우면 되는데 그걸 지우는 것보다 맨 앞에 4를 지우는게 더 better ( 4,1, 지우면 앞자리가 7로 시작하게 되므로 )

나보다 앞의 숫자들에서 낮은게 존재하면 안되는 것 !! => 스택으로 접근
(관련 문제 : 6198 옥상정원 , 탑 블로그 정리 & 2493 탑 )

(3) 스택 접근 => 그러나 72프로에서 틀림

import sys

n,k = map(int,sys.stdin.readline().rstrip().split())
lis=list(map(int,sys.stdin.readline().rstrip()))
stack = []
cnt = 0

for i in range(n) : 
    while stack : 
        if cnt<k and stack[-1] < lis[i]: 
            # 내가 스택 마지막 애보다 크면 스택 마지막 애 제거 
            # ( 내 이전 애들은 나보다 커야하므로 )
            stack.pop()
            cnt+=1
        else : break
    stack.append(lis[i])
    
for j in stack :  
    print(j,end="")

=> 반례

10 5
9993333932
정답 : 99993
출력 : 999932

5 3
98291
정답 : 99
출력 : 991

- 마지막 애에 대한 예외사항 존재 !!

근데 예외처리 해주어야 하는 부분은 맨 마지막 요소이다.
맨 마지막 요소 앞에는 이미 걸러진 애들만 있어서 자신보다 작은 애들이 없을 수도 있다.
이 상황에서 cnt (삭제한 갯수) 가 k (삭제해야 하는 갯수) 보다 작으면 이 마지막 요소를 없애줘야 함
- 이 마지막 요소가 삭제 안된 것은 나보다 앞에 애들이 이미 커서 (나보다 작은 애들이 없기 때문 ) 가 이유이다.
- 이 말인 즉슨 마지막 요소가 가장 작은 요소이므로 끝까지 다 돌았는데도 cnt<k 인 상황이라면 스택에 맨 마지막으로 들어간 애 제거해주면 됨
  # k개만큼 제거 안됐을 시엔 k개만큼 뒤에서부터 제거
while cnt<k : 
   stack.pop()
   cnt+=1