졍's 기술 블로그

균형잡힌 세상

티어 : Silver 4
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 자료 구조, 문자열, 스택

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 입출력

힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

Algorithm

Stack 이용
1. Stack을 생성
2. 문자가 ( 이거나 [ 인 경우 Stack에 추가, ) 이거나 ] 인 경우 stack의 마지막 원소가 ( 이거나 [ 인지 확인하고 맞으면 POP()
3. pop할 때 짝이 맞지 않으면 no
4. 스택에 원소가 남아있으면 no

Code

import sys
input = sys.stdin.readline

while True:
    words = input().rstrip()
    # 입력이 .이면 종료
    if words == '.':
        break
    
    stack = []
    flag = False # 균형이 맞으면 False, 균형이 맞지 않으면 True
    for word in words:
        # 문자가 (인 경우 소괄호 stack에 추가
        if word == '(':
            stack.append(word)
        elif word == ')': # 문자가 )인 경우 소괄호 stack에서 pop
            # stack의 마지막 원소와 짝이 맞으면 pop
            if stack and stack[-1] == '(': 
                stack.pop()
            # stack 비어있으면 no 출력
            else:
                flag = True
                break
                
        elif word == '[': # 문자가 [인 경우 대괄호 stack에 추가
            stack.append(word)
        elif word == ']': # 문자가 ]인 경우 대괄호 stack에서 pop
            # stack의 마지막 원소와 짝이 맞으면 pop
            if stack and stack[-1] == '[':
                stack.pop()
            # 대괄호 stack 비어있으면 no 출력
            else:
                flag = True
                break

    # flag가 True이거나 소괄호 stack과 대괄호 stack 중 비어있지 않은 리스트가 있으면 균형을 이루지 않는 문자열
    if flag or stack:
        print('no')
    # 소괄호 stack과 대괄호 stack에 아무것도 없으면 균형을 이루는 문자열
    elif not stack:
        print('yes')

메모리: 30864 KB
시간: 112 ms

괄호

티어 : Silver 4
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 자료 구조, 문자열, 스택

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입출력

Algorithm

1. ( 모양인 경우 리스트에 해당 문자 append
2. ) 모양인 경우 리스트에서 pop
2.1. pop이 불가능하면, 마지막에 리스트에 뭔가 남아있으면 NO 반환
2.2. 마지막에 리스트에 아무것도 없으면 YES 반환

Code

T = int(input())
for _ in range(T):
    string_ = list(input())
    
    list_ = []
    flag = False
    for chr in string_:
        # ( 모양인 경우 리스트에 해당 문자 append
        if chr == '(':
            list_.append(chr)
        else: # ) 모양인 경우 리스트에서 pop
            if len(list_) == 0: # 리스트에서 pop이 불가능한 경우 
                flag = True
                break
            list_.pop()
    
    # 마지막에 리스트에 뭔가 남아있으면 NO 반환
    if flag or len(list_) > 0:
        print('NO')
    else:
        print('YES')

메모리: 30864 KB
시간: 80 ms

잃어버린 괄호

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 문자열, 그리디 알고리즘, 파싱

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입출력

Algorithm

1. 숫자는 숫자끼리, 연산자는 연산자끼리 각각 다른 List에 저장
    1.1. 숫자를 저장할 때 자릿수 생각해서 정수로 담기
2. A - B + C의 경우 - 연산자 뒤의 값 모두 계산하기
    2.1. - 연산자가 여러 개 있는 경우 A - B + C - D에서 A - (B+C) - D 로 계산

Code

# 입력
data = input()

operator_ = []
nums = []
temp = []
index = 0
for i in range(len(data)):
    if data[i] in ['+', '-']:
        operator_.append(data[i])
        # 숫자 자릿수에 맞춰서 하나의 숫자로 만들기
        nums.append(0)
        for j in range(len(temp)):
            nums[index] += temp[-1] * (10**j)
            del temp[-1]
        index += 1
    else:
        temp.append(int(data[i]))
# 마지막 숫자 추가
nums.append(0)
for j in range(len(temp)):
    nums[index] += temp[-1] * (10**j)
    del temp[-1]

# - 연산자 나오면 그 다음 - 연산자 전까지 + 모두 계산
i = 0
while True:

    # operator가 비어있으면 while문 돌지 않고 바로 출력
    if not operator_:
        break
    
    # - 연산자가 있으면 -연산자와 -연산자 사이의 값 모두 계산
    if operator_[i] == '-':
        
        index = 0
        flag = False # - 연산자 못찾으면 True
        
        if len(operator_) == 1 or i == len(operator_)-1:
            flag = True
            
        # 다음 - 연산자 찾기
        for j in range(i+2, len(operator_)+1):
            if operator_[j-1] == '-':
                index = j-1
                flag = False
                break
            else:
                flag = True
        
        # 그 뒤에 - 연산자가 없었다면
        if flag == True:
            nums[i+1] = sum(nums[i+1:])
            index = len(nums) - 1
        else: # - 연산자 있으면
            nums[i+1] = sum(nums[i+1:index+1])
        
        # 다음 - 연산자 전까지 모두 계산
        if '+' in  operator_[i+1:index]:
            temp = i + 2
            end = index + 1
            while True:
                nums[i + 2] = 0
                del operator_[i + 1]
                if nums[i + 2] == 0:
                    del nums[i + 2]
                    end -= 1
            
                if i + 2 == end:
                    break

    if i == len(operator_) - 1:
        break
    
    i += 1
    
for i in range(len(operator_)):
    if operator_[i] == '-':
        index = operator_.index('-')
        nums[index] -= nums[index+1]
        del nums[index+1]
print(sum(nums))

메모리: 30864 KB
시간: 76 ms