SW Expert Academy 13428 숫자조작

문제 출처 (opens new window)

• 풀이 방법 및 배워야할 것:

  • 모든 조합을 다 찾아 최솟값과 최댓값을 찾음
  • 조합을 구하는데 DFS 방법을 썼는데 좀 더 간단히 할 수 있는 방법이 있을 것 같다.

• 풀이 코드 :

#include<iostream>
#include<string>
#include<vector>
#define MAX 9
 
using namespace std;
 
 
int n;
int m=2;
int a[MAX] = {0,};
bool c[MAX] = {0,};
vector <pair <int, int>> v;
 
void dfs(int num, int cnt)
{
    if(cnt == m)  //Only m ==2
    {
        v.push_back(make_pair(a[0],a[1]));
        return;
    }
    for(int i = num; i <= n; i++)
    {
        if(!c[i])  
        {
            c[i] = true;
            a[cnt] = i;
            dfs(i+1, cnt+1);
            c[i] = false;
        }
    }
}
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
    //freopen("sample_input.txt", "r", stdin);
    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        int tmp;
         
        cin >>tmp;
        string word1=to_string(tmp);
        n=word1.size();
        v.clear();
        dfs(1,0);
        int min=tmp;
        int max=tmp;
        //int number;
        // 모든 조합 다 계산
        for (int i=0; i<v.size();i++){
            string word2=to_string(tmp);
            char ch1=word2[v[i].first-1];
            char ch2=word2[v[i].second-1];
             
            if (v[i].first-1==0 && ch2=='0') continue;
            else {
                 
                word2[v[i].first-1]=ch2;
                word2[v[i].second-1]=ch1;   
                int number=stoi(word2);
                //cout << v[i].first << " " << v[i].second << " " << number << "\n";
                if (number < min){
                        min=number;
                }
                if (number > max){
                        max=number;  
                }   
            }
         
        }
 
        cout <<  "#" << test_case << " "<< min << " " <<  max  << "\n";
 
    }
    return 0; 
}