[백준/BOJ] 15926번: 현욱은 괄호왕이야!!

문제

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

해설

처음 문제에 접근한 방법은 다음과 같았다.

1. "(" 라면 Stack에 집어넣는다.
2. ")"이며 Stack이 비어있지 않다면 길이에 2를 더한 후 max 값을 갱신한다.
3. ")"이며 Stack이 비어있다면 Stack과 길이를 초기화시킨다.

문제를 너무 단순하게 접근하였는지 당연히 틀렸습니다를 받게 되었다.

문제에 나와있는 테스트케이스를 모두 통과하기에 질문 게시판에서 추가 테스트케이스를 확인하였고,

(()(()()(()(
위와 같은 케이스에서 답이 4가 나와야 하지만 8이라는 오답이 나오는 것을 확인할 수 있었다.

나의 풀이대로면 아래와 같이 된다.

이렇게 적어가면서 했다면 당연히 아니란걸 알았을테지만 너무 느낌대로 풀었던 것 같다.

 

때문에 다른 해결 방법을 생각하게 되었고, 다음으로 생각해낸 방법은 다음과 같다.

1. 괄호가 정상인지 체크할 Boolean 배열을 선언한다. → 이하 check(변수명) 이라고 한다.
2. "("라면 Stack에 현재 index의 값을 넣는다. → "("를 넣는 것에서 index로 변경
3. Stack이 비어있지 않고 ")"라면 check[stack.pop()], check[i]를 true로 설정해준다. 이를 통해 ( )가 정상적인 괄호라고 체크된다.
4. 문자열의 끝까지 확인을 마친 후, for문을 통해 check 변수에서 true가 연속으로 가장 많이 나온 값이 가장 긴 괄호 문자열이 된다.

코드

import java.util.Stack

fun main() {
    val n = readln().toInt()
    val brackets = readln().toCharArray()
    val check = BooleanArray(n)

    val stack = Stack<Int>()
    for(i in brackets.indices) {
        if(brackets[i] == '(') stack.add(i)
        else if(stack.isNotEmpty() && brackets[i] == ')') {
            check[stack.pop()] = true
            check[i] = true
        }
    }

    var max = 0
    var cnt = 0
    for(i in 0 until n) {
        if(check[i]) cnt++
        else {
            max = maxOf(max, cnt)
            cnt = 0
        }
    }
    max = maxOf(max, cnt)

    println(max)
}