[백준] 1039번_교환 C++

14 Apr 2023 in Study on Coding Test

완전탐색인줄 알았더니 알고보니 큐를 쓰는거였던 문제.

정답제출코드

#include <iostream>
#include <string>
#include <queue>
#include <set>

using namespace std;

string N;
int K;
int num[7];
queue<string> q;

void swap(string& s, int a, int b)
{
    char temp;
    temp = s[a];
    s[a] = s[b];
    s[b] = temp;

    return;
}

int m_max(int a, string b)
{
    int B = stoi(b);

    if (a > B)
        return a;
    else
        return B;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;

    q.push(N);

    for (int i = 0; i < K; ++i)
    {
        set<string> s;
        size_t qsize = q.size();

        for (size_t j = 0; j < qsize; ++j)
        {
            string str = q.front();
            q.pop();

            if (s.count(str) != 0)
                continue;
            s.insert(str);

            for (size_t k = 0; k < str.length()-1; ++k)
            {
                for (size_t l = k+1; l < str.length(); ++l)
                {
                    if (!(k == 0 && str[l] == '0'))
                    {
                        swap(str, k, l);
                        q.push(str);
                        swap(str, k, l);
                    }
                }
            }
        }
    }

    int ans = -1;
    while(!q.empty())
    {
        ans = m_max(ans, q.front());
        q.pop();
    }

    cout << ans;

    return 0;
}

완전탐색이라고 했지만 도저히 감이 잡히지 않아서

참고링크를 참고해서 풀었다.

N을 swap하기 편하게 string으로 받은 뒤에 모든 경우의 수를 세트와 큐에다가 보관하는 식으로 구현하였다.

세트는 중복되는 경우를 방지하기 위해서 설치하였다.

즉, 세트 안에 있는 어떤 경우가 이미 있는 경우라면 큐에다가 넣는 과정을 생략하는 것이다.

만일 연산이 불가능하다면 ans는 -1로 그대로 남을 것이기 때문에 -1을 출력할 수 있을 것이고,

큐에 값이 들어갔다면 연산을 실시했다는 것이다.

이렇게 해서 마지막에 가장 큰 경우를 출력하도록 구현하였다.