[CLASS 2]백준 4949번, 9012번, 10773번, 10816번

4949번 : 균형잡힌 세상

 

괄호의 균형(?)을 맞추는 문제이다. 스택을 이용한다면 쉽게 풀 수 있다.

 

파이썬은 스택을 따로 모듈로 제공하지는 않고 대신 list의 pop과 append를 사용한다면 스택처럼 사용할 수 있다.

 

내 코드:

def balanced(string):
    stack = []
    for char in string:
        if char == '(' or char =='[':
            stack.append(char)
        elif char == ')' or char == ']':
            if stack:
                if char == ')' and stack.pop() != '(':
                    return 'no'
                elif char == ']' and stack.pop() != '[':
                    return 'no'
            else:
                return 'no'
        elif char =='.':
            if not stack:
                return 'yes'
            else:
                return 'no'

answer = []
while True:
    string = input()
    if string == '.':
        break
    answer.append(balanced(string))

print('\n'.join(answer))

 

( 혹은 [ 가 나오면 스택에 이를 저장하고, ) 혹은 ] 가 나오면 스택이 비었는지 확인한 후 꺼내어 비교하면 된다.

 

9012번 : 괄호

 

방금 풀었던 4949번 문제보다도 쉬운 문제이다. 이 문제는 괄호가 소괄호로 한정되어 있기 때문에 스택을 사용할 필요도 없이 정수형 변수 하나를 설정해서 풀면 된다.

 

내 코드:

for _ in range(int(input())):
    baskets = 0
    for char in input():
        if char == '(':
            baskets += 1
        elif char == ')':
            baskets -= 1
            if baskets < 0:
                break

    if baskets == 0:
        print('YES')
    else:
        print('NO')

 

baskets 변수에 현재 열려있는 소괄호의 개수를 저장하면 된다.

 

10773번 : 제로

 

이 문제또한 스택의 개념을 이용하면 쉽다.

 

내 코드:

import sys
input = sys.stdin.readline
stack = []
for _ in range(int(input())):
    number = int(input())
    if number == 0:
        stack.pop()
    else:
        stack.append(number)

print(sum(stack))

 

스택에 숫자를 일단 저장하고 0이 입력될 때마다 꺼내어 없애면 된다.

 

10816번 : 숫자 카드 2

 

가장 먼저 문제를 보고 혹시나 싶어 내장 함수만으로 구현해보려고 했다.

 

내 코드(시간 초과):

N,numbers,M,targets = input(),list(map(int,input().split())),input(),list(map(int,input().split()))
counts = []
for target in targets:
    counts.append(str(numbers.count(target)))

print(' '.join(counts))

 

결과는 역시 시간 초과였다. count함수가 일일이 숫자를 세는데 시간이 너무 많이 소요된다.

 

그 다음으로 이용한 것이 bisect 모듈을 이용한 이진 탐색이다.

 

내 코드(이진 탐색):

# 이진 탐색
from bisect import bisect_left,bisect_right

N,numbers,M,targets = input(),list(map(int,input().split())),input(),list(map(int,input().split()))
numbers.sort()
counts = []

for target in targets:
    lidx = bisect_left(numbers,target)
    ridx = bisect_right(numbers,target)
    count = ridx - lidx
    counts.append(str(count))

print(' '.join(counts))

 

이진 탐색을 이용하였더니 통과하였다. 그런데 속도가 영 시원치 않아서 문제를 푼 다른 분들의 코드를 참고하였더니 collections의 Counter를 사용하였다. 다음은 Counter를 사용한 코드이다.

 

내 코드(Counter 사용):

# Collections.Counter 이용
from collections import Counter
N,counts,M = input(),Counter(input().split()),input()
targets = input().split()
for target in targets:
    print(counts[target],end=' ')

 

Counter에 매개변수로 list를 집어넣는다면 알아서 그 안에있는 원소를 찾아 dictionary 형태로 저장해준다. 이에 대한 자세한 설명은 여기에서 볼 수 있다.