[백준] 1316번 - 그룹 단어 체크 — 멈추지 않는 기록

728x90

문제 링크 : https://www.acmicpc.net/problem/1316

| 문제 탐색하기

1) 목표

: 주어진 단어에서 그룹단어의 개수를 출력한다.

2) 기능 명세서

(1) 입력 구문 파싱하기

: 단어의 개수, 문자열을 구분한다.

(2) 각 문자 별 그룹 단어 체크하도록 순회하기

: 각 배열 별로 순환하므로, reduce를 사용하여 총합을 구하기

(3) 각 문자 별 그룹 단어 체크하기

현재 문자가 직전 문자와 같은지 비교 (같지 않으면 진행)
-> 그룹 단어는 직전 문자와 이어서 작성될 수 있기에
현재 문자가 등장한 문자인지 확인
- 등장한 문자이면, 바로 그룹단어가 아님
- 등장하지 않은 문자이면, 사용한 단어 Set에 추가하고, 직전 문자로 업데이트

(4) 결과 출력

: 그룹단어의 개수를 출력한다.

| 고민이 되었던 부분

1) 그룹 단어를 어떻게 정의할 것인가?

: 그룹 단어는 한 문자가 등장한 이후에는 다른 문자가 나오기 전까지 연속해서만 등장해야 하는 단어였다. 그렇기에 같은 문자가 연속으로 반복되는 것은 괜찮지만, 중간에 다른 문자가 나온 뒤에 다시 같은 문자가 나오면 그룹 단어로 인정할 수 없는 이 조건을 어떻게 코드로 옮길 수 있을지 고민이 됐다. 이는 이전 문자와 이미 등장한 문자를 동시에 추적하는 방법으로 해결할 수 있을 것 같았다.

2) 이미 등장한 문자를 어떻게 관리할 것인가?

: 중복 체크 방법에 대해서, 배열로 관리하고 Includes를 사용할지, Set을 사용할지 고민이 됐다. 빠르게 중복을 체크하고, 문제의 크기(N <= 100, 단어 길이 <= 100)를 고려했을 때, Set을 고르게 되었다. Set은 중복 체크가 명확하고, 시간 복잡도도 O(1)이기에, 의미적으로 가장 적합한 선택이라고 판단했다.

| 처음 코드 & 개선이 필요한 점

function printResult(inputs) {
  // 1. 배열 분리
  const [n, ...words] = inputs;

  // 2. 각 문자 별 그룹 단어 체크 후 총 개수 반환
  return words.reduce((count, word) => count + checkGroupWord(word), 0);
}

// 특정 단어에 대한 그룹 단어인지 체크하는 함수
function checkGroupWord(word) {
  let isCheck = true; // 그룹단어 여부
  let beforeChar = ""; // 직전 문자
  let charSet = new Set(); // 등장한 문자를 담는 Set
  const wordCharArr = word.split(""); // 특정 단어를 문자로 분리한 배열

  // 1. 단어의 각 문자 별로 순회하면서 체크
  for (let i = 0; i < wordCharArr.length; i++) {
    // 2. 이전 문자와 현재 문자가 같은지 체크
    if (beforeChar === wordCharArr[i]) {
      continue;
    }

    // 3. 현재 문자가 이전에 등장했는지 체크
    if (!charSet.has(wordCharArr[i])) {
      // 3-1-1. 등장하지 않았으므로, 새로운 문자를 Set에 추가
      charSet.add(wordCharArr[i]);

      // 3-1-2. 현재 문자를 직전 문자로 할당
      beforeChar = wordCharArr[i];
    } else {
      // 3-2-1. 직전 문자와 현재 문자가 같지 않고, 현재 문자는 이전에 등장했기에 그룹단어로 미인정
      isCheck = false;
      break;
    }
  }
  return isCheck ? 1 : 0;
}

function main() {
  const fs = require("fs");
  const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

  const [n, ...words] = input;
  const N = Number(n);

  const output = printResult([N, ...words]);
  console.log(output);
}

if (require.main === module) {
  main();
}

module.exports = {
  printResult,
};

1) isCheck는 필요 없다.

: 그룹단어 여부를 관리하고자 isCheck 라는 변수를 사용하려고 했으나, early return을 도입하면 필요 없는 변수가 될 것 같았다.

2) word을 Split하여 배열로 관리할 필요가 없다.

: for(const char of string)과 같은 문법을 사용하면, 배열을 만들지 않고도 동일한 효과를 볼 수 있을 것 같았다.

3) else 구문을 지우자

: 현재 문자가 이전에 등장했는지 판단하는 구문인데, !를 사용한 점이 else를 사용하게 만들었다. 현재 문자가 이전에 등장한 단어였다면 바로 false를 리턴하는 형식이 좋을 것 같았다.

| 최종 코드

function printResult(inputs) {
  // 1. 배열 분리
  const [n, ...words] = inputs;

  // 2. 각 문자 별 그룹 단어 체크 후 총 개수 반환
  return words.reduce((count, word) => count + checkGroupWord(word), 0);
}

// 특정 단어에 대한 그룹 단어인지 체크하는 함수
function checkGroupWord(word) {
  const usedChars = new Set();
  let prevChar = "";

  for (const char of word) {
    if (char !== prevChar) {
      if (usedChars.has(char)) {
        return false;
      }
      usedChars.add(char);
      prevChar = char;
    }
  }
  return true;
}

function main() {
  const fs = require("fs");
  const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
  const output = printResult(input);
  console.log(output);
}

if (require.main === module) {
  main();
}

module.exports = {
  printResult,
};

| 느낀점

백준 문제를 종종 풀긴 했지만, 포스팅을 붙잡은 것은 오랜만이다. 문제에 대한 포스팅을 남기면, 더 생각 후 코딩도 가능해지고, 내가 어떤 점이 부족했고, 이를 어떻게 개선했는지에 대해서 더 기록하고 돌아볼 수 있어서 더욱 나의 것으로 만들 수 있을 것 같았다. 그래서 앞으로도 문제를 풀기 전에 포스팅을 먼저 적고, 생각 후 코딩을 하면서 문제를 풀고, AI의 도움을 받아 개선할 점에 대한 피드백을 받고 더 성장하는 프로그래밍 실력을 갖고 싶다.