BOJ 11966 2의 제곱인가?

By kuper0201

Published in 알고리즘

2023-05-25

1 min read

문제

입력

풀이

문제

BOJ 11966 2의 제곱인가? 바로 가기

자연수 N이 주어졌을 때, 2의 제곱수면 1을 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 $N(1 ≤ N ≤ 2^{30})$ 이 주어진다.

풀이

해당 문제는 자연수 N이 주어졌을 때 2의 제곱수인지 아닌지 판별하라는 문제이다.

최대 $2^{30}$ 까지의 자연수가 입력 될 수 있으므로 이는 32Bit 정수형으로 표현 가능하다.

따라서 $2^{K}$ (0 ≤ K ≤ 30)을 연산하여 N과 같은지 비교하여 판별하면 된다.

이 때, 1을 좌측으로 K번 Shift하면 $2^{K}$ 과 같다는 특징을 이용하면 곱셈 연산을 이용할 때 보다 빠른 처리가 가능하다.

1을 Shift연산한 결과는 아래의 표와 같다.

연산	비트	결과
1 << 0	00000001	1
1 << 1	00000010	2
1 << 2	00000100	4
1 << 3	00001000	8
1 << 4	00010000	16
1 << 5	00100000	32

코드 보기(Java)

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean flag = false;

        // 정수 입력
        int N = Integer.parseInt(br.readLine());
        for(int i = 0; i < 31; i++) {
            // Shift연산 결과와 정수 비교
            if(N == (1 << i)) flag = true;
        }

        if(flag) System.out.println(1);
        else System.out.println(0);
    }
}

코드 보기(C++)

#include <iostream>

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define endl '\n'

using namespace std;

int main() {
    fastio;
    
    bool flag = false;

    // 정수 입력
    int N;
    cin >> N;
    
    for(int i = 0; i < 31; i++) {
        // Shift연산 결과와 정수 비교
        if(N == (1 << i)) flag = true;
    }
    
    if(flag) cout << 1 << endl;
    else cout << 0 << endl;
    
    return 0;
}

코드 보기(Kotlin)

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    var flag = false

    // 정수 입력
    var N = readLine().toInt()
    for(i in 0 until 31) {
        // Shift연산 결과와 정수 비교
        if(N == (1 shl i)) flag = true
    }

    if(flag) println(1)
    else println(0)
}

코드 보기(Python)

from sys import stdin

def main():
    flag = False

    # 정수 입력
    N = int(stdin.readline())
    for i in range(0, 31):
        # Shift연산 결과와 정수 비교
        if N == (1 << i):
            flag = True

    if flag:
        print(1)
    else:
        print(0)

if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    var flag = false

    // 정수 입력
    var N = Int(readLine()!)!
    for i in 0..<31 {
        // Shift연산 결과와 정수 비교
        if N == (1 << i) {
            flag = true
        }
    }

    if flag {
        print(1)
    } else {
        print(0)
    }
}

main()