백준 (5) 1322 X와 K

안 약한 부분이 있겠냐만 비트 쪽은 잘 모르는 분야라 일단 머리를 부딪혀서 풀어보았다

	int X, K;
	cin >> X >> K;
	// K번째 작은 숫자니까
	
	
	while (K != 0) {
		Y++;
		int result = X & Y;
		if (result == 0) K--;
	}

	cout << Y;

근데 이러면 하나씩 보는거라 시간초과가 당연히 나는 구조이다

그래서 다음 발상은 비트 연산자를 쭉쭉 펼쳐서 0과 1을 비교 구분해 밀어넣는 방식을 사용해봤다

vector<int> Xbits;
vector<int> Kbits;
vector<int> Ansbits;
int leftK = K;

while (X > 0) {
	Xbits.push_back(X & 1);
	X >>= 1;
}

while (K > 0) {
	Kbits.push_back(K & 1);
	K >>= 1;
}
int kIdx = 0;
int xSize = (int)Xbits.size();
int kSize = (int)Kbits.size();


for (int i = 0; ; i++) {
	int xbit = (i < xSize) ? Xbits[i] : 0;

	if (xbit == 1) {
		// X가 1인 자리는 Y는 무조건 0
		Ansbits.push_back(0);
	}
	else {
		// X가 0인 자리면 K의 현재 비트를 채움
		int kbit = (kIdx < kSize) ? Kbits[kIdx] : 0;
		Ansbits.push_back(kbit);
		if (kIdx < kSize) kIdx++; // K 비트 "소비"는 X가 0일 때만
	}

	// K 비트를 다 썼고, X의 최고비트까지도 처리 끝났으면 종료
	if (kIdx >= kSize && i + 1 >= xSize) break;
}

long long Y = 0;
long long bit = 1;
for (int i = 0; i < (int)Ansbits.size(); i++) {
	if (Ansbits[i]) Y += bit;
	bit <<= 1;
}

cout << Y << "\n";
return 0;

사실상 문제의 구조 자체가 X 비트의 0인 부분을 비집고 들어가는 구조였다

그렇기때문에 K를 비트화해서 X 비트가 1인 부분은 0, 0인 부분은 K의 첫 비트부터 끼워넣는 구조로 쌓아서 K만 끝까지 털면 답을 도출할 수 있었다

그렇게 하기 위해 X, K 비트를 풀고 Ans에 조건에 따라 쏙쏙 밀어넣는 구조로 코드를 짰다

음.. 비트 변환 방식에 대해서 공부가 좀 필요할 듯 싶다