[백준] 1316: 그룹 단어 체커 (javascript)

Link

1316번: 그룹 단어 체커

문제

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.
단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

입력 > 첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.
출력 > 첫째 줄에 그룹 단어의 개수를 출력한다.

| 예제 입력

3
happy
new
year

| 예제 출력

3

 

제출

const input = (
  process.platform === "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `2
    aabb
    abc
    `
).split("\n");

const N = Number(input[0]);
let count = 0;

for (let i = 1; i <= N; i++) {
  let isGroupWord = [];
  const word = input[i].trim().split("");

  for (let j = 0; j < word.length; j++) {

    let indexArr = [];
    let index = word.indexOf(word[j]);

    while (index != -1) {
      indexArr.push(index);
      index = word.indexOf(word[j], index + 1);
    }

    if (indexArr.length === 1) {
      isGroupWord.push(true);
    } else {
      let isSequence = [];

      for (let m = 0; m < indexArr.length - 1; m++) {
        if (indexArr[m] + 1 === indexArr[m + 1]) {
          isSequence.push(indexArr[m]);
        }
      }
      isSequence.length + 1 === indexArr.length && isGroupWord.push(true);
    }
  }

  isGroupWord.filter((item) => item === true).length === word.length && count++;
}

console.log(count);

 

풀이과정

첫 번째 제출

단어의 문자에 해당하는 인덱스를 찾아서 인덱스 길이가 1이거나 연속적인 숫자의 배열 형태이면 그룹단어이다.

ex ) 주어진 단어 : aabb 일 때,
문자열이 첫번째로 나타나는 인덱스를 적어보면 1122가 된다.
인덱스가 연속적인 숫자 배열의 형태이므로 그룹단어가 된다.

ex ) 주어진 단어 : abc ▶️ 123
ex ) 주어진 단어 : a ▶️ 1
ex ) 주어진 단어 : abcca ▶️ 12331 => 연속적인 숫자의 배열 형태가 아니므로 그룹 단어가 아니다.

코드 분석

const N = Number(input[0]);
let count = 0;

for (let i = 1; i <= N; i++) {
  let isGroupWord = []; // 각 문자가 연속으로 나타나는만큼 true 요소를 가지고 있는 배열
  const word = input[i].trim().split(""); // 주어진 단어
  ...

문자가 연속적으로 나타남에 따라 true를 저장하기 위해 isGroupWord를 선언한다.

 

// 단어의 문자가 연속해서 나타나는지 확인하는 로직
for (let j = 0; j < word.length; j++) {
    let indexArr = []; // 지정된 문자의 모든 인덱스를 가지고 있는 배열
    let index = word.indexOf(word[j]); // 단어에서 지정된 문자의 첫 번째 인덱스

    // 지정된 문자의 인덱스를 indexArr 배열에 저장
    while (index != -1) {
      indexArr.push(index);
      index = word.indexOf(word[j], index + 1);
    }
...

• 입력받은 단어를 while문으로 순회하며 문자 하나의 인덱스를 indexArr에 저장한다.
  • ex) 입력받은 단어 : aabc
  • indexArr : [0, 1] => [2] => [3]
  • for문 한 번에 하나의 문자에 해당하는 index를 저장한다.

 

...
    // 지정된 문자 하나가 연속적으로 나온다면 isGroupWord에 true 값 넣기
    if (indexArr.length === 1) {
      isGroupWord.push(true);
    } else {
      let isSequence = [];
      for (let m = 0; m < indexArr.length - 1; m++) {
        if (indexArr[m] + 1 === indexArr[m + 1]) {
          isSequence.push(indexArr[m]);
        }
      }
      isSequence.length + 1 === indexArr.length && isGroupWord.push(true);
    }
}

• indexArr의 크기가 1이라면 입력받은 단어의 문자가 하나씩 연속해서 나오는 것이기 때문에 그룹 단어로 구별되어 isGroupWord에 true를 넣어준다.
  • ex) 입력받은 단어 : abc
  • indexArr : [0] => [1] => [2]
  • 따라서 indexArr의 크기가 1
• indexArr의 크기가 1이 아니라면 특정 문자가 2번이상 나타나는 것이다. 따라서, 특정 문자가 떨어져서 나오는지 판별하기 위해 isSeqeunce에 인덱스를 저장한다.
• 문자가 연속적으로 2번 이상 나온다면 isSequence의 길이와 indexArr의 길이는 1차이가 난다.
  • ex) 입력받은 단어 : aaab
  • isSeqeunce: [0, 1], indexArr : [0,1, 2] // 크기 차이 : 1
  • ex) 입력받은 단어 : aba
  • isSequence : [], indexArr : [0,2] // 크기 차이 : 2

 

isGroupWord.filter((item) => item === true).length === word.length && count++;

각 문자가 연속해서 나타난다면 단어의 길이와 isGroupWord의 true의 개수와 같아지기 때문에 count를 증가한다.

 

 

두 번째 제출

코드가 너무 복잡해져서 좀 더 효율적인 방법을 찾아봤다.

처음 발견된 문자를 letter 배열에 저장해놓고 특정 문자가 letter 배열에서의 인덱스와 letter 배열의 크기를 비교하면 그룹 단어를 찾을 수 있다.

const input = (
  process.platform === "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `3
      happy
      new
      year`
).split("\n");

const N = Number(input[0]);
let count = 0;

for (let i = 1; i <= N; i++) {
  const word = input[i].trim();
  const letter = []; // 처음 발견되는 문자의 배열
  let isGroupWord = true;

  for (let j = 0; j < word.length; j++) {
    if (letter.indexOf(word[j]) === -1) {
      // 처음 발견되는 문자일 경우
      letter.push(word[j]);
    } else {
      // 처음 발견되지 않은 문자일 경우
      if (letter.indexOf(word[j]) !== letter.length - 1) {
        // 특정 문자가 연속되어 나왔다면 그 문자는 letter 배열의 마지막 요소이다.
        // 따라서 특정 문자가 처음 발견된 인덱스와 letter 배열의 크기 - 1 한 값이 같지 않다면
        // 이전에 한번 발견되고 다시 발견된 경우이므로 그룹 단어가 아니다.
        isGroupWord = false;
        break;
      }
    }
  }
  if (isGroupWord) {
    count++;
  }
}

console.log(count);

예시

주어진 단어가 'azzca' 라고 할 때,

특정 문자가 연속적으로 반복된다면, letter에서의 특정 문자 인덱스와 (배열의 크기 - 1)의 값이 같다.

현재 문자 : a, letter = [a]
현재 문자 : z, letter = [a, z]
현재 문자 : z, letter = [a, z]    // letter.indexOf('z') = 1 , (letter.length - 1) = 1 ⭕
현재 문자 : c, letter = [a, z, c]
현재 문자 : a, letter = [a, z, c]    // letter.indexOf('a') = 0, (letter.length - 1) = 2 ❌

 

https://velog.io/@exploit017/%EB%B0%B1%EC%A4%80Node.js-1316%EB%B2%88-%EA%B7%B8%EB%A3%B9-%EB%8B%A8%EC%96%B4-%EC%B2%B4%EC%BB%A4

[백준/Node.js] 1316번: 그룹 단어 체커

 

 

개념

Array.prototype.indexOf()

• 배열이나 문자열에서 지정된 값이 등장하는 첫 번째 인덱스를 반환하고, 없으면 -1을 반환한다.

indexOf를 사용한 문제

[백준] 10809: 알파벳 찾기 (javascript)

 

---

 

Comment

기존 풀이 방법은 정답은 맞았지만, 좀 더 효율적인 코드가 있었다.

코드를 작성하면서도 조건문이 너무 많아지고 복잡해져서 나 스스로 의심이 들긴 했지만...ㅎㅎ

모든 코드에 정답은 없으니 너무 상심하진 말자!