문제 및 제한사항
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- "()()" 또는 "(())()" 는 올바른 괄호입니다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
**제한사항**
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
풀이 방법
1. 실패했던 스택 형태로 설명해보겠다.
스택은 후입선출의 방식으로 데이터를 저장 및 관리한다. 책상 위에 책을 올릴 때 맨 위에 올린 책부터 빼는 모양새다.
배열에 데이터를 추가할 때 push로 데이터를 추가한다. 그럼 1, 2, 3, 4 중 4가 가장 늦게 들어왔으나 pop을 사용해 4부터 지워준다.
이런 식의 자료구조가 스택인데, 이 문제는 스택/큐 형태로 풀어야 할 것 같았으나 그렇게 하니 유효성에서 빠꾸가 났다.
아무튼 stack이라는 빈 배열을 선언한 후, 문자열 s를 for문으로 순회한다. 만약 s[i]가 '('라면 stack에 push한다.
'('가 아닐 때에, 즉 ')'일 때는 2가지 경우가 있다.
1) stack의 길이가 0인지 ==> '('가 없는 상태에서 지금 ')'를 만난 거다. ==> false
2) stack.pop() ==> stack에 '('가 있으므로 ')'를 만나 지워준다.
이 구조를 반복하며 for문의 바깥에는 그래서 stack의 길이가 0인지를 확인한다.
정상적인 () 의 형태로 잘 열리고 닫혔다면 모두 pop되어 stack이 비어 있을 것이기 때문이다.
그런데 이 구조로 문제를 풀면 유효성에서 오류가 난다.
왜냐하면 문자열이 길 때, 일일이 push pop을 반복하기 때문이다.
2. 그렇다면...
배열로 반복하지 말고 숫자로 풀어보았다.
1번과 동일한데, count = 0 으로 선언한 후 '('라면 1을 더해주고 ')'라면 1을 빼 정상적인 ()의 형태일 때 0인지 확인하면 된다.
대신 여기선 stack의 길이가 0인지 확인할 수 있는 방법을 count가 음수인지로 바꿨다.
만약 '('보다 ')'가 많으면 뺄셈이 더 많아져서 음수가 되기 때문이다.
스택과 큐를 공부해볼 수 있었던 문제였다.
코드
function solution(s) {
let count = 0;
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (char === '(') {
count++;
} else {
count--;
}
if (count < 0) {
return false;
}
}
return count === 0;
}
'⚙️ 코딩테스트' 카테고리의 다른 글
[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 이진 변환 반복하기 (0) | 2023.04.10 |
---|---|
[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 최솟값 만들기 (0) | 2023.04.09 |
[JavaScript] 프로그래머스 코딩테스트 레벨 2 : JadenCase 문자열 만들기 (0) | 2023.04.08 |
[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 최댓값과 최솟값 (0) | 2023.04.08 |
[JavaScript] 프로그래머스 코딩테스트 레벨 1 : 문자열 내림차순으로 배치하기 (0) | 2023.04.08 |