백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2504 괄호의 값 편 (python)

728x90

문제 살펴보기!!

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

솔루션 살펴보기!!

import sys

def input():
    return sys.stdin.readline().rstrip()

def is_valid_bracket_sequence(s):
    """괄호 유효성을 검사하는 함수"""
    stack = []
    for ch in s:
        if ch in '([':
            stack.append(ch)
        elif ch == ')':
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                return False
        elif ch == ']':
            if stack and stack[-1] == '[':
                stack.pop()
            else:
                return False
    return not stack  # 스택이 비어 있으면 유효한 괄호

def calculate_bracket_value(s):
    """괄호 구조에 대한 값을 계산하는 함수"""
    stack = []
    
    for ch in s:
        if ch == '(':
            stack.append(('(', 2))
        elif ch == '[':
            stack.append(('[', 3))
        elif ch == ')':
            # 괄호 안의 값을 계산해서 곱해줍니다.
            if stack and stack[-1][0] == '(':
                stack.pop()  # 열린 괄호 제거
                stack.append((None, 2))  # () -> 2
            else:
                last_value = 0
                while stack and stack[-1][0] is None:
                    last_value += stack.pop()[1]  # 값들을 더해줍니다.
                if stack and stack[-1][0] == '(':
                    stack.pop()  # 열린 괄호 제거
                    stack.append((None, last_value * 2))
        elif ch == ']':
            if stack and stack[-1][0] == '[':
                stack.pop()  # 열린 괄호 제거
                stack.append((None, 3))  # [] -> 3
            else:
                last_value = 0
                while stack and stack[-1][0] is None:
                    last_value += stack.pop()[1]  # 값들을 더해줍니다.
                if stack and stack[-1][0] == '[':
                    stack.pop()  # 열린 괄호 제거
                    stack.append((None, last_value * 3))
    
    # 모든 값을 더해줍니다.
    total_value = 0
    while stack:
        total_value += stack.pop()[1]
    
    return total_value

def main():
    s = input()
    
    # 먼저 괄호 유효성 체크
    if not is_valid_bracket_sequence(s):
        print(0)
        return
    
    # 유효한 괄호일 경우, 점수 계산
    result = calculate_bracket_value(s)
    print(result)

if __name__ == "__main__":
    main()

코드 흐름 및 주요 개념 알아보기!!

이 코드는 입력된 괄호 문자열이 유효한지 검사하고, 유효한 경우 해당 괄호 구조에 따른 값을 계산하여 출력하는 문제를 해결합니다. 코드는 크게 두 가지 작업을 합니다:

괄호 유효성 검사 (is_valid_bracket_sequence 함수)
괄호 값 계산 (calculate_bracket_value 함수)

이 흐름을 하나씩 살펴보겠습니다.

1. 메인 함수 (main)

def main():
    s = input()
    
    # 먼저 괄호 유효성 체크
    if not is_valid_bracket_sequence(s):
        print(0)
        return
    
    # 유효한 괄호일 경우, 점수 계산
    result = calculate_bracket_value(s)
    print(result)

if __name__ == "__main__":
    main()

입력: 문자열 s를 입력받습니다. 이 문자열은 여러 개의 괄호로 구성되어 있습니다.
유효성 검사: 먼저 is_valid_bracket_sequence 함수를 호출하여 입력된 문자열이 유효한 괄호 구조인지 확인합니다. 유효하지 않다면 0을 출력하고 종료합니다.
값 계산: 유효한 경우 calculate_bracket_value 함수를 호출해 괄호 구조의 점수를 계산하고 그 결과를 출력합니다.

2. 괄호 유효성 검사 (is_valid_bracket_sequence)

def is_valid_bracket_sequence(s):
    """괄호 유효성을 검사하는 함수"""
    stack = []
    for ch in s:
        if ch in '([':
            stack.append(ch)
        elif ch == ')':
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                return False
        elif ch == ']':
            if stack and stack[-1] == '[':
                stack.pop()
            else:
                return False
    return not stack  # 스택이 비어 있으면 유효한 괄호

스택 사용: 스택을 이용해 괄호가 올바르게 짝을 이루는지 확인합니다.
- 여는 괄호 ( 또는 [가 나오면 스택에 추가합니다.
- 닫는 괄호 ) 또는 ]가 나오면 스택의 마지막 요소가 해당 여는 괄호인지 확인한 후, 맞다면 짝을 이루므로 스택에서 제거합니다.
- 괄호의 짝이 맞지 않거나 스택이 비어 있는 상태에서 닫는 괄호가 나오는 경우, 유효하지 않은 괄호 구조이므로 False를 반환합니다.
최종 결과: 모든 괄호를 확인한 후 스택이 비어 있으면 유효한 괄호 구조입니다(True), 그렇지 않으면 유효하지 않으므로 False를 반환합니다.

3. 괄호 값 계산 (calculate_bracket_value)

