[백준 2529] - 부등호(C++)[실버1]

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1) 자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

 

🔎문제 해석

백트래킹 알고리즘은 진행하다가 막히면 이전 선택지에서 다른 경우를 선택하는 알고리즘이다.
부등호문제와 백트래킹 알고리즘은 결이 비슷하다고 생각해서 백트래킹 알고리즘을 선택해서 풀었고, 문제 알고리즘 분류도 그러하다!
백트래킹을 진행하면서 문제의 조건(모든 숫자는 딱 한번만, 부등호의 방향)을 생각하면서 최솟값과 최댓값을 구해주면 된다.

 

💡문제 풀이

• 기본적인 함수의 진행은 재귀함수로 진행했다.
  • 한칸씩 증가시키고, 문자열도 계속 이어 붙였다.
• 부등호의 방향에 따라 bool 값에 변화를 줬다. ">" -> true, "<" -> false
• 반복문을 0~9까지의 숫자를 검사했다.
• 만약 처음 넣는 경우라면 조건을 검사하지 않고, 문자열 뒤에 숫자를 이어 붙였다.
  • 여기서 방문처리를 한 후 -> 재귀함수 호출 -> (재귀함수가 만약에 빠져나온다면) 방문처리 초기화
• 만약 처음 넣는 경우가 아니라면, 부등호와 해당 숫자가 이미 사용되었는지에 대한 검사를 해줘야 한다.
  • 부등호의 방향이 > 라면, 지금 뽑으려는 숫자와, 이 전 숫자의 대소관계를 비교해서, 뽑으려는 숫자가 더 작아야 한다.
  • 부등호의 방향이 < 라면, 지금 뽑으려는 숫자와 , 이 전 숫자의 대소관계를 비교해서, 뽑으려는 숫자가 더 커야 한다.
• 만약 재귀호출이 n+1번 이루어졌다면, 그때 문자열을 숫자로 바꿔서 최솟값과 최댓값을 각각 갱신해 주면 된다.

 

❌주의할 점

나는 int형으로 stoi를 사용했는데 부등호가 9개일 때 int의 범위를 벗어나기에 long을 사용해야 한다!

 

💻전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <string.h>
using namespace std;
int n;
vector<char> str;
long long small = LONG_MAX, big = 0;
vector<int> v;
void funct(int step, string s);
string ss = "";
string banswer = "", sanswer = "";
int main()
{
    cin >> n;
    str.resize(n, 0);
    v.resize(10, 0);
    for (int i = 1; i <= n; i++)
    { // 부등호 방향 넣기.
        cin >> str[i];
    }
    funct(0, ss);
    cout << banswer << "\n"
         << sanswer << endl;
}
void funct(int step, string s) // 백트래킹 함수.
{
    bool opt = true;
    if (str[step] == '>') // 왼쪽 방향은 true
        opt = true;
    else // 오른쪽 방향은 false
        opt = false;
    if (step == n + 1) // 만약 숫자가 n+1개 만들어졋다면
    {
        long num = stol(s);
        // 최대값 최소값 갱신해주기.
        if (num > big)
        {
            big = num;
            banswer = s;
        }
        if (num < small)
        {
            small = num;
            sanswer = s;
        }
        return;
    }
    else
    {
        for (int i = 0; i <= 9; i++)
        { // 0~9까지 반복
            string c = to_string(i);
            if (s.length() == 0)
            {
                v[i] = 1;
                funct(step + 1, s + c);
                v[i] = 0;
            }
            else
            {
                if (v[i] == 1) // 이미 사용한 숫자라면 continue
                    continue;
                if (opt) // 왼쪽 방향
                {
                    int num = (s[step - 1]) - '0';
                    if (num < i) // 부등호 방향에 맞게 숫자를 걸러줘야 함.
                        continue;
                    v[i] = 1;
                    funct(step + 1, s + to_string(i));
                    v[i] = 0;
                }
                else
                { // 오른쪽
                    int num = (s[step - 1]) - '0';
                    if (num > i) // num은 추출한 숫자고, i는 넣을려눈 숫자. 부등오 방향에 맞게 해줘야함.
                        continue;
                    v[i] = 1;
                    funct(step + 1, s + to_string(i));
                    v[i] = 0;
                }
            }
        }
    }
}

 

😀느낀 점

• 문자열 -> 정수, 정수 -> 문자열로 계속 변환해서 코드를 작성해서 엄청 헷갈리고 보는 사람도 헷갈릴 거라고 생각한다.
  • 더 좋은 방법이 있을 거 같은데 문자열 다루는 건 정말 익숙하지가 않다.