[Algorithm/BOJ] 4889 - 안정적인 문자열 Swift Python

문제풀이:

문제에서 말하는 안정적인 배열로 만드는 연산 횟수를 구하면 된다. 

스택을 사용해서 "}" -> "{"로 바꾸고 연산 횟수를 증가시키고

반대로 "{" -> "}"로 바꾸는 연산 횟수는 연산 처리후 스택에 남아 있는 개수의 절반이 곧 연산 횟수가 된다. 

why? 스택에 "{{{{"가 남아 있을 때 "{}{}"처럼 2번만 바꿔주면 안정적인 배열이 된다.

"-"가 나오면 반복문을 빠져 나온다.

 

코드:

Swift

var index = 0
while true {
    let data = Array(readLine()!)
    if data.first == "-" {
        break
    }
    var stack = [Character]()
    var cnt = 0
    for d in data {
        if d == "{" {
            stack.append(d)
        }
        // d == "}"일 때
        else {
            // 스택이 비어있으면 "}" -> "{"로 바꾸고 연산 횟수 증가시킴
            if stack.isEmpty {
                stack.append("{")
                cnt += 1
            }
            // 스택이 비어있지 않으면 "{"와 "}" 순서니 안정적이므로 pop
            else {
                stack.popLast()
            }
        }
    }
    index += 1
    // 처리 후 스택에 남아있는 개수의 절반이 곧 연산 횟수
    // why? "{" -> "}" 처리하는 연산을 하지 않았고 만약 스택에 "{{{{"가 남아 있을 때 2번만 바꿔주면 안정적인 배열이 됨
    print("\(index). \(cnt + stack.count / 2)")
}

 

Python 

import sys
input = sys.stdin.readline
index = 0
while True:
    data = input().rstrip()
    if data[0] == '-':
        break
    
    stack = []
    cnt = 0

    for d in data: 
        if d == '{':
            stack.append('{') 
        else:
            if stack:
                stack.pop()
            else:
                stack.append('{')
                cnt += 1
    index += 1
    print(str(index) + ". " + str(cnt + int(len(stack)/2)))

 

문제:

4889번: 안정적인 문자열