LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: ( ) { } [ ] 로만 이루어진 문자열 s

2. output: 주어진 문자열이 유효한지 여부 리턴

3. 괄호의 규칙에 맞게 쓰여진 문자열인지 판단

   • 1 <= s.length <= 104

Idea

주어진 문자열이 유효한 괄호인지 판단 → Stack

Solution

1. Stack

   여는 괄호 → 스택에 그냥 삽입

   닫는 괄호 → 스택의 최상단 값이 같은 종류의 여는 괄호인지 확인

   모든 문자열을 처리 후 스택이 비어있는지 확인

   import java.util.*
   
   class Solution {
       fun isValid(str: String): Boolean {
           val stack = LinkedList<Char>()
           for (c in str) {
               when (c) {
                   ')' -> {
                       if (stack.peekLast() != '(') return false else stack.pop()
                   }
                   '}' -> {
                       if (stack.peekLast() != '{') return false else stack.removeLast()
                   }
                   ']' -> {
                       if (stack.peekLast() != '[') return false else stack.removeLast()
                   }
                   else -> stack.offer(c)
   
               }
           }
   
           return stack.isEmpty()
       }
   }
   

   시간 복잡도: 문자열 순회 = n

   

Point