[BOJ/백준 12025/C++] 장난꾸러기 영훈

https://www.acmicpc.net/problem/12025

 

[ 문 제 ]

- 희현이는 인터넷 ID를 만들 때 주로 쓰는 비밀번호가 있다. 하지만 이 비밀번호는 너무 길어서 희현이는 항상 쪽지에 적어 다니면서 확인을 한다.

- 하지만 장난꾸러기 영훈이는 이 쪽지를 가져가 1들 중 몇 개를 6로, 6들 중 몇 개를 1로 바꾸고 2들 중 몇 개를 7로 7들 중 몇 개를 2으로 바꾸는 장난을 쳤다. 따라서 영훈이가 장난쳐놓은 비밀번호 무용지물이 되었다.

- 왜냐하면 1이라고 쓰여 있어도 1 또는 6일수가 있고, 또한 6이라 쓰여 있어도 1 또는 6일수가 있다. 2과 7에서도 마찬가지이다.

- 하지만 희현이는 이러한 상황에 대비하여 비밀번호에 대한 한 가지 단서를 만들어 놓았는데 이는 다음과 같다.

- 비밀번호 수열의 숫자 중 1과 6을 모두 1로, 2와 7을 모두 2으로 바꾼 숫자와 1과 6을 모두 6으로 2과 7을 모두 7로 바꾼 숫자 사이에 가능한 경우를 모두 사전순으로 나열한 다음 그 중 k번째가 비밀번호이다.

- 따라서 이 단서를 통해 멘붕에 빠진 희현이를 도와 비밀번호를 다시 찾아보자.

 

[ 문 제 조 건 ]

- 첫째 줄에 영훈이가 장난을 쳐서 바뀐 비밀번호가 주어진다. (비밀번호의 길이는 60자까지이고 첫 숫자가 0일수도 있다.)

- 둘째 줄에 숫자 k가 주어진다. (k ≤ 2^63 – 1)

- 첫째 줄에 원래 비밀번호를 출력한다.

- 만약 k번째 비밀번호가 존재하지 않으면 -1을 출력한다.

 

[ 문 제 풀 이 ]

이번 문제는 주어진 비밀번호의 6을 모두 1로 바꾸고, 7을 2로 바꾼 다음 다시 1->6으로 2->7로 바꿔 나가면서 (사전순) K번째 수열을 찾으면 되는 문제다.

 

이 문제를 모든 경우의 수를 다 계산하면서 K번째를 구한다면 참 편하겠지만 경우의 수가 너무 많아지는 입력이 존재한다. 

 

따라서 이번 문제는 비트마스킹을 이용하여 K번째 수를 구할 수 있다.

 

먼저, K를 이진수로 표현해준다. 예를들어 들어오는 입력이 1234567890이고, K가 4라면 100(2)가 된다.

 

입력에서 1,2,6,7의 위치를 표현한 2진수와 대응시켜 생각해준다.

 

이게 무슨말이냐 입력에서 존재하는 1,2,6,7의 문자열에서의 위치는 0, 1, 5, 6이 된다. 

 

위에서 K를 이진수로 바꾸면 0100(2) 라는 것을 미리 구해놨고, 맨 앞의 0은 0번째 위치, 그 다음 1은 1번째 위치, 그 다음 0은 5번째 위치, 마지막 0은 6번째 위치와 대응시켜주고, 1이면 6or7, 0이면 1or2로 숫자로 바꾸어주면 K번째 수를 구할수 있게된다.

 

다른 K로 생각해보면

 

K = 1 , 0001(2) , 1217 - > 1234517890

K = 2,  0010(2) , 1262 - > 1234562890

K = 3,  0011(2) , 1267 - > 1234567890

 

이렇게 생각할 수 있다.

 

이때 주의 할 점은 입력으로 들어온 K에서 1을 빼줘야 정확한 값을 구할 수 있다.

왜냐하면 입력으로 K가 1일 들어왔을 때 첫번째 라는 의미를 가지지만 이진수로 표현했을때는 0000(2)이 첫번째를 의미하므로 1을 빼줘야 한다.

 

그리고 구하고자 하는 K번째가 입력으로 들어온 비밀번호에서 2^(1,2,6,7의 갯수)보다 크면 생각할 수 있는 경우의 수보다 많은 번째를 구하는 것이기 때문에 -1을 출력해주면 된다.

 

[ 소스 코드 ]

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string input;
	ll k;
	cin >> input >> k;

	vector<ll> pos;
	for (ll i = 0; i < input.size(); i++)
	{
		if (input[i] == '1' || input[i] == '6' || input[i] == '2' || input[i] == '7')
		{
			if (input[i] == '6') input[i] = '1';
			else if (input[i] == '7') input[i] = '2';
			pos.push_back(i);
		}
	}

	//불가능
	if (pow(2, pos.size()) < k)
	{
		cout << -1 << "\n";
		return 0;
	}

	k--;
	ll i = pos.size() - 1;
	while (k != 0)
	{
		ll value = k % 2;
		k /= 2;

		if (input[pos[i]] == '2' || input[pos[i]] == '7')
		{
			if (value == 0) input[pos[i]] = '2';
			else input[pos[i]] = '7';
		}
		else if (input[pos[i]] == '1' || input[pos[i]] == '6')
		{
			if (value == 0) input[pos[i]] = '1';
			else input[pos[i]] = '6';
		}
		i--;
	}
		
	cout << input;
}

 

굳