[Goorm] 파손된 램 (Java)

 

구름LEVEL

 

이 문제는 2의 제곱수의 용량을 가진 램 중에서 파손이 되어 2의 제곱수의 용량을 가지지 않는 램의 수와 번호를 출력하는 문제입니다. 비트 마스크를 이용하면 되게 간단한 문제인데 할 줄 몰라서 열심히 찾아봤네요.. 😂😂

 

2의 n제곱 수를 2진수로 나타내면

2의 0 제곱 : 1 → 1

2의 1 제곱 : 2 → 10

2의 2 제곱 : 4 → 100

2의 3 제곱 : 8 → 1000

과 같이 1로 시작하여 오른쪽을 모두 0으로 채우는 형태입니다.

 

만약 2의 제곱에서 1을 뺀 수를 2진수로 나타내면

2의 0 제곱 - 1 : 0 → 0

2의 1 제곱 - 1 : 1 → 1

2의 2 제곱 - 1 : 3 → 11

2의 3 제곱 - 1 : 7 → 111

과 같이 0 제곱을 제외하고는 모두 1로 이루어진 것을 확인할 수 있습니다.

 

이 사실을 이용하면 임의의 수 n이 2의 제곱수인지 판별이 가능해요! 😎😎

n과 n - 1을 비트 연산자 &를 이용해서 계산했을 때 2의 제곱수이면 결과가 0이 나옵니다.

(& 연산자는 두 수 모두 1이어야 결괏값에 1이 속하게 되기 때문입니다)

즉, n이 2의 제곱수이면 아래와 같은 결과를 얻을 수 있다는 의미입니다.

& 연산 결과

이러한 사실을 적용하여 다음과 같이 문제를 풀 수 있습니다.

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 램 개수
		ArrayList<Integer> error = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++){
			int ram = Integer.parseInt(st.nextToken());
			if ((ram & (ram - 1)) != 0) // 2의 제곱이 아닌 경우
				error.add(i);
		}
		
		int errorLen = error.size();
		if (errorLen > 0) {
			System.out.println(errorLen);
			for (int i = 0; i < errorLen; i++)
				System.out.printf("%d ", error.get(i));
		}
		else
			System.out.println(errorLen);
	}
}

 

---

🔗 Reference

👉 2의 n제곱 수인지 판별하기