백준 - 14629 숫자 조각

문제

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

14629번: 숫자 조각

준하가 수포자가 되지 않도록 0~9까지의 숫자를 한 번만 사용해 입력받은 숫자 N과 가장 차이가 적은 숫자를 구하는 문제였다.

 

문제 풀이

그리디로 풀면 될 것 같아서 그리디로 풀었다. 근데 백트래킹으로 푸는게 정신 건강에 더 좋을 것 같다.

 

처음에는 long long으로 N을 입력받고, int 배열에 각 자리를 저장해줬었다. 문제를 풀다가 string으로 받게 하는게 더 간단한 것 같아서 string으로 입력받도록 수정했다. initNum과 num 배열은 지우는걸 까먹었다. ㅎ

 

핵심 원리는 앞자리 수가 최대한 비슷해야 전체 차이가 적어진다는 것이다.

 

처음에는 간단하게 앞에서부터 돌면서 사용하지 않은 수일 때는 계속 추가하고, 이미 사용한 숫자가 나올 경우에는 big과 small 둘로 나눴다.

• big: 현재 자리 숫자와 가장 비슷한 큰 수
• small: 현재 자리 숫자와 가장 비슷한 작은 수

그리고 다음부터는 big에는 사용하지 않은 작은 수부터, small에는 사용하지 않은 큰 수를 더해줬다.

 

하지만!! 반례가 나왔다..

2100 → 2098 이 정답이어야 했으나 2103이 나옴

 

이 반례를 생각하고 나서는 단순히 모든 자리의 수가 겹치지 않을 때까지 1을 뺄까도 생각했지만.. 전혀 효율적이지 않은 것 같았고 다른 방법을 생각했다.

 

현재 수보다 작은 수/큰 수를 만들어 small과 big의 값을 변경해 주는 방법이었다.

 

작은 수를 만드는 경우를 먼저 생각하고 그 후에 makeBigNum은 makeSmallNum과 동일한 방법으로 만들어서 makeSmallNum의 원리만 적겠다.

 

먼저 뒷자리부터 현재 자리와 가장 비슷한 작은 수가 존재하면 변경하고, 존재하지 않으면 현재 자리는 더이상 작은 수가 없기 때문에 뒷자리로 넘어간다. 이를 위해 마지막 수를 삭제했다. 이를 반복하다가 변경 가능한 부분에서 변경하고, 삭제한 만큼은 사용하지 않은 큰 수를 차례로 채워줬다.

 

2100 → 4번째 자리에서 이미 사용한 수임!
0과 가장 비슷한 작은 수 : 존재하지 않음
→ makeSmallNum 210

0 : 가장 비슷한 작은 수 존재하지 않음 → 삭제
1 : 가장 비슷한 작은 수 존재 → 0으로 변경
현재 수 : 20
삭제한 만큼 큰 수로 채우기
209 반환

 

그리고 처음에는 n의 마지막을 지울 때 '\0'으로 바꿔주는 방법을 사용했는데, 이렇게 하니.. '\0' 다음에 붙어서 저장되어 이상한 값이 나왔다. c++의 string에는 맨 뒤 문자를 지워주는 pop_back() 이라는 아주 좋은 메소드가 존재했다. ^^ string을 잘 사용하지 않아서 모르는 함수가 꽤 있는 것 같다.. 언제 한 번 정리해야겠다..

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <math.h>

using namespace std;

int num[15];
int numSize;
set<int> useNum; //smallNum
set<int> useBigNum;

void printNum(){
    printf("num 출력\n");
    for(int i=0;i<numSize;i++){
        printf("%d ",num[i]);
    }
    printf("\n\n");
}

void initNum(string str){
    numSize = str.size();
    for(int i=0;i<numSize;i++){
        num[i] = str[i]-'0';
    }    
}

void initUseBigNum(){
    for(auto iter:useNum){
        useBigNum.insert(iter);
    }
}

int findSmallNum(){
    for(int i=0;i<=9;i++){
        if(useNum.count(i) == 0) return i;
    }
}

