수 지우기( BOJ 1467 )

문제 : https://www.acmicpc.net/problem/1467

1467번: 수 지우기

 

문제 파악하기

세준이가 가지고 있는 숫자 중 제시된 지울 숫자들을 지워서 만들 수 있는 가장 큰 숫자를 구하는 문제입니다. 문제 자체는 이해하기 어렵지 않지만 문제를 해결할 전략을 세우는데 생각이 필요한 문제입니다. 문제를 해결하기 위해 우리가 초점을 맞춰야 할 핵심요소는 바로 큰 수의 조건입니다. 큰 수가 되기 위해서는 큰 숫자가 왼쪽에 있어야 합니다. 이 점에 주목하면 문제를 해결할 수 있습니다.

 

문제 해결하기

우리는 세준이가 가지고 있는 숫자 중 제시된 지울 숫자들을 어느 위치의 어떤 숫자를 제거했는지에 따라 숫자의 크기 자체는 달라집니다. 하지만 결과물로 가지고 있는 숫자의 길이는 항상 동일합니다. 따라서, 우리는 정해진 길이의 숫자 중 가장 큰 숫자부터 하나씩 만들 수 있는지 확인하면 됩니다. 물론, 모든 경우의 수를 고려하면 너무 오래 걸리기 때문에 효율적으로 만들 수 있는 숫자인지 여부를 파악해야 합니다.

 

정답을 구할 때에는 가장 왼쪽부터 숫자를 배치하며, 가장 큰 숫자(9)부터 배치할 수 있는지 확인해봅니다. 확인할 때에는 현재 남은 숫자 중 확인할 숫자의 위치를 찾은 다음, 찾은 숫자 앞에 있는 숫자들을 모두 지울 수 있는지 확인하면 됩니다. 예를 들어 세준이가 가지고 있는 숫자가 [ 4432334413 ]이며, 제시된 숫자가 [ 3324 ]라고 가정해봅시다. 이 경우, 정답의 첫 번째와 두 번째 숫자에는 의심할 여지가 없이 4를 배치합니다. 그리고 세 번째 자리에 배치할 숫자를 확인해봅시다.

 

남은 숫자: 23334413 지울 숫자: 3324 >> 만들어진 숫자(정답): 44

 

3번째에 배치할 수 있는 숫자는 4, 3, 1 중 하나입니다. 그럼 4부터 확인해봅시다. 만약 3번째에 4를 넣기 위해서는 3개의 3과 1개의 2를 지워야 합니다. 하지만 3은 최대 2개까지만 지울 수 있습니다. 그렇기에 3번째 자리에 4는 배치할 수 없습니다. 이어서 3을 확인해봅시다. 다행히 3은 2를 하나만 지운다면 배치할 수 있습니다. 그럼 3을 배치하고 다음 4번째 자리 숫자를 확인하면 됩니다. 3번째 자리까지 배치하면 다음과 같은 결과를 얻게 됩니다.

 

남은 숫자: 334413 지울 숫자: 334 >> 만들어진 숫자(정답): 443

 

이렇게 왼쪽부터, 그리고 큰 수부터 배치할 수 있는지 하나씩 확인하면 문제를 해결할 수 있습니다. 다행히 제시되는 모든 숫자의 최대 길이가 1,000개이기에 중첩 반복문을 사용하여 알고리즘을 설계할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
 
string inp, e;
 
string ans;
int len, pos;
int numCnt[10], eCnt[10], tCnt[10];
 
bool isPossible() {
    for(int i=0;i<10;i++) {
        if(tCnt[i] > eCnt[i]) return 0;
    }
 
    return 1;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> inp;
    cin >> e;
 
    for(int i=0;i<inp.length();i++) numCnt[inp[i]-'0']++;
    for(int i=0;i<e.length();i++) {
        numCnt[e[i]-'0']--;
        eCnt[e[i]-'0']++;
    }
 
    len = inp.length()-e.length();
    for(int i=0;i<len;i++) {
        for(int j=9;j>=0;j--) {
            if(!numCnt[j]) continue;
 
            memset(tCnt, 0, sizeof(tCnt));
            for(int ii=pos;(inp[ii]-'0')!=j;ii++) tCnt[inp[ii]-'0']++;
 
            if(isPossible()) {
                while((inp[pos]-'0')!=j) {
                    eCnt[inp[pos]-'0']--;
                    pos++;
                }
                ans += (j+'0');
                numCnt[j]--;
                pos++;
 
                break;
            }
        }
    }
 
    cout << ans;
}

후기

그리디 문제답게 단순하지만 생각을 많이 하게 만드는 문제였습니다. 해결할 때에 가장 도움이 된 건 숫자를 지우는 것보다 큰 수를 어떻게 만들 수 있을까에 초점을 맞춘 것입니다. 복잡한 자료구조보다 아이디어와 생각을 좋아하는 사람에게 추천하고 싶은 문제입니다.