[G5] 백준 12025번 장난꾸러기 영훈 C++ 비트마스킹

리뷰

 

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

설정할 수 있는 비밀번호를 오름차순으로 정렬했을때 k번째 비밀번호를 출력하는 문제

 

 

전역 변수

• s : 영훈이가 장난을 쳐서 바뀐 비밀번호를 저장할 변수
• k : 원래 비밀번호의 순서를 저장할 변수

 

함수

없음

 

 

문제풀이

1. s, k값을 입력 받고, 변수 n을 s의 크기로 초기화한다.
2. 정수형 벡터 pos를 초기화한다.
3. s를 순회하며 현재 문자가 '6'이라면 '1'로, '7'이라면 '2'로 변경한다.
4. 변경 후 현재 문자가 '1'이거나 '2'라면 pos에 인덱스를 push한다.
5. 변수 m을 pos의 크기로 초기화한다.
6. 만약 k가 1을 m만큼 왼쪽으로 시프트한 값보다 크다면 -1을 출력하고 조기 리턴한다.
7. k를 1만큼 감소시키고, m번의 for문을 개행한다.
8. 1을 m-1-i만큼 왼쪽으로 시프트한 값과 k의 비트가 모두 1이라면 아래 로직을 수행한다.
9. s[pos[i]]를 기존 s[pos[i]]가 '1'이라면 '6'으로, 아니라면 '7'로 변경한다.
10. s에 저장된 최종 값을 출력한다.

 

트러블 슈팅

1. 인덱스와 비트를 뒤에서부터 순회하여 LSB형식으로 구현되어 39%에서 WA를 받았다.
2. 인덱스를 앞에서부터 관리하되, 비트 연산을 m-1-i로 순회함으로 로직을 변경하여 AC를 받았다.

 

참고 사항

1. 초기 문자열에서 '6', '7'을 모두 '1', '2'로 변경해주어 비트가 모두 0인상태로 만들어주었다.
2. k를 1만큼 감소시켜 0-based-indexing 구조로 변경해주었다.
3. k의 m-1-i번째 비트가 켜져있을 경우 pos[i]번째 인덱스의 값을 전환시켜주었다.

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;

string s;
long long k;

int main() {
	cin >> s >> k;

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

	
	int m = pos.size();
	if (k > (1ll << m)) {
		cout << -1;
		return 0;
	}

	--k;
	for (int i = 0; i < m; ++i) {
		if (k & (1LL << (m - 1 - i))) {
			s[pos[i]] = (s[pos[i]] == '1') ? '6' : '7';
		}
	}

	cout << s;
}