6장은 자료구조(스택 배열, 큐 배열)에 관련된 문제다.
문제
괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.
(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.
[입력설명]
첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.
[출력설명]
첫 번째 줄에 YES, NO를 출력한다.
입력예제 1
(()(()))(()
출력예제 1
NO
문제 풀이
예습 이론
- 스택(stack)은 배열으로, 가장 마지막에 들어간게 먼저 나오는 LIFO 구조이다.
스택은 배열이기 때문에, 생성할 때let stack=[]와 같이 하면 된다. stack에 요소 x를 삽입하고 싶다면stack.push(x), 요소를 꺼내고 싶다면stack.pop()을 하면된다. LIFO이기 때문에, pop을 하면 가장 마지막에 들어간 요소가 나오게 된다. - 이후에 나오는 큐(queue) 역시 배열으로, 스택과 달리 가장 먼저 들어간게 먼저 나오는 FIFO 구조이다.
코드
이 문제는 스택(stack)을 활용한 문제이다.
(1) 여는 괄호가 나오면 stack.push(x)
(2) 닫는 괄호가 나오면 stack.pop() (만약, pop할것이 없다면 return "NO")
(3) 마지막에도 stack에 남아있는것이 있다면, return "NO"
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(s){
let answer="YES";
let stack=[];
for(let x of s){
if(x==='(') stack.push(x);
else{
//뺄려고 했는데, stack이 비어있다면
if(stack.length===0) return "NO";
stack.pop();
}
}
if(stack.length>0) return "NO";
return answer;
}
let a="(()(()))(()";
console.log(solution(a));
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/13