[백준/C++] 2529번: 부등호

문제

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

---

문제 요약

두 종류의 부등호 기호 '<'과 '>'가 k개 나열된 순서열 A를 입력 받는다.

 

해당 부등호 기호들 앞뒤에 서로 다른 한 자릿수 숫자를 넣어 모든 부등호 관계를 만족시켜야 한다.

 

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 붙이면 만들어지는 수들 중 최대 최소를 각각 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>

#define MAX_K 10

using namespace std;

// 부등호 개수
int k;

// 부등호 순서열
char A[MAX_K];

string max_num = "0";
string min_num = "9876543210";

bool visited[MAX_K];
 
void dfs(int num, string s) {
    // 원하는 길이의 수가 만들어지면
    if (s.size() == k + 1) {
        max_num = max(max_num, s);
        min_num = min(min_num, s);
        return;
    }

    for (int i = 0; i < 10; i++) {
        if (visited[i]) continue;

        if (A[s.size() - 1] == '>' && s.back() - '0' < i) continue;
        if (A[s.size() - 1] == '<' && s.back() - '0' > i) continue;

        s.push_back(i + '0');
        visited[i] = true;
        dfs(i, s);
        s.pop_back();
        visited[i] = false;
    }
}

int main() {
    // 입력
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> A[i];
    }

    string s = "";

    for (int i = 0; i < 10; i++) {
        visited[i] = true;
        s.push_back(i + '0');
        dfs(i, s);
        s.pop_back();
        visited[i] = false;
    }

    cout << max_num << "\n";
    cout << min_num;

    return 0;
}

---

코드 설명

1. 부등호 개수 k와 부등호 순서열 A를 각각 입력 받는다.

 

2. 빈 문자열 s를 선언하고, s 뒤에 문자를 삽입하고 삭제하면서 완전탐색(백트래킹)을 진행한다.

 

3. bool형 배열 visited를 통해 각 숫자가 s에 존재하는지를 체크한다.

 

4. 탐색 중 원하는 길이의 문자열이 만들어지면, 크기가 더 큰/작은 수를 표현하는 문자열을 갱신한다.

 

5. 아니라면, s에 존재하지 않은 문자 중 조건을 만족하는 문자를 찾아 s 뒤에 삽입하고, 재귀적으로 탐색한다.

 

6. 재귀 탐색이 끝나면, 다시 s 뒤에서 삭제하고 조건을 만족하는 다른 문자로 탐색한다. (반복)

 

7. 완전탐색(백트래킹)이 끝나면, 최대와 최소 문자를 각각 출력한다.

---

고찰

1. '문자열.push_back(문자)'를 통해 문자열 뒤에 문자를 삽입할 수 있다.

 

2. '문자열.pop_back(문자)'를 통해 문자열 뒤에 문자를 삭제할 수 있다.

 

3. 'max(문자열, 문자열)'을 통해 두 문자열 중 아스키 코드 상으로 더 큰 문자열를 반환할 수 있다.

 

4. 'min(문자열, 문자열)'을 통해 두 문자열 중 아스키 코드 상으로 더 작은 문자열를 반환할 수 있다.

 

5. '문자열.size()'를 통해 문자열의 길이를 반환할 수 있다.

 

6. '문자열.back()'을 통해 해당 문자열의 맨 뒤 문자를 반환할 수 있다.

 

7. 문자 - '0'은 문자를 정수로, 정수 + '0'은 정수를 문자로 변환할 수 있다.