문제

백준 31458번-!!초콜릿 중독 주의!!
이 문제에서 계산할 수식은 정수 하나와 $0$개 이상의 느낌표로 이루어져 있다. 정수는 $0$ 또는 $1$이며, 느낌표는 정수의 앞이나 뒤에 올 수 있다. 이 수식을 계산하는 규칙은 다음과 같다.

$n!$은 $n$의 팩토리얼이다.
$0!=1$,
$1!=1$로 정의된다.

$!n$은 $n$의 논리 반전(logical not)이다.
$!0=1$,
$!1=0$으로 정의된다.

팩토리얼이나 논리 반전이 중첩되어 있으면 중첩된 횟수만큼 계산하며, $!n!$과 같이 둘 다 사용된 경우에는 팩토리얼을 먼저 계산한다. 예를 들어, $!!n!!=!(!((n!) !))$이다.

예시

입력:

6
0!
1!
!0
!1
!!0!!
!!1!!

출력:

1
1
1
0
1
1

풀이

1. 첫번째 풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = sc.nextInt();
        sc.nextLine();
        
        while (T-- > 0) {
            String str = sc.nextLine();
            int left = 0;
            
            while ((left < str.length()) && (str.charAt(left) == '!')) {
                left++;
            }
            
            int right = str.length() - left - 1;
            int num = str.charAt(left) - '0';
            
            if (right > 0) {
                num = 1;
            }
            
            sb.append((num + left) % 2).append("\n");
        }
        
        
        System.out.print(sb);
        sc.close();
    }
}

맨 처음에는 if-else문을 통해서 0!이거나 1!이면 둘 다 1로 출력하도록 하고, !1이면 0, !0이면 1을 출력하도록 하려고 했다. 그런데 중첩된 거는 어떻게 해결해야할지 너무 막막했다. 결국 구글링을 통해 C++로 되어있는 코드를 자바에 맞게 작성하였다.

1. 먼저 왼쪽 느낌표의 개수를 구한다. left가 str보다 작으면서 charAt(left) == '!'라면 왼쪽 느낌표가 있는거다. ++를 해준다.
2. 오른쪽 느낌표의 개수는 전체 문자열의 길이(str.length()) - 왼쪽 느낌표의 개수(left) - 정수(1)을 빼준 값이다.
3. 정수는 str.charAt(left) - '0'을 해준 값이다.
   3-1. charAt()은 0부터 시작한다. 따라서 만약 left가 1개가 있다면, charAt(1)은 왼쪽 느낌표의 뒤의 정수를 나타낼 것이다.
   3-2. - '0'은(는) ASCII 코드 활용으로 문자를 정수로 변환하는 방식이다. 해당 과정을 생략하면 실제 left가 저장된 ASCII 코드값이 반환됨로 '0'을 빼줌으로써 0 또는 1을 반환한다.
4. 패러다임 계산: 오른쪽 느낌표는 정수값이 0이든 1이든 둘 다 1을 반환해주므로 오른쪽 느낌표가 있다면 1을 반환해주도록 한다.
5. 논리부정 계산: (num + left) % 2를 통해 나머지 값을 반환해준다.

2. 두번째 풀이

num ^= (left % 2);
            
sb.append(num).append("\n");

그리고 나는 문득 비트 연산자를 사용해서 계산할 수도 있지 않을까? 라는 생각을 했다. ^는 XOR 비트 연산자이다. 두 비트가 서로 다르면 1, 같으면 0을 반환한다.

1. 위에서 오른쪽 느낌표가 있다면 1을, 없다면 0을 num에 저장했을 것이다.
2. XOR 계산
   2-1. left % 2가 0이라면, 0 ^ 0이므로 같아서 0을 반환한다.
   2-2. left % 2가 1이라면, 0 ^ 1이므로 다르기 때문에 1을 반환한다.

💡
left % 2가 짝수라면, 부정->부정 이므로 다시 원래의 숫자를 반환하는 원리이다.

맨 위가 비트 연산자를 사용한 결과로, 나머지 두 개는 첫번째 풀이 방법이다. (백준이 익숙하지 않아서 같은 코드로 두 번 제출되었다.) 비트 연산자를 통해서 확실히 메모리 사용량이 줄어든 것을 볼 수 있다!

회고

int num = str.charAt(left) - '0';에서 '0'을 빼줌으로써 문자를 숫자로 변환할 수 있음을 새로 깨달았다. 즉, '0'을 빼지 않으면 숫자가 아니라 ASCII 코드값이 저장된다.