올바른 괄호

올바른 괄호 문제는 전에도 많이 풀어 본 문제이다.

괄호는 두가지의 성격을 가지고 있다.
첫번째, 왼쪽 괄호는 반드시 오른쪽 괄호와 짝을 이루고 있어야 한다.
두번째, 오른쪽 괄호가 왼쪽 괄호보다 먼저 나와서는 안된다.

이 두가지의 성격을 확인하기 위해서는
첫번째로 스택 자료형을 만들어준다. 그래서 만약에 왼쪽 괄호가 나오면 오른쪽 괄호를 스택에 추가한다. 그리고 오른쪽 괄호를 만나면 stack의 top에 있는 오른쪽 괄호를 가져온다. 이 때 만약에 스택에 괄호가 존재하지 않으면 올바르지 못한 괄호이다.
두번째로 모든 연산이 종료가 된 이후에 stack 자료형을 살펴본다. 만약에 stack 자료형에 괄호가 존재하면 이 또한 올바르지 못한 괄호이다.

🌞 문제

문자열 s의 길이가 10만 이하의 자연수이다. 이는 n의 값이 10만 이라는 것이고
1초의 시간안에 이 문제를 해결하기 위해서는 O(nlogN)의 시간 안에서 해결을 해야한다.

🌼 풀이