알고리즘 문제 풀이(백준 - 킥다운)

백준 GOLD 5(킥다운)

• 사용 언어 : javascript

• 해결 날짜 : 2023-01-29

• 해결 방법 :

  • 나올 수 있는 최대 길이는 두 기어의 합, 최소 길이는 두 기어 중 긴 기어의 길이
  • 두 기어 중 짧은 기어를 아래 세 방법으로 움직여가며 맞물리는지 확인
    • 긴 기어의 좌측에서 짧은 기어를 걸치게 이동
    • 긴 기어의 우측에서 짧은 기어를 걸치게 이동
    • 긴 기어의 안쪽에서 짧은 기어를 겹치게 이동
  • 각 경우에서 맞물린다면 result를 짧은 값으로 갱신
    • 맞물리지 않은 경우는 두 기어의 겹치는 부분이 둘 다 ‘이’(2)인 경우

• 회고 :

  • x

• 코드

  const fs = require('fs');
  const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
  const input = fs.readFileSync(filePath).toString().trim();
  
  solution(input);
  
  function solution(props) {
    let [shortGear, longGear] = props.split('\n');
    if (shortGear.length > longGear.length) {
      const temp = shortGear;
      shortGear = longGear;
      longGear = temp;
    }
    let result = shortGear.length + longGear.length;
  
    for (let i = 0; i < shortGear.length; i++) {
      let isEngaged = true;
  
      for (let j = 0; j < i + 1; j++) {
        if (longGear[j] === '2' && shortGear[shortGear.length - (i + 1) + j] === '2') {
          isEngaged = false;
          break;
        }
      }
  
      if (isEngaged) {
        result = Math.min(result, shortGear.length + longGear.length - (i + 1));
      }
      isEngaged = true;
  
      for (let j = 0; j < i + 1; j++) {
        if (longGear[longGear.length - (i + 1) + j] === '2' && shortGear[j] === '2') {
          isEngaged = false;
          break;
        }
      }
  
      if (isEngaged) {
        result = Math.min(result, shortGear.length + longGear.length - (i + 1));
      }
    }
  
    for (let i = 0; i < longGear.length - shortGear.length; i++) {
      let isEngaged = true;
  
      for (let j = 0; j < shortGear.length; j++) {
        if (longGear[i + j] === '2' && shortGear[j] === '2') {
          isEngaged = false;
          break;
        }
      }
  
      if (isEngaged) {
        result = Math.min(result, longGear.length);
      }
    }
  
    console.log(result);
  }
  

• 출처: 백준