[BOJ알고리즘, C++]#2504_괄호의 값, 스택, stack

2024. 8. 8. 17:26· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. stack
  4. 2. 괄호 안에 있는 괄호, 바깥에 있는 괄호 구분
  5. #3. 코드

#1. 문제

https://www.acmicpc.net/problem/2504

 


 

#2. 풀이

 

1. stack

 

[Basic C++] #64_stack

[Basic C++] #64_stack C++에서 제공하는 stack 클래스에 대해 알아보겠습니다. Overview 개념 선언 멤버 함수 예제 #0. 개념 1. Stack C++에서 제공하는 stack은 LIFO 데이터 구조를 구현하는 STL 컨테이너입니다. s

webddevys.tistory.com

stack 컨테이너는 C++의 STL에서 제공하는 순차 컨테이너로, 후입 선출 방식으로 동작합니다. stack 컨테이너는 데이터 목록의 한쪽 끝에서만 접근/삽입/삭제 작업을 허용합니다.

 

2. 괄호 안에 있는 괄호, 바깥에 있는 괄호 구분

  1. 먼저, 괄호 매칭을 확인하기 위해 stack 컨테이너를 활용합니다.
  2. 문자열을 순화합니다.
  3. 여는 괄호일 경우 stack 컨테이너에 삽입해줍니다.
  4. 닫는 괄호일 경우, 두 가지로 나누어집니다.
  5. 하나는 stack의 top()이 이에 매칭되는 여는 괄호일 경우, 스택에서 제거하고 대응되는 숫자 2 혹은 3을  삽입해 줍니다.
  6. 다른 하나는, stack의 top()이 숫자일 경우, 여는 괄호가 나올 때까지 숫자들을 pop()해주고 누적합을 계산, 마지막으로 여는 괄호를 만나면 역시 pop() 해주고, 대응되는 숫자 2 혹은 3을 누적합에 곱해주어 결과 값에 더해줍니다. 

 


 

#3. 코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string str;
    cin >> str;

    stack<int> s;
    bool isValid = true;

    for (char c : str) {
        if (c == '(' || c == '[') {
            s.push(c == '(' ? -2 : -3);  // 열린 괄호를 음수로 표시
        } else if (c == ')' || c == ']') {
            int sum = 0;
            while (!s.empty() && s.top() > 0) {
                sum += s.top();
                s.pop();
            }

            if (s.empty() || (c == ')' && s.top() != -2) || (c == ']' && s.top() != -3)) {
                isValid = false;
                break;
            }

            int multiplier = -s.top();
            s.pop();

            s.push(sum == 0 ? multiplier : sum * multiplier);
        } else {
            isValid = false;
            break;
        }
    }

    int result = 0;
    while (!s.empty()) {
        if (s.top() < 0) {
            isValid = false;
            break;
        }
        result += s.top();
        s.pop();
    }

    if (isValid) {
        cout << result << '\n';
    } else {
        cout << "0\n";
    }

    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ, C++]#5972_택배 배송, 다익스트라, 길 찾기 알고리즘, 최단 경로 알고리즘, 무 방향 그래프  (0) 2024.08.22
[BOJ, C++]#13325_이진 트리, 이진 트리, 포화 이진 트리, DFS, 재귀 DFS  (0) 2024.08.22
[BOJ]#17431_단어 뒤집기 2, string, stack  (0) 2024.08.02
[BOJ알고리즘, C++]#3190_뱀, deque, map  (1) 2024.07.03
[BOJ, C++]#1149_RGB거리, DP  (1) 2024.07.03
  1. #1. 문제
  2. #2. 풀이
  3. 1. stack
  4. 2. 괄호 안에 있는 괄호, 바깥에 있는 괄호 구분
  5. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ, C++]#5972_택배 배송, 다익스트라, 길 찾기 알고리즘, 최단 경로 알고리즘, 무 방향 그래프
  • [BOJ, C++]#13325_이진 트리, 이진 트리, 포화 이진 트리, DFS, 재귀 DFS
  • [BOJ]#17431_단어 뒤집기 2, string, stack
  • [BOJ알고리즘, C++]#3190_뱀, deque, map
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 우선순위 큐
  • 최단 경로
  • 개발
  • BFS
  • DP
  • unreal
  • 디자인 패턴
  • Effective C++
  • 정렬
  • 기술 질문
  • BOJ
  • 트리
  • Unreal Blueprint
  • programmers
  • 그래프
  • dfs
  • stl
  • C++
  • set
  • 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#2504_괄호의 값, 스택, stack
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.