JArchive 프로그래밍 일기

문제

부등호 백준 2529번

리뷰

부등호의 개수k와 부등호 리스트가 주어진다.

< < < > < < > < >

k+1 개의 숫자를 나열하여 부등호를 만족시켜야 한다. 0부터 9까지의 숫자만 사용 가능하다.

이를 만족하는 수열 예시 2개는 아래와 같다. 수열은 모두 달라야 한다. 숫자를 모두 이어붙이면 하나의 '숫자'가 된다.

//  3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 
3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0
5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

주어진 부등호 관계를 만족하는 k+1자리의 최소 정수와 최대 정수를 출력해야 한다.

0부터 9까지 10가지의 숫자를 중복하지 않고 수열을 만드는 것은 재귀를 이용하여 N과 M 시리즈 문제에서 해봤다.

아래는 기본 구조다. index는 채워야 할 자리의 index 이다.

만약 4자리 숫자로 구성된 수열을 만들어야 하면, (n == 4 라고 가정)

index가 0,1,2,3 까지 변화하면서 for문에서 숫자를 선택하여 채우고, ( 이 때, ch[i] 배열을 검사하면서 선택이 이미 된 )

index가 4가 된 순간에 if문 조건을 만족시키면서 수열이 완성되서 return 된다.

bool ch[11]; // 중복을 피하기 위한 체크 배열 

void Combination(int index){ 

    if(index == n ){ // 수열 완성. 
        //
        return;      
    }

    for(int i = 0; i <= 9; i++){
        if(ch[i]) continue; // 이미 사용한 숫자라면 지나감

         ch[i] = true; // 선택
         Combination(index+1); // 다음 자리수 선택을 위해 재귀 호출 
         ch[i] = false; // 선택 안함  
    } 
}

이 문제에서는 백트레킹 기법을 쓴다.

백트레킹은 의미 없는 함수 호출을 피하기 위해 앞에 조건문으로 검사해서 함수 호출 횟수를 줄이는 것이다.

k 개의 부등호가 주어지면, 수열의 숫자는 k+1개로 구성된다.

Combination 함수는 index 자리의 숫자를 선택하면서 숫자를 string num에 담아서 넘긴다.

만약 첫째 자리 숫자를 선택해야 하는 index == 0 인 상황에는, 무조건 숫자를 선택한다. 재귀 호출을 피할 이유가 없다.

이와 달리 index가 1 이상인 경우, 즉 둘째, 셋째 그 이상의 자리의 숫자를 선택해야 하는 상황일 때는 앞자리 숫자와 부등호를 고려해야 한다.

// 왜냐하면 첫째 숫자가 9 이고 부등호가 < 인 경우가 있다. 그런데 9 를 초과하는 1자리 숫자는 없다.

if(index == 0 || SignCheck(num[index-1], i+'0', sign[index-1]))

// 따라서 앞자리 숫자, 현재 선택하려는 숫자, 앞자리 부등호를 인자로 넘겨서 검사한다.
// 아래는 함수의 시그니처다.     
bool SignCheck(char a, char b, char oper); 

SignCheck 함수는 현재 선택하려는 숫자 b가 부등호를 만족시킬 수 있는 숫자라면 true를 반환한다.

수열이 완성되면 index가 k+1이 되는 순간이다. 그 때 ans 벡터에 넣는다.

답은 최대, 최소 숫자니까 ans 벡터를 정렬해서 맨앞, 맨뒤 값을 출력하면 된다.

void Combination(int index, string num){ 
    // index : 선택해야 할 (수열에서의) 숫자 자리. 0부터 9까지. 

    if(index == (k+1) ){ // 수열 완성. 벡터에 넣는다 
        ans.push_back(num); 
        return;      
    }

    for(int i = 0; i <= 9; i++){
        if(ch[i]) continue; // 이미 사용한 숫자라면 지나감

        // 첫번째 자리 숫자를 고르는 거라면, 무조건 선택. (index == 0)
        //  그게 아니라면, 앞자리 숫자 num[index-1] 과 현재 선택하려는 숫자 i 와 부등호를 넘긴다.  
        if(index == 0 || SignCheck(num[index-1], i+'0', sign[index-1])){
            ch[i] = true; // 선택
             Combination(index+1, num + to_string(i)); // 다음 자리수 선택을 위해 재귀 호출 
            ch[i] = false; // 선택 안함  
        }

    } 
}

코드

#include <iostream>
#include <algorithm> 
#include <vector>
#include <string>
using namespace std;


int k;
char sign[11];  // 부등호 담은 수열   
int num[11];     // 조합으로 만들어진 수열  
bool ch[11];  // 숫자 중복 불허 
vector<string> ans; // 부등호를 만족하는 수열을 저장하는 벡터 
string maxnum, minnum;

bool SignCheck(char a, char b, char oper){ // 부등호를 만족시키는지 검사

    if(oper == '<'){
        if(a>b) return false;

    } else {// '>'
        if(a<b) return false;
    }
    return true;
}

void Combination(int index, string num){ 
    // index : 선택해야 할 (수열에서의) 숫자 자리. 0부터 9까지. 

    if(index == (k+1) ){ // 수열 완성. 벡터에 넣는다 
        ans.push_back(num); 
        return;      
    }

    for(int i = 0; i <= 9; i++){
        if(ch[i]) continue; // 이미 사용한 숫자라면 지나감

        // 첫번째 자리 숫자를 고르는 거라면, 무조건 선택. (index == 0)
        //  그게 아니라면, 앞자리 숫자 num[index-1] 과 현재 선택하려는 숫자 i 와 부등호를 넘긴다.  
        if(index == 0 || SignCheck(num[index-1], i+'0', sign[index-1])){
            ch[i] = true; // 선택
             Combination(index+1, num + to_string(i)); // 다음 자리수 선택을 위해 재귀 호출 
            ch[i] = false; // 선택 안함  
        }
    } 
}


int main(void){

    cin >> k;

     for(int i = 0; i < k; i++){
         cin >> sign[i];
    } // 입력받기 끝 

    Combination(0, "");    

    sort(ans.begin(), ans.end()); // 오름차순 정렬 후, 맨 뒤가 최대, 맨 앞이 최소

    cout << ans[ans.size()-1] << '\n' << ans[0];

    return 0;
}