Swift) 백준 9012번: 괄호

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

9012번: 괄호

 

ㅎㅎ... 엄청난 어려운 말처럼 보여서 처음엔 좀 쫄았다.. "()" 하나의 완성된 괄호를 vps라는 변수로 만들어서 가장 큰 괄호부터 vps들이 있는지 확인을 해야 하나.. 그러면 어떻게 구현을 하지..? 이런 고민을 많이 하게 돼서 여느 때처럼 아이패드에 필기하며 설계를 해봤다!

 

글씨 죄송합니다.. 그냥 어떤식으로 생각을 했는지만 봐주십쇼 ㅎㅎ

 

아무리 생각해도 굳이 vps변수를 만들어서 그에 맞는 로직을 작성하는 것 보다는 "("와 ")" 이 괄호의 요소를 각각의 문자로 바라보았다!

그다음엔 완벽한 괄호(VPS라고 하겠다)가 아닐 조건이 필요해서 코드를 작성하며 하나씩 추려나갔다.

 

1. "(", ")" 의 개수가 일치하지 않다? -> 성립이 안된다.
    ex) 입력: )))(((  => 개수는 서로 일치하지만 괄호라고 볼 수 없다.

2. "(", ")" 의 개수가 홀수? -> 마찬가지로 성립이 안된다.  
     ex) 입력: )))((( => 위와 같은 입력인데 이 또한 괄호가 아니지만 짝수인데 짝수로 VPS성립 조건을 판단한다면 오답이다.

 

 

그러다 생각한것이 바로.... 조합이다!

이게 무슨 말이냐면, VPS는 "("와 ")"의 조합으로 이루어진다! 이게 완벽한 조건이라고 생각한다. 괄호의 완성 여부를 판단해야 하는 상황에서 어떤 것이 괄호를 완성시키는지에 대해 생각하다가 떠오른 것이다.

 

그래서 다시 문제 설계에 들어가 코드를 작성했다.

 

설계

입력을 문자 단위로 쪼개서 배열 형태로 받는다.
그 후 0번째 인덱스를 항상 조합의 첫 번째 요소로 삼는다.

1. 만약 0번째 인덱스가 "("라면, 0번째 이후 첫번째 ")"를 찾아 입력받은 배열에서 삭제를 해준다.
2. 만약 0번째 인덱스가 ")"라면, 0번째 이후 첫번째 "("를 찾아 입력받은 배열에서 삭제를 해준다. 

이런 식으로 조합을 완성시키다 보면 완벽한 VPS 입력문에서는 하나도 남는 문자가 없을 것이며,
불완전한 입력문에서는 "(" 혹은 ")"가 배열에 남아 그에 따라 YES or NO를 출력한다!

 

 

 

1차 제출: 오답

---

import Foundation

let n = Int(readLine()!)!

func vpsTest () -> String {
    var temp = readLine()!.map({String($0)})
    
    for _ in 0..<temp.count/2{
        if temp[0] == "(" {
            if let index = temp.firstIndex(of: ")") {
                temp.remove(at: index)
                temp.remove(at: 0)
            }
        } else {
            if let index = temp.firstIndex(of: "(") {
                temp.remove(at: index)
                temp.remove(at: 0)
            }
        }
    }
    
    if temp.isEmpty {
        return "YES"
    } else {
        return "NO"
    }
}

for _ in 0..<n {
    print(vpsTest())
}

엥?? 도대체 왜?? VPS의 성립 조건을 지켜서 조합을 완성했는데 왜 틀린 거지??

 

그 이유는 바로 else구문에 있다. 이해하기 쉽게 예시를 들어보자!

 

ex) 입력: ))(( => 분명히 위에서 필기를 하며 필터링 한 입력 예시지만 이번 로직에서는 미처 생각하지 못했다.
                            누가 봐도 괄호라고 볼 수 없지만 두 개씩의 문자들은 서로 조합을 하면 ()() 이런 완벽한 VPS 두 개가 나온다.

 

 

그러면 어떤 식으로 else 구문을 바꿀까?

 

 

그건 바로! 0번째 인덱스가 ")" 일 때 NO를 return 하는 것이다!

 

그렇게 바로 확정 지어도 되나??? -> 된다! 아무리 긴 완벽한 VPS입력문이라도 괄호가 완성되려면 무조건 "("로 시작을 해야 한다.

VPS의 완성 조건이 정답을 도출하는 데에 큰 도움이 되었다. ")"로 시작하는 괄호는 이 세상에 존재하지 않기 때문에 확신할 수 있었다.

 

 

 

 

 

 

 

 

 

2차 제출: 정답

---

import Foundation

let n = Int(readLine()!)!

func vpsTest () -> String {
    var temp = readLine()!.map({String($0)})
    
    for _ in 0..<temp.count/2{
        if temp[0] == "(" {
            if let index = temp.firstIndex(of: ")") {
                temp.remove(at: index)
                temp.remove(at: 0)
            }
        } else {
            return "NO"
        }
    }
    
    if temp.isEmpty {
        return "YES"
    } else {
        return "NO"
    }
}

for _ in 0..<n {
    print(vpsTest())
}

정말 이 코드를 완성시켰을 때는 유레카 같은 기분이었다.

아마 내가 처음에 너무 쫄았다가 온전히 내 힘으로 해결해서 그런 것 같다 ㅎㅎ

 

 

 

 

 

 

 

 

다른 문제풀이 방법 

---

import Foundation

let n = Int(readLine()!)!

for _ in 0..<n {

    let temp = readLine()!
    var count = 0
    
    for char in temp{
        if char == "(" {
            count += 1
        } else if char == ")" {
            count -= 1
            if count < 0 {
                break
            }
        }
        
    }
    print(count==0 ? "YES" : "NO")
}

다른 방법을 시도하던 중 더 간결하고 메모리 측면에서도 더 효율적인 코드를 찾았다.

우선 이 코드는 위에서 언급한 문자 개수에 따라 VPS 성립 판별을 한다.

 

아깐 분명히 개수로는 성립이 안된다 하지 않았나? -> 그렇지! 개수만으로는 성립이 안된다.
ex)  )))(((  -> 이러한 입력이 YES가 되는 것을 방지하기 위해 count가 0보다 작을 때는 NO를 출력한다. 
앞서 언급한 것처럼 ")"로 시작하는 괄호는 없다. 만약 ex처럼 입력이 들어오면 count가 0인 상태에서 -1을 해준다. 그러면 0보다 작아지기 때문에 NO를 출력하게 된다.

 

 

 

 

 

 

 

 

 

---

문제를 푸는 데는 아주 많은 방법이 존재하고 어떤 게 정답이고 아니 다를 말하기는 힘들다.

대신 문제를 맞혔더라도 더 나은 방법이 있는지 고민해보고 찾아보는 건 정말 좋은 습관 같다. 더 나은 코드를 작성하거나 다른 사람의 효율적인 코드를 보며 느끼는 게 참 많은데 나도 언젠가는 도움이 되는 코드를 작성하고 싶다.