2812 크게 만들기

백준 2812 크게 만들기 문제이다.

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

그리디 알고리즘으로 풀 수 있는 문제이다. 나는 생각해보다가 전혀 감이 안 잡혀서 풀이도 많이 참고하였다.

 

 

내가 생각한 풀이 )

앞에서부터 읽으면서 가장 작은 숫자를 k번만큼 반복하면서 지운다.

-> 백준 예제 3이 반례이다. 앞에서부터 지우면 1,2,2,1을 지우게 되서 477584가 나오고, 이는 775841보다 작다.

2812 예제 3번

여기서 부터 아무 생각이 안 났다... 마음을 다 잡고 더 생각해봤어야 했는데 무작정 여기서부터 풀이를 참고하였다.

 

진짜 풀이 )

내가 생각한 풀이와 비슷했다면 비슷했다고 볼 수 있다. 가장 작은 숫자를 지우는 것은 맞으나, 숫자의 n번째 자리까지 읽었을 때에 가장 작은 숫자들을 지우고, 그 다음으로는 숫자의 n+1자리까지 읽었을 때에 가장 작은 숫자들을 지우고...(이미 n번째 자리에서 가장 작은 숫자들이 지워져 있는 상태이다!따라서 그리디가 가능하다고 생각할 수 있는 것 같다) 이걸 숫자가 끝날 때까지 반복하면 된다.

 

코드 (https://sihyungyou.github.io/baekjoon-2812/ 참고. 감사합니다 !!):

#include <iostream>
#include <queue>
using namespace std;

int main(){
    int n,k;
    char a[500001];

    scanf("%d%d", &n, &k);
    scanf("%s", a);

    deque<char> dq;
    for(int i=0;i<n;i++){
        while(k && !dq.empty() && dq.back()<a[i]){ // dq에 넣는데 그 상황에서 조금이라도 작은 게 있으면 dq안에 있는걸 다 pop한 후 dq에 넣기.
            dq.pop_back();
            k--;
        }
        dq.push_back(a[i]);
    }
    for(int i=0;i<dq.size()-k;i++) printf("%c", dq[i]);
    printf("\n");

    
}

따라서 코드는 dq라는 큐에 우리의 정답을 계속 넣는 것인데, a를 순서대로 하나씩 읽으면서 dq의 원소들과 비교했을 때 pop을 해야 한다!라고 하면(그러니까 a의 n번째 숫자가 dq의 마지막 원소보다 크고 dq가 안 비었을때) pop을 계속 해주고, 그 다음에 dq에 a의 i번째 원소를 추가하는 것이다. 이 과정을 반복하면 된다.

여기서 deque가 어려울 수 있는데, deque는 큐랑 똑같다. (FIFO) 그런데 queue는 마지막 원소를 접근 할 수 없고 front만 가능하다면 deque는 마지막 원소 접근과 pop_back()이 가능하도록 만들어 놓은 것이다.

 

여기서 내가 이해가 안 갔던 부분..은 dq의 맨 마지막 원소랑 n번째 자리 숫자랑 비교해서 작으면 지우는데, 그럼 그 앞에 있는 작은 숫자는 언제 지워지냐는 거였다. 생각해보면, 맨 마지막 원소랑 n번째를 비교하기 전, n-1번째에서 그 전 맨 마지막 원소와 비교되서 이미 지워졌을 것이라는 거다. 따라서 여기까지는 내림차순? 으로 이미 정렬되어있다고 생각할 수도 있을 것 같다.

 

예시)

4 2

1477

여기서 세번째 자리 7, (14'7'7)을 지울때 1은 그럼 안 지우나 ?? 이렇게 생각했던 것이다. 그러나 생각해보면, 1은 이미 두번째 자리 4를 고려할 때 이미 지워져 있다는 것을 알 수 있다. 

 

아직도 약간 왜 이렇게 돌아가지...? 라는 생각이 들기는 한다. 

여기서 내가 주목한 부분은 -----1에서 1을 지우는 것보다 1-----에서 1을 지우는 게 더 영향력이 크다는 것이다. 이것이 모두 고려되어서 맨 앞에서부터 읽을 때 이렇게 한다는 것 같기는 하다.

그리디 문제가 넘 어렵당... 흑흑 한번 복기한다는 마음으로 정리했는데도 어렵다. 내일 코드리뷰쓰게되면 쓰면서 한번 더 혼자 짜봐야겠다!!