백준 1039 - 교환(C++)

문제 링크입니다 https://www.acmicpc.net/problem/1039

1039번: 교환

문자열을 사용한 BFS 문제였습니다

 

문제 조건

출력 예시

 

N을 입력받아서 K번 수를 바꾼뒤 최댓값을 출력하는 문제입니다.

N을 자릿수를 바꿔야하기에 string으로 선언해서 문자열로 사용했습니다. 

 

문제 접근 방법

1. 수의 위치를 바꿀 수 없을 경우를 찾아서 -1를 return 해준다.

2. 수를 K번만큼 바꾼 뒤, 최댓값을 찾아서 출력해준다.

 

 

문제 접근 방법 - 1번

	if (N.size() == 1 || (N.size() == 2 && stoi(N) % 10 == 0)) {
		cout << "-1";
		return 0;
	}

수를 바꿀수 없는 경우는 2가지입니다.

1. 자릿수가 1자리일 경우.

2. 2자리이지만, 1의 자리가 0인 경우.

위 2가지 경우일 때, -1를 return 해주면 됩니다.

 

 

문제 접근 방법 - 2번

int bfs() {
	queue<pair<string, int>> q;
	q.push(make_pair(N, 0));
	string maxi = "0";
	check[stoi(N)][0] = 1;
	while (!q.empty()) {
		string x = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (cnt == K) {
			if (maxi < x) maxi = x;
		}
		else if (cnt < K) {
			for (int i = 0; i < x.size(); i++) {
				for (int j = i + 1; j < x.size(); j++) {
					string xx = x;
					swap(xx[i], xx[j]);
					if (xx[0] == '0' || check[stoi(xx)][cnt+1] == 1) {
						continue;
					}
					q.push(make_pair(xx, cnt + 1));
					check[stoi(xx)][cnt + 1] = 1;
				}
			}
		}
	}
	return stoi(maxi);
}

string으로 선언했기에 자릿수 바꾸는 것이 쉬워집니다. swap(a,b)를 통해서 자릿수를 바꿔주면 됩니다.

check[N][K] 배열은 N의 수를 만드는데 K번 위치를 바꿨다는 의미입니다. 

stoi(N)을 할 경우 string을 int로 바꿔주는 역할을 합니다 - #include<string> 선언은 꼭 해줍시다.

 

수를 바꿨을때, 앞자리가 0으로 시작하거나, 이전에 이미 만들어졌던 수인 경우, 확인할 필요가 없으니, continue를 해줬습니다. 이외의 경우에는 queue에 넣어줘서 탐색을 해줬습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>

using namespace std;

string N;
int K;
int check[1000001][11];

int bfs() {
	queue<pair<string, int>> q;
	q.push(make_pair(N, 0));
	string maxi = "0";
	check[stoi(N)][0] = 1;
	while (!q.empty()) {
		string x = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (cnt == K) {
			if (maxi < x) maxi = x;
		}
		else if (cnt < K) {
			for (int i = 0; i < x.size(); i++) {
				for (int j = i + 1; j < x.size(); j++) {
					string xx = x;
					swap(xx[i], xx[j]);
					if (xx[0] == '0' || check[stoi(xx)][cnt+1] == 1) {
						continue;
					}
					q.push(make_pair(xx, cnt + 1));
					check[stoi(xx)][cnt + 1] = 1;
				}
			}
		}
	}
	return stoi(maxi);
}

void solve() {
	int ans = bfs();
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	if (N.size() == 1 || (N.size() == 2 && stoi(N) % 10 == 0)) {
		cout << "-1";
		return 0;
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!