문제

문제 링크

문제 접근

  • 이 문제는 위상정렬을 이용해서 풀 수 있다.
  • 부등호를 이용해서 두 숫자들간에 종속 관계를 확인하고 incoming edge를 저장해둔다.
  • 이때 incoming edge는 제일 큰 수와 제일 작은 수를 찾기 위해 2개 준비했다.
  • 큰 놈을 찾을 때는 맨처음부터 incoming edge를 확인하면서 0인 위치를 찾아서 9부터 하나씩 넣어준다.
  • 그리고 해당 위치에 종속성이 있는 애들을 찾아서 in을 줄여준다. 이를 반복한다.
  • 작은 놈을 찾을 떄는 다 똑같은데 뒤에서 부터 0을 찾아서 넣어주고 넣어주는 값은 n부터 이다.(n이 2면 2부터 0까지 넣어준다.)

코드

#include <cstdio>
#include <vector>
using namespace std;
int n, in1[10], in2[10], MIN[10], MAX[10];
char c;
vector<int> e[10];
int main(){
    scanf("%d ", &n);
    for(int i = 0; i < n; i++){
        c = getchar();
        if(c == '<'){
            e[i+1].push_back(i);
            in1[i]++, in2[i]++;
        }
        else {
            e[i].push_back(i+1);
            in1[i+1]++, in2[i+1]++;
        }
        getchar();
    }
    
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            if(!in1[j]){
                MAX[j] = 9 - i, in1[j] = 1;
                for(int k = 0; k < e[j].size(); k++) in1[e[j][k]]--;
                break;
            }
        }
        for(int j = n; j >= 0; j--){
            if(!in2[j]){
                MIN[j] = n - i, in2[j] = 1;
                for(int k = 0; k < e[j].size(); k++) in2[e[j][k]]--;
                break;
            }
        }
    }
    for(int i = 0; i <= n; i++) printf("%d", MAX[i]);
    printf("\n");
    for(int i = 0; i <= n; i++) printf("%d", MIN[i]);
}

느낀점

  • 집중력이 흐트러져서 문제를 구현해내는데까지 시간이 오래걸렸다! 그래도 방법을 생각해낸 것에 기쁘다!