백준 - 쇠막대기 - 10799 - swift

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

10799번: 쇠막대기

 

 

문제는 스택 유형이다. 

나름 재밌는 문제 였다. 

특정 문제들은 특정 알고리즘을 쓰면 풀 수 있는 그런 뻔한 문제들이 있는데, 

그런 문제 말고 이렇게 직접 문제 해결 과정을 오롯이 찾아가는 문제가 재밌다. 

 

처음 봤을때는 이걸 어떻게 접근해야하는지, 감이 안왔다. 

레이저기준으로 양옆을 확인해야하는지... 등등 시도 해봤지만 다 영 아니였다. 

 

그러다가, 스택으로, 앞에서부터 순차적으로 확인하는걸로 생각해봤다.

만약 ((( () ))) 이렇게 3개의 쇠막대기가 겹쳐있고, 가운데로 레이저가 쏜다고 가정하면,

레이저가 나타나기전까지 ((( 는 스택에 추가해준다. 

만약 레이저가 나타났다면,  스택에 있는 개수만큼 답을 추가해준다. 즉 스택에 있는 개수만큼 잘렸다라고 가정한다.

그다음, 다시 (((를 스택에 추가해준다 ( 사실 추가하지 않는다. 스택에 이미 ((( 가 있기때문에. ) 

 

만약 레이저가 아닌,  닫히는 쇠막대기가 ")"  가 나타날경우,  이는 온전한 한개의 쇠막대기이므로,  스택에서 마지막을 빼면서, 답에 +1을 해준다. 

 

즉 핵심은 레이저가 나타났을때, 이미 앞에있던 쇠막대기들을 잘라주고,  잘라준 쇠막대기들을 다시 온전한 상태에서 시작한다는 점이다. 

 

let line = readLine()!.map{String($0)}
var ans = 0
var stack = 0
var i = 0
while i < line.count {
    // 레이저인경우 
    if i<line.count-1, line[i] == "(", line[i+1] == ")" {
        ans += stack
        i += 2
    } else {
        if line[i] == ")" {
            ans += 1
            stack -= 1
        } else {
            stack += 1
        }
        i += 1
    }
}

print(ans)