2841번: 외계인의 기타 연주

문제 풀이 아이디어

# 사용해야 하는 자료 구조: stack
	: 프렛을 오름차순으로 누르고 있어야 합니다.
	: stack의 last와 현재 누를 음을 비교해서 push할지 pop할지 결정하면 됩니다.
		: last가 더 크면 pop하기 (= 프렛 떼기)
		: last가 더 작으면 push하기 (= 프렛 누르기)
  : 각 음마다 스택을 사용해서 총 6개 사용합니다.

# 의사 코드
  1. 입력을 받고 배열 1개에 6개 스택을 선언한다.
  2. 반복문으로 음과 프렛을 받습니다. (스택에 추가하거나 빼면 result += 1)
    2-1. 해당 음의 stack.last가 프렛이 누르려는 프렛보다 작으면 stack에 프렛 추가
    2-2. 해당 음의 stack.last과 프렛이 누르려는 프렛과 같으면 break
    2-3. 해당 음의 stack.last가 누르려는 프렛 크면 stack.pop()하고 다시 비교
  3. result 출력한다.

# 시간 복잡도
  : n만큼 반복되는 반복문 1개
  : 내부에 while문이 있기는 한데 n보다 한참 작을 것으로 생각됩니다.

풀이 코드

// 외계인의 기타 연주

/*
 stack 안이 정렬되어야 한다고 생각하면?
 = stack.last 보다 큰 것만 push 하면된다.
 = 그 이전 것보다 더 작은게 나오면 뭔가 동작을 해야할 때 사용하면 좋음. (ex. 오큰수)
 */

// 첫줄 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], P = input[1]

// stack의 배열 만들기 (1 ~ 6이니까 index 맞추기 편하게 7개)
var stacks = Array(repeating: [Int](), count: 7)
// 동작의 횟수 저장할 변수
var result = 0

// N개의 줄 입력 받기
for _ in 0..<N {
    let line = readLine()!.split(separator: " ").map { Int(String($0))! }
    let n = line[0], p = line[1]
    
    while true {
        // stack의 마지막과 지금 누를 플랫 비교
        guard let last = stacks[n].last else {
            //✅ stack이 비었을 때 push하고 result + 1 (= 아무것도 안 눌렀을 때 플랫누름)
            stacks[n].append(p)
            result += 1
            break
        }
        
        //✅ 더 큰 플랫을 지금 누르고 있다면 pop하고 result + 1 (= 더 높은음 누르고 있으면 손 떼어야 함)
        if last > p {
            stacks[n].removeLast()
            result += 1
        //✅ 같은 플랫을 이미 누르고 있다면 break (= 동작 필요 없음)
        } else if last == p {
            break
        //✅ 더 작은 플랫을 누르고 있다면 현재 플랫 push하고 result + 1
        } else {
            stacks[n].append(p)
            result += 1
            break
        }
    }
}

print(result)