[백준] 1013 Contact - javascript

📌 문제

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

📌 풀이

구현을 이용한 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const strs = input.slice(1).map((str) => str.trim());

function checkPattern(str) {
  let index = 0;
  while (index < str.length) {
    if (str[index] === '1') {
      if (index + 2 < str.length && str[index + 1] === '0' && str[index + 2] === '0') {
        index += 3;
        while (index < str.length && str[index] === '0') index++;

        if (str[index] === '1') index++;
        else return false;

        while (index < str.length && str[index] === '1') {
          if (index + 2 < str.length && str[index + 1] === '0' && str[index + 2] === '0') break;
          else index++;
        }
      } else return false;
    } else {
      if (str[index + 1] === '1') index += 2;
      else return false;
    }
  }
  return true;
}
strs.map((str) => {
  if (checkPattern(str)) console.log('YES');
  else console.log('NO');
});

정규표현식을 이용한 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const strs = input.slice(1).map((str) => str.trim());

strs.map((str) => {
  if (/^(100+1+|01)+$/.test(str)) console.log('YES');
  else console.log('NO');
});

✔ 알고리즘 : 문자열 (정규표현식)

✔ str을 index로 순회하며 1인 경우와 0인 경우로 나누어서 판단

✔ 1인 경우
1인 경우 뒤에 무조건 00이 와야함 아닌 경우, false 반환 👉 100이 온 다음부터는 0이 안나올때 까지 index 1씩 증가 👉 1이 최소한 1개 이상 와야 하므로 str[index] 가 1인지 check 아닌 경우, false 반환 👉 뒤에 100이 나오지 않을 경우에만 1인지 check 하여 index 1 증가

❓ 왜 100이 나오지 않을 경우에만 1인지 check 해야하는가
10011001 인 경우 10011 을 지우면 001이 남게 되는데 패턴으로 001을 만들 수 없으므로 NO를 출력하지만 1001을 지우면 1001이 남게 되어 패턴으로 만들 수 있게 된다.

✔ 0인 경우
0인 경우 바로 뒤에 1이 와야지만 패턴에 일치하므로 1인 경우는 index 2 증가하고 1이 아닌 경우, false 반환

✔ 아래의 정규표현식으로도 판별이 가능

/^(100+1+|01)+$/.test(str)

✔ 난이도 : 백준 기준 골드 5