/ ALGORITHM

Baekjoon 알고리즘 - 1039번 교환 c++

1039 교환 문제

문제 접근 법

정수 N을 입력 받았을 때 K번의 횟수를 사용하여 각 자리에 있는 숫자의 위치를 바꾸는 문제이다. 자리를 바꿀 때의 조건은 i < j 여야 한다!!

문제에 대한 알고리즘은 이중 for문을 사용하여 각 자리에 있는 숫자를 바꾸고 이를 큐에 넣어 계속해서 확인한다.

이렇게 단순하게 된다면 메모리 초과 문제를 맞이할 것이다. 이를 해결하기 위해 set 자료구조를 사용하여 이미 나온 숫자에 대해 큐에 넣지 않도록 하여 메모리 낭비를 막을 수 있다. 그리고 while문 1번 실행시 큐의 크기 만큼 반복해줘야 메모리 초과를 막을 수 있다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
int answer = -1;
int main() {
	string str; int k;
	cin >> str >> k;

	queue<pair<int, string>> q;
	q.push(make_pair(0, str));

	while (!q.empty()) {
		int qsize = q.size();

		// set 자료구조를 사용하여 이미 나온 숫자를 큐에 넣지 않도록 한다.
		set<string> visit;

		// 이게 중요함!!!
		// 현재 단계에서의 큐 사이즈 만큼 반복문
		for (int l = 0; l < qsize; l++) {
			string num = q.front().second;
			int cnt = q.front().first;
			q.pop();
			if (cnt == k) {
				answer = max(answer, stoi(num));
				continue;
			}
			for (int i = 0; i < num.size() - 1; i++) {
				for (int j = i + 1; j < num.size(); j++) {
					if (i == 0 && num[j] == '0') continue;
					swap(num[i], num[j]);
					// set를 통해 이미 나온 수의 중복을 피한다
					if (visit.find(num) == visit.end()) {
						visit.insert(num);
						q.push(make_pair(cnt + 1, num));
					}
					swap(num[i], num[j]);
				}
			}

		}
	}
	cout << answer;
}