Algorithms

[LeetCode] 190. Reverse Bits 문제 풀이 (Java)

작은별._. 2026. 2. 17. 16:51
728x90
반응형

✔️ 오늘의 리트코드 공부 기록 – Reverse Bits

문제 요약 (Reverse Bits)

32비트 정수 n이 주어졌을 때,
비트(bit) 순서를 거꾸로 뒤집은 값을 반환하라.
(0번째 비트 ↔ 31번째 비트)

문제 링크: Reverse Bits

🤔 처음 떠올린 아이디어

처음에는 단순하게 생각했다.

“이진수로 바꾼 다음에 뒤집고, 다시 숫자로 만들면 되지 않을까?”

그래서 자연스럽게
Stack에 비트를 넣고(pop해서) 뒤집는 방식이 떠올랐다.

💡 핵심 깨달음: 숫자 뒤집기가 아니라 “32칸 고정 비트” 뒤집기다

여기서 중요한 함정이 있다.

예를 들어 n = 2라면 이진수는 10이지만,
이 문제는 32비트 전체를 본다.

즉 실제 형태는:


00000000000000000000000000000010

이걸 뒤집으면:


01000000000000000000000000000000

👉 그래서 while(n > 0)처럼 “0 될 때까지” 뽑으면
leading zero가 사라져서 오답이 된다.

🧠 무엇을 판단해야 할까?

이 문제의 핵심 질문은 하나다.

“지금 비트를 몇 개 처리했지?”

즉, 무조건 32번 처리해야 한다.
(값이 0이 됐는지 여부와 상관 없음)

🔒 왜 Java에서는 >>>를 쓰는가?

Java의 int는 signed(부호 있는) 32비트다.

  • >> : 오른쪽 shift 시 부호 비트(sign bit)를 유지
  • >>> : 오른쪽 shift 시 무조건 0으로 채움 (논리 시프트)

비트 문제에서는 “숫자 의미”가 아니라 “비트 패턴”을 다루므로
안전하게 >>>를 쓰는 게 정석이다.

(이번 constraints가 양수라면 >>도 동작하긴 하지만, 습관은 >>>가 맞다.)

🔁 스택 풀이에서의 불변식

“스택에는 항상 32개의 비트가 들어가고,
pop하면 정확히 reversed order로 나온다.”

그래서:

  • 32번 push (LSB부터)
  • 32번 pop (MSB부터 재조립)

코드 (Java) — 스택 방식

import java.util.Stack;

class Solution {
    public int reverseBits(int n) {
        Stack<Integer> stk = new Stack<>();

        // 32비트 모두 push
        for (int i = 0; i < 32; i++) {
            stk.push(n & 1);   // 마지막 비트
            n >>>= 1;          // 논리 시프트로 안전하게 이동
        }

        int result = 0;
        int mul = 1;

        // pop 하면서 재조립
        while (!stk.isEmpty()) {
            result += stk.pop() * mul;
            mul <<= 1;
        }

        return result;
    }
}

📈 시간 / 공간 복잡도

  • 시간: 32번 push + 32번 pop → O(1) (고정)
  • 공간: 스택 32칸 → O(1) (고정)

🚀 최적 풀이 (공간복잡도 O(1))

Stack 없이
비트 연산만으로 해결할 수 있다.

핵심은:

마지막 비트를 꺼내서
결과를 왼쪽으로 밀고 붙인다.
이 과정을 32번 반복한다.

코드 (Java) — Bit Manipulation 방식

class Solution {
    public int reverseBits(int n) {
        int result = 0;

        for (int i = 0; i < 32; i++) {
            result <<= 1;      // 결과를 왼쪽으로 한 칸 이동
            result |= (n & 1); // n의 마지막 비트를 붙임
            n >>>= 1;          // 논리 시프트 (안전하게 이동)
        }

        return result;
    }
}

📈 시간 / 공간 복잡도

  • 시간: 32번 고정 반복 → O(1)
  • 공간: 추가 자료구조 없음 → O(1)

🧠 왜 이게 더 좋은가?

Stack 방식은:

  • push 32번
  • pop 32번
  • 스택 공간 사용

하지만 Bit 방식은:

  • 한 번의 루프
  • 추가 메모리 없음

📝 이번 문제에서 얻은 깨달음

  • 이 문제는 “이진수 문자열 뒤집기”가 아니다.
  • 32칸 고정 배열을 뒤집는 문제다.
  • 따라서 while(n > 0) 같은 조건은 위험하다.
  • Java에서는 비트 패턴을 안전하게 밀기 위해 >>>를 쓰는 게 정석이다.

👉 결국 중요한 한 문장

Reverse Bits는 값이 아니라 “32비트 패턴”을 뒤집는 문제다.

728x90
반응형