[백준 파이썬 2841] 외계인의 기타 연주 (실버 1)

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

2841번: 외계인의 기타 연주

from collections import deque
import sys

input = sys.stdin.readline # 입력이 최대 500,001 번 받으므로 이렇게 해주었다.

N, P = map(int, input().split()) # 음 개수 N, 프랫 개수 P
arr = [[] for _ in range(6)] # 기타줄은 6개 이고, 각 줄의 프렛은 다른 줄에 영향 못 미치니 6개의 배열 생성
count = 0 # 총 손가락을 움직인 횟수를 저장.

for _ in range(N):
    line_num, fret = map(int, input().split())
    arr[line_num - 1].append(fret) # 줄 번호가 1~6으로 들어오므로 인덱싱 0~5으로 바꿔서 저장.

for i in range(6): # 0번줄부터 5번줄까지 각각 따로 돌림.
    li = arr[i] # i번째 줄의 배열을 가져와서,
    if not li: # 배열이 비었으면(= 이 줄에서 칠 음이 없으면)
        continue # 다음 줄로 이동

    stack = deque() # 스택 자료구조 이용.

    for x in li: # 음이 입력된 순서대로 연주가 된다.
        while stack: # 만약 스택이 쌓여있으면,
            if stack[-1] < x: # 스택의 peek이 현재 음보다 작으면(= 더 높은 음을 쳐야하면)
                stack.append(x) # 현재 음을 스택에 넣는다.
                count += 1 # 현재 음을 쳐야하므로(= 손가락으로 프렛을 눌러야 하므로) 횟수 +1
                break # 다음 프렛을 확인해야하므로 while문을 나간다.
            elif stack[-1] > x: # 스택의 peek이 현재 음보다 낮으면(= 기존에 눌러놨던 높은 음의 손가락을 떼야하면)
                stack.pop() # 스택에서 뺀다.(= 손가락을 뗀다.)
                count += 1 # 손가락을 뗐으므로 횟수를 +1 한다.
            else: # 스택의 peek과 현재 음이 같아서 손가락을 움직일 필요가 없다면
                break # 현상 유지한 채로 다음 음을 확인한다.

        if not stack: # 만약 줄을 누르고 있는 손가락이 하나도 없으면,
            stack.append(x) # 현재 음을 누르고
            count += 1 # 손가락을 움직였으므로 횟수를 +1 한다.

print(count)

 

딱 보자마자 아 이거 스택문제다. 했다. 근데 이렇게 말고 처음에는 for i in range(len(li)): 로 해서 li[i] 로 각 요소에 접근했는데 이렇게 하니까 시간 초과가 났다. 그래서 아 이거 스택으로 푸는 거 아닌가? 아닌데? 빼박 스택인데 하다가 설마하고 for x in li: 로 해주니 통과가 됐다. ㅎㅎ;; 

 

for x in li: 로 할 경우 li 배열을 통째로 가져와서 빠르다는 얘기는 들었는데 이렇게 직접 겪어보니 바로 머리에 각인이 됐다. 앞으론 바보같은 짓 하지 말 것. 

 

 

그리고 인강으로도 들어봤는데 위 코드는 정말 멍청하게 짰다.. 인강에서는 입력 받지마자 바로 처리를 하더라고. 

 

import sys
input = sys.stdin.readline # 입력이 최대 500,001 번 받으므로 이렇게 해주었다.

N, P = map(int, input().split()) # 음 개수 N, 프랫 개수 P
stacks = [[] for _ in range(7)] # 기타줄은 6개 이고, 각 줄의 프렛은 다른 줄에 영향 못 미치니 6개의 배열 생성
count = 0 # 총 손가락을 움직인 횟수를 저장.
for _ in range(N): # 음을 입력 받으면서 처리.
    line_num, fret = map(int, input().split())
    # 특정 줄을 누르고 있고(= 스택에 있고), 스택 peek이 눌러야 하는 음보다 크면,
    while stacks[line_num] and stacks[line_num][-1] > fret:
        stacks[line_num].pop() # 누르고 있는 음에서 손가락을 뗀다.
        count += 1 # 손가락을 움직였으니 +1
    # 특정 줄을 누르고 있고, 누르고 있는 음과 눌러야 하는 음이 같다면,
    if stacks[line_num] and stacks[line_num][-1] == fret:
        continue # 아무것도 하지 않고 넘어간다.
    # 아무것도 누르고 있지 않다면 눌러야 하는 음을 누른다(= 스택에 추가한다.)
    stacks[line_num].append(fret)
    count += 1

print(count)

특히나 나는 while 문 안에서 큰 경우, 같은 경우도 if문으로 넣어서 처리했는데 여기서는 아주 간결하게,, 처리를 했네. 

시간은 큰 차이는 없지만 메모리가 거의 2배다 ㄷㄷ 

 

 

모 일단 문제의 요지는 스택에 있다 == 손가락으로 특정 음을 누르고 있다 라고 이해하면 풀 수 있는 문제였다. 그리고 줄이 6개가 있고 각 줄은 다른 줄과 독립적이니 스택을 6개 준비해두면 되는 거고.