int findBigNum(){
    for(int i=9;i>=0;i--){
        if(useNum.count(i) == 0) return i;
    }
}

int findNearSmallNum(int n){
    for(int i=n;i>=0;i--){
        if(useNum.count(i) == 0 && i != n) return i;
    }
    return -1;
}

int findNearBigNum(int n){
    for(int i=n;i<=9;i++){
        if(useNum.count(i) == 0 && i != n) return i;
    }
    return -1;
}

string makeSmallNum(string n){    
    int t = 0;
    for(int i=n.size()-1;i>=0;i--){ //마지막 꺼부터 작은거로 변환 ㄱㄴ하면 변환
        t++;
		int nowNum = n[i]-'0';
        useNum.erase(useNum.find(nowNum));
        int smallNum = findNearSmallNum(nowNum);
        n.pop_back();
        
        if(smallNum != -1) { //변경 가능
            n += to_string(smallNum);
            useNum.insert(smallNum);
            break;
        }        
    }
    t--;
    for(t;t>0;t--){
        int bigNum = findBigNum();
        n += to_string(bigNum);
        useNum.insert(bigNum);
    }

    return n;
}

string makeBigNum(string n){
    int t = 0;
    for(int i=n.size()-1;i>=0;i--){ //마지막 꺼부터 큰거로 변환 ㄱㄴ하면 변환
        t++;
		int nowNum = n[i]-'0';
        useNum.erase(useNum.find(nowNum));
        int bigNum = findNearBigNum(nowNum);
        n.pop_back();
        
        if(bigNum != -1) { //변경 가능
            n += to_string(bigNum);
            useBigNum.insert(bigNum);
            break;
        }        
    }
    t--;
    for(t;t>0;t--){
        int smallNum = findSmallNum();
        n += to_string(smallNum);
        useNum.insert(smallNum);
    }

    return n;
}

int main(int argc, char** argv)
{

    //1. string으로 입력받기
    string str;
    string small="", big="";
    
    cin >> str;
    
    // size가 10보다 큰 경우에 9876543210이 답
    if(str.size() > 10) {
        printf("9876543210");
        return 0;
    }
    
    initNum(str);
    
    //2. 앞에서부터 big, small 값 저장하기
    //2-1. 안겹치면서 같은 수일 경우엔 계속 진행
    //2-2. 겹치면 big/small 나눠서 계산
    //2-3. 현재 자리수보다 작은 수가 없을 경우에 앞자리를 작은 수로 변경해 더 작은 수로 만들어줘야함
    int i;
    for(i=0;i<numSize;i++){
        int nowNum = num[i];        
        if(useNum.count(nowNum) != 0){ //사용 불가능
            //가장 가까운 작은거 큰거 찾아야함, 원래 로직 사용 필요
            initUseBigNum();
            int nextSmall = findNearSmallNum(nowNum);
            int nextBig = findNearBigNum(nowNum);
            
            if(nextSmall == -1){ //앞자리 변경 필요
                small = makeSmallNum(small); //210 -> 209
                nextSmall = findBigNum();
            }
            
            if(nextBig == -1){
                big = makeBigNum(big);
                nextBig = findSmallNum();
            }       
            small += to_string(nextSmall);
            useNum.insert(nextSmall);
            big += to_string(nextBig);
            useBigNum.insert(nextBig);
            break;
        }
        //사용 가능
        small += to_string(nowNum);
        big += to_string(nowNum);
        useNum.insert(nowNum);
    }

    //나머지 숫자 만들어줘야함
    i++;
    for(i;i<numSize;i++){
        int findSmall = findSmallNum();
        int findBig = findBigNum();
        
        small += to_string(findBig);
        useNum.insert(findBig);
        big += to_string(findSmall);
        useBigNum.insert(findSmall);
    }
    
    long long smallDiff = abs(stoll(str)-stoll(small));
    long long bigDiff = abs(stoll(big)-stoll(str));

    if(smallDiff > bigDiff) cout<<stoll(big);
    else cout<<stoll(small);
	return 0;
}