[백준] 15926번: 현욱은 괄호왕이야!! (JavaScript)

 

 

---

 

문제

https://www.acmicpc.net/problem/15926

 

개념

자료구조, 스택

 

 

실행 결과

 

 

 

구현 코드(js)

const fs = require('fs');

// 백준 제출용
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 로컬 테스트용
// const filePath =
//   process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
// let input = fs.readFileSync(filePath).toString().trim().split('\n');

// 15926번 현우는 괄호왕이야!!
const n = Number(input.shift()); // 문자열의 길이
const str = input[0]; // 문자열
let stack = []; // 올바른 괄호 문자열인지 체크할 스택
let max = 0; // 최대 길이
let start = -1; // 현재 올바른 괄호 문자열의 시작 인덱스

for (let i = 0; i < str.length; i++) {
  // 여는 괄호의 위치를 스택에 저장
  if (str[i] === '(') {
    stack.push(i);
  }
  // 괄호 쌍인 경우: 닫는 괄호이고, 스택의 탑이 여는 괄호면 스택에서 제거
  else {
    if (stack.length > 0) {
      stack.pop();
      // 현재까지의 길이를 계산하기 위해 스택의 탑 인덱스를 저장
      let end = stack.length > 0 ? stack[stack.length - 1] : start;
      max = Math.max(max, i - end); //
    }
    // 잘못된 경우: 시작 인덱스를 현재로 초기화
    else {
      start = i;
    }
  }
}

console.log(max);

 

 

 

 

코드 설명

이 문제에서는 올바른 괄호 문자열을 여는 괄호 '('와 닫는 괄호 ')'로 이뤄진 문자열이라고 정의하고 있다.

단순히 () 같은 형식뿐만 아니라, (()). ((())) 이런 식으로 이루어진 형식도 올바른 괄호 문자열로 취급한다.

이는 Parenthesis String이라는 명칭으로 LeetCode에서도 풀 수 있는 꽤 유명한 문제이다.

 

문제의 의도를 이해했다면 이 문제는 스택으로 풀어야 한다는 것을 알 수 있다.

 

왜 스택인가?

 

괄호 문자열은 '('와 ')'가 중첩된 형태로 이루어져 있다. 

중첩된 괄호 문자열에서 가장 첫번째로 나오는 '('는 가장 마지막에 나오는 ')'와 매칭되어야 올바른 괄호 문자열이 된다. 이는 후입선출(LIFO) 구조를 가진 스택과 유사하다.

 

 

이러한 구조를 바탕으로 여는 괄호를 스택에 push해두고, 닫는 괄호를 만나면 올바른 괄호 문자열로 간주해 pop하면 된다.

문제에서 가장 긴 괄호 문자열을 찾으라고 했으므로, 매 단계에서 현재 매칭된 괄호 문자열을 체크해서 저장해야 한다.

 

for (let i = 0; i < str.length; i++) {
  // 여는 괄호의 위치를 스택에 저장
  if (str[i] === '(') {
    stack.push(i);
  }
  ...

 

 

이때 end 변수를 활용해, 올바른 괄호 문자열인 경우 현재 스택의 탑 인덱스를 저장하게 했다.

만약 스택에 남아있는 괄호가 하나도 없다면 시작 인덱스와 동일하게 설정하도록 했다.

이후 max 메소드를 활용해 최대 길이와 비교하여 만약 현재 길이가 더 길다면 갱신하도록 구현했다.

  else {
    if (stack.length > 0) {
      stack.pop();
      // 현재까지의 길이를 계산하기 위해 스택의 탑 인덱스를 저장
      let end = stack.length > 0 ? stack[stack.length - 1] : start;
      max = Math.max(max, i - end);
    }

 

 

만약 올바른 괄호 문자열이 아니라면, 현재 시작 인덱스를 초기화한다.

문제에서 요구하는 최대 괄호 문자열의 길이를 저장하기 위해 해당 과정이 필요하다.

// 잘못된 경우: 시작 인덱스를 현재로 초기화
    else {
      start = i;
    }
  }

 

 

---