Softeer 연습문제 - 전광판

Published on May 18, 2024

해당 포스팅에서는 Softeer 전광판 문제를 활용하여 비트연산에 대해서 알아보고자 합니다.

1. 비트연산이란?

알고리즘 문제를 풀 때 활용할 수 있는 테크닉 중 하나로, 다양한 타입의 변수를 bit로 생각하여 연산을 진행하는 방법입니다

2. 비트연산의 종류

AND (&)

AND 연산은 자바에서 ‘&’라는 연산자로 사용됩니다.
AND 연산은 대상이 되는 비트들이 모두 1이어야만 1을 return합니다.
이외의 경우에는 모두 0을 return 합니다.

OR (|)

OR 연산은 자바에서 ‘|’라는 연산자로 사용됩니다.
OR 연산은 대상이 되는 비트들 중에 하나라도 1이 존재한다면 1을 return합니다.
즉, 대상 비트들이 모두 0일 경우에만 0을 return합니다.

XOR (^)

XOR 연산은 자바에서 ‘^’라는 연산자로 사용됩니다.
XOR 연산은 대상이 되는 두 비트가 같으면 0, 다르면 1을 return합니다.

Shift (», «)

Shift 연산은 개발자가 비트를 이동시키려는 방향에 따라 ‘> >’ 혹은 ‘< <’로 사용됩니다.
예를들어, 오른쪽 비트 이동 연산자 ‘> >’를 사용한다면 ‘> > 1’과 같이 뒤에 몇비트를 이동시킬건지 개발자가 지정해줘야합니다.
해당 shift 연산자는 부호를 유지하면서 비트를 이동시킨다는 특징이 있습니다.
즉, 이동시키려는 대상이 양수인 경우 최상위 비트를 0으로 채우면서 이동시킵니다.
만약, 대상이 음수인 경우 최상위 비트를 1로 채우면서 이동시킵니다.

Shift (> > >, < < <)

해당 Shfit 연산은 위에서 소개한 연산과는 다르게 부호를 무시하고 비트를 이동시킨다는 특징이 존재합니다.
즉, 이동시켜서 생긴 빈 공간을 모두 0으로 채우는 특징이 있습니다.

3. Softeer 전광판 문제

이제부터는 해당 문제를 통해 비트 연산을 실제로 어떻게 사용하는지 코드를 이용하여 간단하게 살펴보겠습니다.

Code (Java)

public void run() throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
        int count = Integer.parseInt(br.readLine().trim());

        ##1.
        int[] bitPatterns = {0b1110111, 0b0010010, 0b1011101, 0b1011011, 0b0111010, 0b1101011,
                0b1101111, 0b1110010, 0b1111111, 0b1111011, 0b0000000};
        final int DEFAULT_BIT_PATTERN = bitPatterns[10]; // For leading zeroes

        for(int i=0; i<count; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int result = 0;

            boolean A_zero = false;
            boolean B_zero = false;


            for (int j = 0; j < 5; j++) {
                int A_digit = A_zero ? 10 : A % 10;
                int B_digit = B_zero ? 10 : B % 10;

                A /= 10;
                B /= 10;

                A_zero = A == 0 ? true : false;
                B_zero = B == 0 ? true : false;

                ##2.
                result += Integer.bitCount(bitPatterns[A_digit] ^ bitPatterns[B_digit]);
            }
            System.out.println(result);
        }
    }
}

Code analysis

해당 문제는 전광판의 숫자가 변경될 때 아래 사진의 작은 막대기가 변하는 횟수를 계산하는 문제입니다.
코드 안에 ##으로 표기된 부분을 분석해보도록 하겠습니다.
Softeer 연습문제 전광판 다이얼 그림
##1. Analysis
전광판에서 0부터 9까지의 숫자가 어느 부분을 색칠할것인지 개발자가 임의로 지정하고 그에 맞춰서 2진수로 저장합니다.
전광판의 숫자 0과 아무것도 존재하지 않는 것은 다르게 판단해야 합니다.
따라서, 아무것도 존재하지 않은 상태에는 어느 곳도 색칠되지 않기 때문에 0을 10번째 배열 요소로 집어넣습니다.

##2. Analysis
결과를 의미하는 result를 출력하기 위해 해당 비트에 1이 몇개 존재하는지 확인하는 부분입니다.
bitPatterns 배열에서 현재 숫자에 맞는 요소를 가져오고 XOR 연산을 진행합니다.
이렇게되면 그대로 존재해야하는 부분은 0으로 출력되고 바뀌는 부분만 1로 변경된 값을 얻을 수 있습니다.
해당 코드에서는 Integer.bitCount를 사용하였으나 이 부분은 아래와 같이 shift 연산을 이용하여 2진수를 이루는 1의 갯수를 찾아낼 수 있습니다.


while (tmp != 0) {
    if ((tmp & 1)) {
        result++;
    }
    tmp = tmp >>> 1;
}


위 코드를 살펴보면 ‘tmp & 1’이라는 조건을 통해 최하위 비트가 1인지 아닌지를 판단하고 있습니다.
1은 이진수로 표현하면 0b000000001입니다. 따라서 & 연산을 통하여 최하위 비트를 판별할 수 있습니다.
다음으로 ‘tmp = tmp »> 1;’부분에서는 tmp를 오른쪽으로 1비트씩 shift시키면서 tmp를 매 반복마다 수정하고 있습니다.
즉, tmp가 0이 될 때까지 최하위 비트가 1이면 result를 증가시키고 아니면 넘어가는 식으로 비트를 이루는 1의 갯수를 확인할 수 있습니다.

4. 마무리

간단하게 And, Or, Xor, Shift 연산을 살펴봤습니다. 해당 연산은 알고리즘 문제에서 유용하게 사용할 수 있으니 많은 적용을 해봐야합니다.
참고 : 현대자동차 Softeer 전광판 문제