백준 31458번 [!!초콜릿 중독 주의!!](C++) -yes6686- 티스토리

백준 문제 풀이: 31458 (!!초콜릿 중독 주의!!)

---

문제 링크: https://www.acmicpc.net/problem/31458

문제 설명:

주어진 논리 수식 문자열은 '0' 또는 '1'의 불리언 상수와 연산자 '!'(NOT)만 포함됩니다. 수식은 항상 오른쪽으로만 연산되며, 괄호 없이 연산 순서는 오른쪽에서 왼쪽으로 적용됩니다.

예를 들어 !!1은 !(!1)로 해석되고, 결과는 1입니다. 문자열에는 불리언 상수 하나만 존재하며, 왼쪽의 느낌표 개수에 따라 최종 결과가 결정됩니다.

---

문제 해결 코드

// 31458번: Evaluation
// '!' 연산의 개수가 짝수/홀수에 따라 최종 불리언 값을 반전하거나 유지

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    while (T--) {
        string s;
        cin >> s;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] != '!') {
                int ans = s[i] - '0';       // 불리언 상수: 0 또는 1
                int lCnt = i;               // 불리언 앞에 있는 느낌표 개수
                int rCnt = s.size() - i - 1;

                // 우측에 !가 하나라도 있으면 항상 1로 바뀜
                if (rCnt > 0) {
                    ans = 1;
                }

                // 느낌표 개수가 홀수면 반전
                if (lCnt % 2 == 0) {
                    cout << ans << '\n';
                } else {
                    ans = (ans == 1) ? 0 : 1;
                    cout << ans << '\n';
                }
            }
        }
    }
}

---

코드 설명

• 핵심 알고리즘: 오른쪽에서 왼쪽으로 적용되는 NOT 연산의 개수에 따라 결과를 반전시키는 논리 연산 구현.
• 구현 세부사항:
  • s[i] != '!': 불리언 상수를 찾는 조건
  • lCnt: 상수 앞의 느낌표 개수
  • rCnt: 상수 뒤에 있는 느낌표 개수. 이 값이 존재하면 항상 결과는 1로 초기화됨.
  • 홀수 개의 느낌표면 값을 반전시킴
• 시간 복잡도 분석:O(n) — 각 테스트 케이스마다 문자열 길이만큼 순회

---

결과

논리 수식을 해석하여 최종 불리언 값을 출력합니다.

예시 입력:
3
!!1
!!!0
!1

예시 출력:
1
1
0

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!