[BOJ/백준] 2529 부등호

● [문제번호 2529] 부등호

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

2529번: 부등호

 

● 알아야 할 것

: DFS

: 재귀

: vector 자료구조와 메소드

 

 

● 풀이 과정

: [530 - 브루트 포스 - 재귀] 문제집에 있는 동일한 문제

 

: DFS의 기본 구현 형태에서 크게 벗어나지 않는다.

 

: 맨 앞자리의 숫자는 그대로 저장하고

다음 숫자부터 부등호 조건에 맞는 숫자들을 저장한다.

그리고 부등호는 K개이므로 숫자는 K+1 개 인 경우,

최대 숫자인지, 최소숫자인지 확인 후 저장 여부를 결정한다.

 

 

● 주의 할 것

: 맨 앞자리의 숫자인 경우, 최초의 숫자배열인 경우 와 같이

예외적인 부분에 대해 고려해서 구현해야한다.

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// sign : 부등호 저장
// num : 각 경우의 숫자배열 저장
// visited : num 배열에 들어있는 숫자(index)인지 확인
// maxNum : 가장 큰 숫자배열 저장
// minNum : 가장 작은 숫자배열 저장
char sign[11];
vector<int> num;
bool visited[11];
vector<int> maxNum, minNum;
int K;

// 숫자배열 만들기
void makeNumber(int cnt)
{
    // 숫자배열에 숫자가 K+1 개 인 경우 (∵ 부등호는 K개 이므로)
    if(num.size() == K + 1)
    {
        // 최초의 숫자 배열인 경우
        if(maxNum.size() == 0 && minNum.size() == 0)
        {
            for(int i = 0; i < num.size(); i++)
            {
                maxNum.push_back(num[i]);
                minNum.push_back(num[i]);
            }
        }
        else
        {
            // 최대의 숫자배열인지 확인
            int maxflag = 0;
            for(int i = 0; i < num.size(); i++)
                if(maxNum[i] < num[i])
                {
                    maxflag = 1;
                    break;
                }
            if(maxflag == 1)
                for(int i = 0; i < num.size(); i++)
                    maxNum[i] = num[i];
            
            // 최소의 숫자배열인지 확인
            int minflag = 1;
            for(int i = 0; i < num.size(); i++)
                if(minNum[i] < num[i])
                {
                    minflag = 0;
                    break;
                }
            if(minflag == 1)
                for(int i = 0; i < num.size(); i++)
                    minNum[i] = num[i];
        }
        
        return ;
    }
    
    // 0부터 9까지 순서대로 탐색
    for(int i = 0; i <= 9; i++)
    {
        // num 배열에 없는 숫자인 경우
        if(!visited[i])
        {
            // 부등호의 조건에 만족하는 지
            // 1. num 배열에 체크인
            // 2. num 배열에 저장
            // 3. 재귀
            // 4. num 배열에서 제거
            // 5. num 배열에서 체크아웃
            if(sign[cnt] == '<' && num.back() < i)
            {
                visited[i] = true;
                num.push_back(i);
                makeNumber(cnt + 1);
                num.pop_back();
                visited[i] = false;
            }
            else if(sign[cnt] == '>' && num.back() > i)
            {
                visited[i] = true;
                num.push_back(i);
                makeNumber(cnt + 1);
                num.pop_back();
                visited[i] = false;
            }
            // 맨 앞자리의 숫자인 경우
            else if(num.size() == 0)
            {
                visited[i] = true;
                num.push_back(i);
                makeNumber(cnt + 1);
                num.pop_back();
                visited[i] = false;
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> K;
    
    // 부등호 저장
    for(int k = 1; k <= K; k++)
        cin >> sign[k];
    
    // num 배열에 0개의 숫자가 있으므로 0부터
    makeNumber(0);
    
    // maxNum 과 minNum 의 숫자 출력
    for(auto element : maxNum)
        cout << element;
    cout << "\n";
    for(auto element : minNum)
        cout << element;
    
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [521 - 브루트 포스 - 순열 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	2529	부등호	https://pirateturtle.tistory.com/294
2	1339	단어 수학	https://pirateturtle.tistory.com/295
3	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/296
4	14889	스타트와 링크	https://pirateturtle.tistory.com/297