알고리즘 :: 백준 :: 시뮬레이션 :: 1039 :: 교환

Embedded June·2021년 8월 4일
0

알고리즘::백준

목록 보기
107/109

1. 문제 분석하기

1.1. 문제 의도

  • 시뮬레이션 문제입니다.

2. 문제 해결하기

  • 이 문제는 간단하지만, 숨겨진 예외조건을 찾기 까다롭습니다.
    연산을 K번 할 수 없는 경우 -1을 출력한다는 말을 이해하기 어렵기 때문입니다.
    1. N = 1,000,000인 경우, 연산을 수행할 수 없습니다.
    2. N = 1~9 또는 N = 10, 20, 30, …, 90인 경우, 연산을 수행할 수 없습니다.
  • 왜냐하면, 연산을 1회 수행할 때 무조건 맨 앞이 0이 돼서 진행할 수 없기 때문입니다.
  • 연산을 수행하다보면 중복되는 수가 등장합니다.
    • image-20210804112916001.
    • 중복되는 수는 기하급수적으로 증가해서 메모리 초과를 유발합니다.
      반드시 중복을 제거해줘야 합니다.
    • 수의 범위가 커서 bool 타입 배열로는 판단이 힘듭니다. 따라서 unordered_set 자료구조를 이용해서 중복을 자동으로 제거하도록 합니다.
  1. queue자료구조를 이용해서 이번 loop에 queue안에 들어있는 요소들의 교환조합을 구합니다.
  2. 모든 교환조합은 set에 집어넣고 중복을 제거합니다.
  3. 다음 loop로 가기 전에 set에 남아있는 요소들을 queue에 다시 넣습니다.
  • 이때 연산을 K번 수행하기 전에 queue가 비어버리면 K번 진행할 수 없게되므로 -1을 출력합니다.

3. 코드

#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>
using namespace std;

int main() {
    	ios::sync_with_stdio(false), cin.tie(NULL);
	int K, answer = 0;
	string N;
	cin >> N >> K;
	
	// 예외처리 :: 한자리, 끝이 0인 두자리, 백만
    	if (N == "1000000") { cout << N; return 0; }
    	if (N.size() == 1) { cout << -1; return 0; }
    	if (N.size() == 2 && N[1] == '0') { cout << -1; return 0; }
	
	queue<string> q;
	q.push(N);
	
	while(!q.empty() && K--) {
		unordered_set<string> s;
		
		int cnt = q.size();
		while(cnt--) {
			string num = q.front();
			q.pop();
			// 모든 조합을 구하고, set에 삽입해서 중복 제거.
			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]);
					if (s.find(num) == s.end()) {
						if (K == 0) answer = max(answer, stoi(num));
						q.push(num);
						s.insert(num);
					}
					swap(num[i], num[j]);
				}
		}
	}
    	// 여기서 queue에서 answer를 구하려고 하면 메모리 초과.
	if (K >= 0) cout << -1;
	else cout << answer;
}

4. 결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글