[백준 알고리즘] Node.js 1366. 기타 코드

1. 문제

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

1366번: 기타 코드

 

2. 풀이

• 오늘의 문제는 다른 분이 푼 해결 방법을 분석해보려고 한다.... ㅎㅎ;;;;;
• https://velog.io/@gihwan319/BOJ-1366-%EA%B8%B0%ED%83%80-%EC%BD%94%EB%93%9C

[BOJ] 1366 기타 코드

• 위의 C++로 푸신 걸 node.js로 변환하고 분석하려고 한다

const inputs = require('fs').readFileSync('/dev/stdin')
               .toString().trim().split("\n");
const [N, M] = inputs.shift().split(" ").map(v => +v);
let ans = Infinity;
let set = new Set();

// 기본 음계 Map으로 생성.
const scaleMap = new Map([
  ["A", 1],
  ["A#", 2],
  ["B", 3],
  ["C", 4],
  ["C#", 5],
  ["D", 6],
  ["D#", 7],
  ["E", 8],
  ["F", 9],
  ["F#", 10],
  ["G", 11],
  ["G#", 12]
]);

// 프렛을 눌렀을 때 실행되는 함수.
const play = (scales, code, difficulty, depth) => {
  if (depth === scales.length) {
    let l = 987654321, r = 0;
    for (let i = 0; i < scales.length; ++i) {
        set.add(difficulty[i][0]);

        if (difficulty[i][1] !== 0) {
            r = Math.max(r, difficulty[i][1]);
            l = Math.min(l, difficulty[i][1]);
        }
    }

    if (set.size === code.length) {
        if (l === 987654321) {
            ans = 0;
        } else if (r - l + 1 < ans) {
            ans = r - l + 1;
        }
    }

    set.clear();
    return;
  }

  for (let i = 0; i < code.length; ++i) {
      difficulty[depth][0] = code[i];
      difficulty[depth][1] = code[i] - scales[depth] + (code[i] >= scales[depth] ? 0 : 12);
      play(scales, code, difficulty, depth + 1);
      difficulty[depth][1] += 12;
      play(scales, code, difficulty, depth + 1);
  }
}

// 메인 함수
const main = () => {
  const scales = inputs.shift().split(" ").map(item => scaleMap.get(item));
  const codes = inputs.shift().split(" ").map(item => scaleMap.get(item));
  const difficulty = new Array(N).fill(null).map(() => [0,0]);

  play(scales, codes, difficulty, 0);

  console.log(ans);
}

main();

• 일단 정답만 보려는 사람들은 위의 코드를 참고하면 된다. 

 

3. 정리

• main function

const main = () => {
  // 둘째줄 음계를 담을 배열 / 담기는 형태 : [코드 번호, 코드 번호...]
  const scales = inputs.shift().split(" ").map(item => scaleMap.get(item));
  
  // 셋째줄 코드를 담을 배열 / 담기는 형태 : [코드 번호, 코드 번호...]
  const codes = inputs.shift().split(" ").map(item => scaleMap.get(item));
  
  // 난이도를 표현해줄 배열 / 담기는 형태 : [음계가 연주한 음, 음에 대한 난이도]
  const difficulty = new Array(N).fill(null).map(() => [0,0]);

  // play 함수 실행.
  play(scales, codes, difficulty, 0);

  console.log(ans);
}

main();

• play function

const play = (scales, code, difficulty, depth) => {
  // depth 와 음계의 길이가 동일해지면
  if (depth === scales.length) {
    let l = 987654321, r = 0; // 최솟값을 담을 l, 최댓값을 담을 r
    
    // 음계만큼 반복
    for (let i = 0; i < scales.length; ++i) {
        set.add(difficulty[i][0]); // Set 객체에 음계가 연주한 음을 담아줌.
		
        // 만약 음계가 연주한 음의 난이도가 0이 아니라면 최대값과 최솟값을 구해준다.
        if (difficulty[i][1] !== 0) {
            r = Math.max(r, difficulty[i][1]);
            l = Math.min(l, difficulty[i][1]);
        }
    }
    
    // Set 객체의 크기와 코드의 길이가 동일해지면
    if (set.size === code.length) {
        // 만약 최댓값이 처음 설정한 값과 동일하다면 프랫을 누를 이유가 없다는 의미이므로 ans = 0;
        // 그 외엔 최댓값 - 최솟값 + 1 의 값과 이전의 ans 값을 비교하면서 최솟값을 찾아나감.
        if (l === 987654321) {
            ans = 0;
        } else if (r - l + 1 < ans) {
            ans = r - l + 1;
        }
    }

    // 한 음계로 코드에 있는 한 음을 쳐봤으니 Set 객체를 초기화 해줌.
    set.clear();
    return;
  }

  // 코드에 있는 한 음을 쳐보기 위한 설정.
  // difficulty의 배열에 [[음계가 연주한 음, 해당 음에 대한 난이도], ...] 이런 형태로 되어 있음.
  // 만약 code에 있는 한 음이 scales에 있는 음보다 작다면 12를 더해줌. 12를 더하는 이유는 반복된다고 문제에 나와있기 때문.
  // 이후 play 함수를 다시 실행해서 ans를 구하고, 다시 12를 더하여 ans를 구함.
  for (let i = 0; i < code.length; ++i) {
      difficulty[depth][0] = code[i];
      difficulty[depth][1] = code[i] - scales[depth] + (code[i] >= scales[depth] ? 0 : 12);
      play(scales, code, difficulty, depth + 1);
      difficulty[depth][1] += 12;
      play(scales, code, difficulty, depth + 1);
  }
}

• 음계에 있는 한 음마다 코드에 있는 음을 칠 수 있게 하면서 난이도를 확인한다고 생각하면 된다고 한다.
• 왜냐하면.... 코드에 있는 음들 모두 한 번씩은 쳐야하기 때문에 다 점검해서 난이도의 최솟값을 찾아야한다.........
  • 이걸 풀려면 DFS, BFS를 이용해야한다고 생각은 했지만 막상 작성하려니까 숨이 턱 막혀버린;;;;;;
• 정리하면서도 이해하기 어려웠음. 다시 풀라해도 못 풀거 같음. 적게 풀고 정답률이 낮은 문제들은 진짜 뭔가 있나봄.