[백준 2529] 부등호 (C++)

2529번: 부등호

브루트 포스 - 순열 (연습)

 

 

어제 푼 카카오 2021 하반기 공채 1차 코테 4번문제 (양궁) 과 비슷한 문제이다.

 

정렬이 잘못되었다고 하는데 나는 아직도 어디가 틀렸는지 감이 오지않는다.

 

경험삼아 쳐본 코테 덕분에 나 자신을 돌아보고 실력이 얼마나 부족한지 다시 생각해보는 계기가 되었다.

 

지금까지 하고싶은 알고리즘 공부, 재밌어보이는 문제, 내가 자신있는 파트의 문제 위주로 풀었고 자기 만족을 위해서 알고리즘 문제를 풀어왔다면, 남은 1년은 시험 공부하는 느낌으로 개념을 하나하나 잡으면서 예전에 푼 문제 위주로 체계적으로 공부하면서 문제를 풀 예정이다.

 

 

 

부등호 왼쪽에 들어온 숫자를 바탕으로 부등호 오른쪽에 들어올 수 있는 모든 숫자에 대해서 백트래킹 기법을 사용해 완전 탐색을 돌렸다.

 

58line을 보면 '-'을 추가해주는데 모든 탐색이 끝나고 코드에서 vector범위를 벗어나는 곳을 참조할 예정이기 때문에 오버플로우 방지를 위해 null문자 느낌으로 넣어주었다.

 

0-9까지의 모든 숫자에 대한 순열을 구하는 것과 동일하다.

시간복잡도는 최대 O(10!)로 360만 정도의 연산이 수행될 것이다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
 
int K;
vector<char> operation;
bool visited[10];
string minvalue = "", maxvalue = "";
 
void dfs(int prev, char op, int cnt, string str){
    if(cnt == K){
        // 최댓값은 가장 마지막에 결정된 숫자가 될 것이다.
        maxvalue = str;
        // 최솟값은 가장 먼저 결정된 숫자가 최소일 것이다.
        if(minvalue == ""){
            minvalue = str;
        }
        return;
    }
    
    
    for(int i = 0; i < 10; i++){
        if(visited[i]) continue;
        visited[i] = true;
        char next = i + '0';
        
        // 이전 숫자와 현재 사용 하려고하는 숫자가 부등호에 알맞은지 확인 후 탐색
        if(op == '<' && prev < i){
            dfs(i, operation[cnt+1], cnt+1, str + next);
        }
        if(op == '>' && prev > i){
            dfs(i, operation[cnt+1], cnt+1, str + next);
        }
        visited[i] = false;
    }
    
}
 
void input(){
    cin >> K;
    char c;
    for(int i = 0; i < K; i++){
        cin >> c;
        operation.push_back(c);
    }
    operation.push_back('-');
}
 
void solve(){
    for(int i = 0; i < 10; i++){
        visited[i] = true;
        char now = i + '0';
        string st = "";
        st += now;
        dfs(i, operation[0], 0, st);
        visited[i] = false;
    }
    
    cout << maxvalue << "\n" << minvalue << "\n";
}
 
int main(){
    input();
    solve();
    
    return 0;
}