def calculate_bracket_value(s):
    """괄호 구조에 대한 값을 계산하는 함수"""
    stack = []
    
    for ch in s:
        if ch == '(':
            stack.append(('(', 2))
        elif ch == '[':
            stack.append(('[', 3))
        elif ch == ')':
            # 괄호 안의 값을 계산해서 곱해줍니다.
            if stack and stack[-1][0] == '(':
                stack.pop()  # 열린 괄호 제거
                stack.append((None, 2))  # () -> 2
            else:
                last_value = 0
                while stack and stack[-1][0] is None:
                    last_value += stack.pop()[1]  # 값들을 더해줍니다.
                if stack and stack[-1][0] == '(':
                    stack.pop()  # 열린 괄호 제거
                    stack.append((None, last_value * 2))
        elif ch == ']':
            if stack and stack[-1][0] == '[':
                stack.pop()  # 열린 괄호 제거
                stack.append((None, 3))  # [] -> 3
            else:
                last_value = 0
                while stack and stack[-1][0] is None:
                    last_value += stack.pop()[1]  # 값들을 더해줍니다.
                if stack and stack[-1][0] == '[':
                    stack.pop()  # 열린 괄호 제거
                    stack.append((None, last_value * 3))
    
    # 모든 값을 더해줍니다.
    total_value = 0
    while stack:
        total_value += stack.pop()[1]
    
    return total_value

스택 사용: 이번에도 스택을 사용하지만, 여는 괄호와 함께 해당 괄호의 값을 저장하는 방식으로 괄호 값을 계산합니다.
괄호 처리:
- 여는 괄호 ( 또는 [가 나오면 스택에 해당 괄호와 곱셈 값을 튜플로 저장합니다. 예를 들어, (는 2, [는 3을 곱해야 하므로 각각 2, 3을 함께 저장합니다.
- 닫는 괄호 ) 또는 ]가 나오면:
  1. 단순 괄호: 바로 앞에 해당하는 여는 괄호가 있다면, 해당 괄호 쌍의 값을 계산합니다. 예를 들어, ()는 2, []는 3입니다.
  2. 중첩 괄호: 중첩된 구조라면 그 안에 있는 값을 먼저 계산해 곱한 후 최종 값을 계산합니다. 예를 들어, (())는 2 * 2 = 4이고, [[]]는 3 * 3 = 9입니다.
  3. 스택에서 값을 꺼내 합산: 스택에서 값을 꺼내며 내부 값을 더하고, 이를 괄호 값과 곱해 최종 값을 스택에 다시 저장합니다.
최종 값 계산:
- 스택에 남아 있는 값들을 모두 더해 최종 값을 계산합니다.
- 이 값이 최종 출력되는 값입니다.

728x90

주요 개념 설명

스택 (Stack):
- 스택은 데이터를 쌓고 꺼내는 자료구조로, "후입선출(LIFO, Last In First Out)"의 원리를 따릅니다. 이 문제에서는 여는 괄호를 스택에 쌓고, 닫는 괄호가 나올 때 짝을 확인하며 스택에서 제거하는 방식으로 유효성을 검사하고, 점수를 계산합니다.
괄호 짝 확인:
- 괄호가 유효하려면 여는 괄호가 먼저 나오고, 그에 맞는 닫는 괄호가 적절히 나와야 합니다. 이를 확인하기 위해 스택을 사용합니다. 여는 괄호는 스택에 추가하고, 닫는 괄호가 나오면 스택의 마지막 요소가 짝이 맞는 여는 괄호인지 확인합니다.
중첩 구조와 값 계산:
- 괄호가 중첩된 구조에서는 괄호 안에 들어 있는 값들을 먼저 계산하고, 괄호의 값과 곱해 줍니다. 예를 들어, ([[]])처럼 중첩된 구조에서 내부 값을 계산한 후, 전체 값을 계산하는 것이 중요한 개념입니다.
유효성 검사와 값 계산의 분리:
- 이 코드는 먼저 괄호의 유효성을 검사한 후, 유효한 경우에만 점수를 계산하는 방식으로 설계되었습니다. 이렇게 유효성 검사를 먼저 하는 것이 효율적입니다. 잘못된 괄호 구조라면, 점수를 계산할 필요 없이 바로 0을 출력할 수 있기 때문입니다.

이 코드를 통해 스택 자료구조와 괄호 유효성 검사를 효율적으로 처리하는 방법을 배울 수 있습니다. 또한 중첩된 구조를 처리할 때 값 계산의 흐름을 이해하는 데 도움이 됩니다.

728x90

저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-22942 데이터 체커 편 (python) (0)	2024.09.11
백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2493 탑 편 (python) (0)	2024.09.10
백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-1966 프린터 큐 편 (python) (0)	2024.09.06
백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-1935 후위 표기식2 편 (python) (0)	2024.09.05
백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2346 풍선 터뜨리기 편 (python) (0)	2024.09.04

평범한 직장인이 사는 세상

백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2504 괄호의 값 편 (python)

문제 살펴보기!!

솔루션 살펴보기!!

코드 흐름 및 주요 개념 알아보기!!

1. 메인 함수 (main)

2. 괄호 유효성 검사 (is_valid_bracket_sequence)

3. 괄호 값 계산 (calculate_bracket_value)

주요 개념 설명

'알고리즘' 카테고리의 다른 글

티스토리툴바

백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2504 괄호의 값 편 (python)

문제 살펴보기!!

솔루션 살펴보기!!

코드 흐름 및 주요 개념 알아보기!!

1. 메인 함수 (main)

2. 괄호 유효성 검사 (is_valid_bracket_sequence)

3. 괄호 값 계산 (calculate_bracket_value)

주요 개념 설명

'알고리즘' 카테고리의 다른 글

'알고리즘' Related Articles

티스토리툴바