문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 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인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

예제

예제 입력
2
< >

예제 출력
897
021

접근

  • 솔직히 알고리즘 분류를 보고 위상정렬을 쓰려고 했으나 위상정렬을 어떻게 써야 할 지 감이 오지 않았다…
  • k의 범위를 보니 순열로 풀 수 있을거라 생각했다. (worst case가 10!이기 때문에)

내가 생각한 풀이

  • next_permutation과 prev_permutation을 적절하게 사용하여 부등호의 조건에 맞는 답을 찾는다.
  • 최대값과 최소값을 찾아야 하기 때문에 최대값을 찾을 때는 prev_permutaion을 통해, 최소값을 찾을 때는 next_permutation을 통해 순차적으로 탐색을 하며 조건이 맞는 것이 있다면 그것을 정답에 넣어주고 break 해준다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
bool c[10] = {0, };
int k;
string a1 = "", a2 = "";
void input()
{
  cin>>k;
  for(int i = 0 ; i<k ; i++)
  {
    char t;
    cin>>t;
    if(t == '<') c[i] = 1;
    else c[i] = 0;
  }
}

bool check(vector<int> v)
{
  bool first = 0;
  for(int i = 0 ; i<v.size() - 1 ; i++)
  {
    bool a = v[i]>v[i+1];
    if(c[i] && a)
    {
      return 1;
    }
    if(!c[i] && !a)
    {
      return 1;
    }
  }
  return 0;
}

void check_next()
{
  bool flag = 0;
  for(int i = 0 ; i<10-k ; i++)
  {
  vector<int> v(k+1);
  for(int j = i ; j<=i+k ; j++)
  {
    v[j-i] = j;
  }
  do{
    if(!check(v))
    {
      for(int i = 0 ; i<v.size() ; i++) a1 += (v[i] + '0');
      flag = 1;
      break;
    }
  }while(next_permutation(v.begin(), v.end()));
  if(flag) break;
  }
}

void check_prev()
{
  bool flag = 0;
  for(int i = 0 ; i<10-k ; i++)
  {
  vector<int> v(k+1);
  for(int j = 9 - i ; j>=9-(i+k) ; j--)
  {
    v[9 - (j-i)] = j;
  }
  do{
    if(!check(v))
    {
      for(int i = 0 ; i<v.size() ; i++) a2 += (v[i] + '0');
      flag = 1;
      break;
    }
  }while(prev_permutation(v.begin(), v.end()));
  if(flag) break;
  }
}
int main(void)
{
  input();
  check_next();
  check_prev();
  cout<<a2<<"\n"<<a1;
  return 0;
}

생각하지 못했던 것

  • 문제를 풀고 나니 다른 사람에 비해 시간이 확실히 많이 걸렸다. 위상정렬을 통해 풀 수 있는 문제를 순열로 풀었기 때문이라 생각한다.
  • 솔직히 위상정렬 코드를 봤는데도 한 번에 이해하기가 쉽지 않았다. 부스트캠프 코딩테스트 끝나면 좀 더 자세히 봐야겠다.