문제 소개
이번 문제에서는 부울 표현식(boolean expression)을 담고 있는 문자열 exp가 주어지며, 우리의 목표는 이 문자열 형태의 부울 표현식을 실제로 평가하는 것입니다.
표현식에 사용될 수 있는 유효한 문자는 다음과 같습니다.
- 0 또는 1 — 부울 값(false / true)을 나타냅니다.
- & — AND 연산
- | — OR 연산
- ^ — XOR 연산
즉, 주어진 표현식을 왼쪽부터 차례대로 계산하여 최종 결과를 반환해야 합니다.
예제를 통한 문제 이해
입력: str = "1&1|0^1^0&1"
출력: 0
풀이 과정:
1&1|0^1^0&1 1 AND 1 OR 0 XOR 1 XOR 0 AND 1 1 OR 0 XOR 1 XOR 0 AND 1 1 XOR 1 XOR 0 AND 1 0 XOR 0 AND 1 0 AND 1 0
왼쪽부터 연산을 하나씩 수행할 때마다 피연산자가 줄어들고, 마지막에는 단일 값인 0이 남게 됩니다.
해결 접근 방법
가장 단순하면서도 직관적인 방법은 문자열을 왼쪽에서 오른쪽으로 훑으면서 피연산자 · 연산자 · 피연산자, 즉 세 글자씩 묶어 연산을 하나씩 수행하는 것입니다. 각 연산의 결과를 다음 피연산자에 누적 적용하면 문자열 끝에서 최종 결과를 얻을 수 있습니다.
알고리즘을 단계별로 정리하면 다음과 같습니다.
- 문자열의 첫 번째 문자를 숫자로 변환해 초기 결과값으로 저장합니다.
- 인덱스 1부터 두 칸씩 이동하면서(홀수 인덱스는 항상 연산자) 반복합니다.
- 현재 연산자가
&면 AND,|면 OR,^면 XOR 함수를 호출해 누적 결과를 갱신합니다. - 모든 문자를 처리하면 최종 결과를 반환합니다.
구현 코드
위 접근 방식을 C++로 구현한 프로그램은 다음과 같습니다.
#include <iostream>
using namespace std;
// AND 연산을 수행하는 함수
int andOperation(int a, int b){
return a & b;
}
// OR 연산을 수행하는 함수
int orOperation(int a, int b){
return a | b;
}
// XOR 연산을 수행하는 함수
int xorOperation(int a, int b){
return a ^ b;
}
// 문자열 형태의 부울 표현식을 평가하는 함수
int solveExpression(string s) {
int n = s.length();
int result = s[0] - '0'; // 첫 피연산자를 정수로 변환
// 연산자 위치(홀수 인덱스)를 기준으로 두 칸씩 이동
for (int i = 1; i < n; i += 2) {
int operand = s[i + 1] - '0';
if (s[i] == '&') {
result = andOperation(result, operand);
}
else if (s[i] == '|') {
result = orOperation(result, operand);
}
else {
result = xorOperation(result, operand);
}
}
return result;
}
int main() {
string expr = "1&1|0^1^0&1";
cout << "표현식 " << expr << "의 평가 결과: " << solveExpression(expr) << endl;
return 0;
}
실행 결과
표현식 1&1|0^1^0&1의 평가 결과: 0
코드 동작 원리
핵심은 s[i] - '0' 부분입니다. 문자 '0'과 '1'은 아스키 코드로 각각 48과 49이므로, 여기서 '0'(48)을 빼주면 실제 정수 값 0과 1을 얻을 수 있습니다. 이렇게 변환된 정수에 비트 연산자 &, |, ^를 적용하면 부울 연산이 그대로 수행됩니다.
예를 들어 입력이 "1&1|0^1^0&1"라면 다음 순서로 계산이 진행됩니다.
- 초기값: 1
- 1 & 1 = 1
- 1 | 0 = 1
- 1 ^ 1 = 0
- 0 ^ 0 = 0
- 0 & 1 = 0 → 최종 결과 0
복잡도 분석
- 시간 복잡도: O(n) — 문자열을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.
마무리
이처럼 문자열로 표현된 부울 표현식은 왼쪽부터 세 글자씩 묶어 처리하는 간단한 순회만으로도 손쉽게 평가할 수 있습니다. 만약 괄호나 연산자 우선순위가 포함된 더 복잡한 표현식을 다뤄야 한다면, 스택(stack) 기반의 파싱 기법으로 자연스럽게 확장할 수 있습니다.