백준 2800번

QUESTION LINK

문자열 중에 괄호가 있는 곳을 찾고, 이 괄호들을 각자의 짝에 맞게 빼주어야 하는 문제였습니다. 각 괄호의 짝을 지어주는 부분이 중요했는데, 이는 왼쪽 괄호의 위치를 구하고, 오른쪽 괄호가 나올 때마다 마지막 왼쪽 괄호를 넣어주는 stack 구조를 활용하기로 했습니다. 문제를 푸는 순서는 다음과 같이 정했습니다.

1. 주어진 식에서 왼쪽 괄호가 보일 때마다 괄호 배열에 해당 위치값을 넣어주기
2. 1번에서 왼쪽 괄호를 순회하며, 오른쪽 괄호가 보일 때 왼쪽 괄호 배열의 마지막 값을 빼내어 서로 연결해주는 객체에 저장하기
3. 각 괄호 짝이 없어지는 경우의 수가 담긴 배열 만들기
4. 경우의 수 배열을 정렬하기

위 순서를 통해 진행을 하며, 1, 2번의 경우는 아래 코드와 같이 주어진 문자열을 forEach로 순회하며 진행하는 것으로 코드를 구성했습니다.

const expressionArr = input[0].split("");
const leftStack = [];
// 왼쪽 괄호를 담은 stack
const matchObj = {};
// 왼쪽 오른쪽 짝을 알려주는 객체

// 순회를 돌면서 왼쪽이 보일 때 stack에, 오른쪽이 보일 때 객체에 담아줌
expressionArr.forEach((word, idx) => {
  if (word === "(") leftStack.push(idx);
  if (word === ")") {
    const leftKey = leftStack.pop();
    matchObj[leftKey] = idx;
  }
});

// (2+(2*2)+2) 일 때,
// matchObj: { '0': 10, '3': 7 } 결과값이 나옴

그리고 주어진 matchObj 정보를 토대로 경우의 수를 구해야했는데, 이 때 경우의 수를 구하는 방법에 대한 고민이 많았고, 결론적으로 조합(Combination)을 적용해 1개부터 최대 개수의 괄호쌍이 없어질 때까지의 경우의 수를 찾아 없어졌을 때의 문자열을 결과 배열에 담아주면 되었습니다.

// 조합을 통한 경우의 수를 구하는 함수
const getCombination = (array, selectedNumber) => {
  const results = [];
  // 결과 배열
  if (selectedNumber === 1) return array.map((v) => [v]);
  // 선택의 가지수가 하나일 때에는 주어진 배열에서 각 요소를 배열로 만든 값을 리턴함
  // [[1],[2],[3]]의 형태

  array.forEach((fixed, index) => {
    // 각 요소를 고정값으로 두고, 요소의 뒷 부분부터 다시 조합을 적용함
    const rest = array.slice(index + 1);
    if (!rest.length) return;

    const restCombination = getCombination(rest, selectedNumber - 1);
    const attached = restCombination.map((v) => [fixed, ...v]);
    // 기존 고정값에 새롭게 적용된 조합들을 적용
    results.push(...attached);
  });

  return results;
};

위 조합 함수를 1개부터 n개의 괄호쌍이 빠질 때까지 찾아주어야 하므로 아래와 같이 while문으로 경우의 수를 모두 구해줄 수 있습니다.

const matchKeys = Object.keys(matchObj);
let i = 1;

while (i <= matchKeys.length) {
  const combination = getCombination(matchKeys, i);
  i += 1;
}

// [ [ '0' ], [ '3' ] ], [ [ '0', '3' ] ]

마지막으로, 주어진 경우의 수 배열을 갖고 해당 위치의 괄호들을 없앤 문자열을 리턴하는 함수를 만들어 적용하도록 했습니다.

const getRemovedByTargets = (targets) => {
  const newExpressionArr = [...expressionArr];
  // 새롭게 만들어질 문자열을 나누어둔 배열
  targets.forEach((target) => {
    // 문자열에서 지정된 부분들을 모두 제거
    newExpressionArr[target] = undefined;
    newExpressionArr[matchObj[target]] = undefined;
  });
  // 문자열을 생성하여 리턴
  return newExpressionArr.join("");
};

const resultArray = new Set();
// ((1))과 같은 괄호가 존재하는 경우에 대한 처리가 필요해 Set으로 처리
const matchKeys = Object.keys(matchObj);
let i = 1;

while (i <= matchKeys.length) {
  const combination = getCombination(matchKeys, i);
  // 생성된 combination에서 각 경우의 수들을 적용한 문자열을 결과값에 넣어줌
  combination.forEach((value) => {
    const removed = getRemovedByTargets(value);
    resultArray.add(removed);
  });
  i += 1;
}

// 결과 리턴
const result = [...resultArray].sort().join("\n");
console.log(result);

이번 문제를 풀며, 가장 어려움을 느낀 곳은 조합 함수를 만드는 것이었습니다. 조합이 코드로 이루어지는 과정에서 재귀 함수를 사용하고 이 때, 재귀 함수가 종료되는 시점을 파악하는 것이 어려웠습니다. 항상 조합과 함께 따라오는 순열을 적용하는 함수를 만드는 것에 대한 공부도 필요합니다.

추가적으로, 예외 처리를 할 때 문제가 발생했었는데, 괄호가 중복으로 발생할 때에 대한 처리가 처음에는 제대로 이루어지지 않아 틀렸다는 결과가 나왔습니다. 그래서 위와 같이 const resultArray = new Set();를 사용하여 문제를 해결할 수 있었고, 예외 처리에 대한 고려가 더 필요하다는 걸 알 수 있었습니다.

GITHUB  EMAIL