10799번: 쇠막대기

문제 풀이 아이디어

따라서 이 문제를 풀기 위해서 주목한 점은 “)”가 나올 때마다 파이프 조각이 추가된다는 것입니다.

1. “)”가 레이저를 의미하는 닫힌 괄호라면 현재까지 존재하는 파이프의 갯수만큼 새로운 조각이 생길 것입니다.
2. “)”가 파이프를 의미하는 닫힌 괄호라면 파이프 꼭다리가 남으므로 새로운 조각이 1개 생길 것입니다.

쉽게 생각하면 “)”가 나올 때 마다 “)” 왼쪽에 있는 파이프 조각의 갯수를 구해서 더한다고 생각하면 됩니다. 문제에 주어진 예시를 예로 들면 아래와 같습니다.

코드

// index로 접근해야하기 때문에 Array로 바꾼다.
let input = readLine()!.map { $0 }

// 현재 파이프 갯수와 최종 조각의 갯수 저장
var pipes = 0
var result = 0

for i in 0..<input.count {
    //1. 레이저의 시작점
    if input[i] == "(" && input[i + 1] == ")" { //🚫 "("로 끝나지 않으므로 index out of range를 걱정하지 않아도 된다.
        continue // 레이저 시작에서는 할 일이 없음
    //2. 파이프의 시작점
    } else if input[i] == "(" && input[i + 1] != ")" {
        pipes += 1 // 파이프 1개 추가
    //3. 레이저의 끝점
    } else if input[i] == ")" && input[i - 1] == "("  { //🚫 ")"로 시작하지 않으므로 index out of range를 걱정하지 않아도 된다.
        result += pipes // 파이프 갯수만큼 조각이 생긴다.
    //4. 파이프의 끝점
    } else {
        pipes -= 1 // 파이프 하나가 끝이므로 제거
        result += 1 // 파이프 꼭다리 1개 추가
    }
}

print(result)

Stack으로 풀어보기

전통적으로(?) 괄호의 쌍을 맞추는 문제는 스택으로 풀어왔습니다. 이번에는 전통에 맞추어 stack을 통해 풀어보도록 하겠습니다.

파이프 갯수를 직접 세는 대신 stack의 길이를 활용한 방법으로 위 방법과 원리는 완전히 동일합니다!

let input = readLine()!.map { $0 }
var stack = [Character]()
var result = 0

for i in 0..<input.count {
    if input[i] == "(" { // 여는 괄호일 때 push
        stack.append(input[i])
    } else { // 닫는 괄호일 때
        stack.removeLast() // pop하고
        if input[i - 1] == "(" { // 레이저일 때 stack 길이 (= 현재 파이프 갯수) 만큼 +
            result += stack.count
        } else {
            result += 1 // 파이프라면 꼭다리 + 1
        }
    }
}

print(result)