백준(BOJ) 2529번 부등호

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

입력

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

출력

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

 

나의 풀이:

완전탐색으로 풀어보았다.

부등호 2개라면 2개를 기준으로 처음 0~9 고르고 / 부등호 /  (앞에 부등호 보고) 0~9 고르고 / 부등호 / (앞에 부등호 보고) 0~9 고르고 를 결정하였다.

완전 탐색

#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

using namespace std;

int k;

char sign[10];

string ans;

vector<string> result;

bool visited[10];

void solve(string ans, int cnt)

{

if (cnt == k) {   // cnt가 k가 됬다면 만족한 답을 result 벡터에 넣어준다. 

result.push_back(ans);

return;

}

if (sign[cnt] == '<') //  부등호가 < 라면

{

int temp = ans[cnt] - '0'; // 바로 전 숫자를 temp에 기억해 둔 후에

for (int i = 0; i < 10; ++i) {

if (temp >= i) // temp보다 i가 작다면 continue 한다.

continue;

if (!visited[i]) {  //temp보다 클 경우 아직 쓰지않은 숫자라면

visited[i] = true;

ans += (i + '0');

solve(ans, cnt + 1); // 숫자를 추가해주고 다시 재귀 함수 돌린다.

visited[i] = false;

ans.pop_back();

}

}

}

else

{

int temp = ans[cnt] - '0';

for (int i = 0; i < 10; ++i) {

if (temp <= i)

continue;

if (!visited[i]) {

visited[i] = true;

ans += (i + '0');

solve(ans, cnt + 1);

visited[i] = false;

ans.pop_back();

}

}

}

}

int main()

{

cin >> k;

for (int i = 0; i < k; ++i)

{

cin >> sign[i];

}

for (int i = 0; i < 10; ++i)

{

if (!visited[i]) {

visited[i] = true;

ans += (i + '0');

solve(ans, 0);  // 0부터 ~ 9까지 한 숫자를 먼저 고른다.

visited[i] = false;

ans.pop_back();

}

}

cout << result[result.size() - 1] << endl; //0부터 완전탐색으로 해왔기에 정렬이 되어있다.

cout << result[0] << endl;

return 0;

}