[알고리즘] Swift -백준 #9012 (괄호)

문제링크

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

9012번: 괄호

 

 

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

 

나의 접근방법

여는 괄호면 +1 닫는 괄호면 -1

마지막 값이 0이면 YES, 마지막 값이 +1 (여는 괄호가 남아있는거)면 NO

이 중에 마지막 값이 0인데 닫는 괄호가 들어오면 -1 해주면서 반복문을 끝낸다.

---

풀이

let num = Int(readLine()!)!

for _ in 0..<num {
    let input = Array(readLine()!).map {String($0)}
    
    var count = 0
    for i in 0..<input.count {
        if input[i] == "(" {
            count += 1
        } else {
            if count == 0 {
                count -= 1
                break
            }
            count -= 1
        }
    }
    
    print(count == 0 ? "YES" : "NO")
}

 

결과

 

 

스택을 구조체를 사용하여 푼 문제 (스택 구현 출처 : https://jeonyeohun.tistory.com/319?category=884320)

struct Stack<T> {
    var elements: [T] = []
  
    var count : Int {
        return elements.count
    }
    var isEmpty : Bool {
        return elements.isEmpty
    }
    
    mutating func pop() -> T? {
        return elements.popLast()
    }
    mutating func push(_ element: T) {
        elements.append(element)
    }
    func top() -> T? {
        return elements.last
    }
}


var num = Int(readLine()!)!

for _ in 0..<num {
    let input = Array(readLine()!).map {String($0)}
    var stack = Stack(elements: [])

    for i in input {
        if i == "(" {
            stack.push(i)
        } else {
            if stack.isEmpty {
                stack.push(i)
                break
            } else {
                let _ = stack.pop()
            }
        }
    }
    print(stack.isEmpty ? "YES" : "NO")
}

 

스택 안 쓴 결과

스택 쓴 결과

 

 

근데 스택은 배열로 구현이 가능하기에 그냥 배열로 해도 된다

스택은 선입후출로 

.append() : 가장 마지막에 추가

.popLast() : 가장 마지막에 삭제

가 있기 때문에 이것을 사용하면 스택을 구현할 필요가 없다..ㅎㅎ

var num = Int(readLine()!)!

for _ in 0..<num {
    let input = Array(readLine()!).map {String($0)}
    var arr = [String]()

    for i in input {
        if i == "(" {
            arr.append(i)
        } else {
            if arr.isEmpty {
                arr.append(i)
                break
            } else {
                let _ = arr.popLast()
            }
        }
    }
    print(arr.isEmpty ? "YES" : "NO")
}