✅ stack

문제

링크

풀이

1. 문제 접근

여러 프렛을 누르고 있을때는 가장 높은 프렛의 음이 발생하므로
같은 줄에서 이미 누르고 있는 프렛보다 낮은 프렛을 누를때는 이미 누르고 있던 프렛들을 떼고 눌러야 한다.
각 줄마다 프렛이 각각 존재한다.

2. 자료구조 선택과 그 이유

이미 누르고 있는 프렛보다 높은 프렛을 누를때는 기존 손가락을 떼지 않고 같이 누르고 있어야 하므로 stack에 저장한다.

자연스럽게 오름차순으로 저장되므로 프렛의 높이를 고려한 우선순위큐 등을 사용하지 않아도 됨

3. 문제 해결 로직 (풀이법)

각 줄마다 프렛이 각각 존재하므로 각 줄마다 stack을 따로 사용하고
새로 누르는 프렛이 기존 누르고 있던 프렛(stack 안의 프렛)보다 낮을 경우 stack 안의 프렛들을 제거하고 새로 누르는 프렛을 추가한다.

의사코드

cin >> N >> P
stack st[7] // 1~6번줄의 프렛 누른 현황

for(i : 1 ~ N){
	cin >> line >> pl
    while(!st[line].empty && st[line].top > pl){
    	st[line].pop
        cnt++
    }
    if(st[line].top == pl)continue // 프렛 같을 경우 또 눌러줄 필요 없음
    st[line].push(i)
    cnt++
}

cout << cnt

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

줄마다 프렛이 독립적이므로 각각의 stack을 사용해야 한다는점