[JS] 프로그래머스 올바른 괄호

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

 

목차

• 문제
• 풀이
• 코드

문제

입력

s - 문자열

 

출력

answer - true (올바른 괄호 '(' 다음 ')' ) / false 나머지.

 

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

풀이

이 문제는 스택과 순서를 활용한 문제이다. 스택을 활용하여 '(' 다음에 ')'이 오면 '('를 pop()하도록 구현하면 된다.

 

따라서 스택을 구현할 배열과 주어진 문자열을 한 번 순회할 때 필요한 조건문을 적으면 된다. 어떤 경우에 false인지 혹은 push()나 pop() 메서드를 사용해야 할지 정리하기 위해 표를 사용하였다.

 

스택 마지막 원소	순회하고 있는 원소	명령 (statement)
X(없는 경우)	'('	push('(')
	')'	return false
'('	'('	push('(')
	')'	pop()

 

위의 표를 그려보니 스택 마지막 원소가 뭔지와 관계없이 무조건 '('가 들어가면 push('(')를 하였다.

 

결과적으로 코드를 구현하는 것은

1. 문자열 s의 순회
2. 순회하는 순간의 타겟 원소가 '('인 경우 push() 메서드 사용
3. 순회하는 순간의 타겟 원소가 ')'인 경우 pop() 메서드 사용
4. 나머지는 false를 반환한다.
5. 순회가 끝나고 스택에 원소가 남으면 false를 반환하고 아닌 경우 true를 반환한다.

이렇게 코드를 구현하였다.

 

시간 복잡도는 문자열 s를 한 번 순회하는 데에 걸리는 시간인 O(n)이다.

공간 복잡도는 스택을 담는 공간인 O(n)이다.

코드

function solution(s){
    const stk = [];
    
    for (v of s) {
        if (v==='(') stk.push(v);
        else if (v===')' && stk.at(-1)==='(') stk.pop();
        else return false;
    }

    return stk.length>0 ? false : true;
}

 

for문, while문, forEach메서드 등 같은 순회하는 기능인데 성능을 비교하고 싶다.

다른 사람의 풀이를 보니 인덱스로 풀었다. 대단하다.

굳이 스택 배열을 사용하지 않고 정수로만 표현해도 될 것 같다. ( 스택에는 '('만 들어가기 때문이다.)