[211110] 백준 2841 외계인의 기타 연주 실버1 문제풀이 python

 

알고리즘 분류 : 자료구조, 스택

 

---

#백준 2841 외계인의 기타 연주 실버1 스택

import sys
input = sys.stdin.readline

#만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

N,P = map(int,input().split()) #멜로디의 음 N, 한 줄의 프렛 P
cnt = 0 #움직임
melody = []

line,fret=map(int,input().split()) #새로운 멜로디 음 line, 새로 누를 프렛 fret
melody.append(fret)
cnt += 1

for i in range(N-1):
    n,p=map(int,input().split()) #다음 멜로디 음 n, 다음 누를 프렛 p
    if(n==line): #음이 같으면
        
        while(melody[len(melody)-1]>p): #전 프렛이 다음 프렛보다 큰 경우
            melody.pop()
            cnt += 1
            if(len(melody)<=0): #stack이 empty면
                break
        if(len(melody)>0):
            if(melody[len(melody)-1]!=p):
                cnt += 1
                melody.append(p)
        else:
            cnt += 1
            melody.append(p)
    else:
        while(len(melody)!=0):
            melody.pop()
            cnt += 1
        melody.append(p)
        cnt += 1
    line,fret = n,p

print(cnt)

 

예제 1번 풀이 정답

 

줄 하나당 손을 하나만 하는 줄 알고 줄이 달라지면 모두 다 떼고 다시 처음부터 잡는걸로 이해했는데 그게 아니었다.

 

 

#백준 2841 외계인의 기타 연주 실버1 스택

import sys
input = sys.stdin.readline

N,P = map(int,input().split()) #멜로디의 음 N, 한 줄의 프렛 P
cnt = 0 #움직임
melody = [[]for _ in range(7)]

# n,p=map(int,input().split()) #음 n, 프렛 p


for i in range(N):
    n,p=map(int,input().split()) #음 n, 프렛 p
    if(len(melody[n])>0):
        while(melody[n][len(melody[n])-1]>p): #전 프렛이 다음 프렛보다 큰 경우
            melody[n].pop()
            cnt += 1
            if(len(melody[n])<=0): #stack이 empty면
                break
        if(len(melody[n])!=0):
            if(melody[n][len(melody[n])-1]!=p):  
                melody[n].append(p)
                cnt += 1
        else:                
            melody[n].append(p)
            cnt += 1
    else:
        melody[n].append(p)
        cnt += 1

print(cnt)

 

이중배열로 총 7개의 배열을 만들어 주고 번호 그대로 하려고 0번 제외 6개의 배열을 만들었다.

 

 

 

 

담엔.. 시간 좀 더 단축해볼게요.. 다른 분은 800ms 대네요....

그래도 이 풀이는 다른 사람 코드 안보고 100% 내 머리에서 나왔다...