JinWoo Kim

백문이 불여일견, 백견이 불여일행.

3 minute read

1. 균형잡힌 세상

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

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

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

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

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

입력

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

  • 입력의 종료조건으로 맨 마지막에 점 하나(“.”)가 들어온다.

출력

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

풀이

import sys
from collections import deque

for line in sys.stdin.readlines()[:-1]:
    line = line.rstrip()
    stack = deque([])

    flag = True

    for s in line:
        if s == '(':
            stack.append(s)
        elif s == '[':
            stack.append(s)
        elif s == ')' and stack and stack[-1] == '(':
            stack.pop()
        elif s == ']' and stack and stack[-1] == '[':
            stack.pop()
        elif s == ')' and (not stack or stack[-1] != '('):
            flag = False
            break
        elif s == ']' and (not stack or stack[-1] != '['):
            flag = False
            break

    if stack or not flag:
        print('no')
    else:
        print('yes')

채점 결과

  • 정답

리뷰

  • 괄호 열릴때 스택에 넣고, 각 괄호가 닫힐때 스택 내부의 괄호가 맞지 않으면(=짝이 맞지 않으면) no, 나머지 경우에 대해 yes를 출력한다.

  • 별달리 입력 횟수에 대한 제한을 두지 않았으므로, readlines()로 입력값 전체를 읽은 후, 마지막줄의 공백줄 하나를 [:-1]을 통해 제외하여 반복문을 실행했다.

2. 프린터 큐

  • 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다.

  • 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

  • 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

  • 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

  • 여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

  • 첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

  • 테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자.
  • 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

  • 각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

풀이

import sys
from collections import deque

T = int(sys.stdin.readline())

for _ in range(0, T):
    N, M = list(map(int, sys.stdin.readline().split()))
    prior = [int(x) for x in sys.stdin.readline().split()]
    idx = [x for x in range(0,N+1)]
    q = deque(zip(prior,idx))
    arr = []
    while q:
        next_output = max(q)[0]
        next = q.popleft()
        if not q:
            arr.append(next)
            break
        elif next[0] < next_output:
            q.append(next)
        else:
            arr.append(next)

    print(arr.index([x for x in arr if x[1] == M][0])+1)

채점 결과

  • 정답

리뷰

  • 큐를 (우선도, 인덱스)의 구성으로 형성하였고, 우선도가 현재 큐 내부의 최대 우선도 값보다 작을경우 큐 맨 뒤에 append, 아니라면 출력했다.

  • 출력된 값들은 따로 리스트에 모아두었다가 M번째 인덱스 문서가 언제 출력되었는지 검색하여 출력한다.

    • 이때, 처음 출력된것은 1번이므로 결과 인덱스값에 1을 더하여 출력한다.

You May Also Enjoy