[99클럽] 코딩테스트 스터디, 6일차 TIL - 비기너

 

1. 문제풀이

1) 문제, 전주 듣고 노래 맞히기 (백준, 31562)

윤수와 정환은 「전주 듣고 노래 맞히기」라는 게임을 할 예정이다. 「전주 듣고 노래 맞히기」는 주어진 노래의 전주를 듣고 먼저 제목을 맞히는 사람이 점수를 얻어 최종적으로 점수가 더 많은 사람이 이기는 게임이다. 절대 음감을 가진 윤수는 노래의 첫 네 음만 듣고도 어떤 노래든 바로 맞힐 수 있다. 따라서, 정환은 윤수를 이기기 위해 첫 세 음만으로 노래를 맞히게 해주는 프로그램을 만들려고 한다. 우선 정환이 알고 있는 노래 제목, 음이름 등을 데이터로 만든 뒤 프로그램을 구현하기 시작했다. 예를 들어, 다음은 TwinkleStar(반짝반짝 작은 별)의 악보 중 일부이다.

 

위 악보를 박자와 관계없이 음이름으로 표현하면 CCGGAAG가 된다.

윤수를 이기기 위해서는 이 프로그램이 첫 세 음인 CCG만으로 노래 제목인 TwinkleStar를 출력할 수 있어야 한다. 또한, 세상의 모든 노래를 아는 윤수와 다르게 정환은 음을 아는 노래가 N$N$개뿐이다. 그래서 프로그램에 N$N$개의 노래의 정보를 저장해 놓을 것이다. 만약 저장된 노래 중 입력한 첫 세 음으로 시작하는 노래가 여러 개 있어 무슨 노래인지 정확히 알 수 없는 경우 ?를 출력하고, 입력한 첫 세 음에 맞는 저장된 노래가 없을 경우 !를 출력한다.

정환을 도와서 첫 세 음만으로 본인이 음을 아는 노래를 맞히는 프로그램을 완성하자. 이 프로그램은 대문자와 소문자를 구분한다.

 

입력

첫 번째 줄에 정환이 음을 아는 노래의 개수 N, 정환이 맞히기를 시도할 노래의 개수 M이 공백으로 구분되어 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐 노래 제목의 길이 T, 영어 대소문자로 이루어진 문자열 노래 제목 S, 해당 노래에서 처음 등장하는 일곱 개의 음이름 a1,a2,a3,a4,a5,a6,a7이 공백으로 구분되어 주어진다.

 N+2번째 줄부터 M개의 줄에 걸쳐 정환이 맞히기를 시도할 노래의 첫 세 음의 음이름 b1,b2,b3가 공백으로 구분되어 주어진다.

주어지는 음이름은 각각 C, D, E, F, G, A, B 중 하나이다. 같은 제목이 두 번 이상 주어지지 않는다.

 

출력

정환이 맞히기를 시도할 각 노래에 대하여 프로그램에 저장된 노래와 첫 세 음이 동일한 노래가 하나만 있다면 해당 노래의 제목을, 두 개 이상이면 ?을, 없다면 !을 한 줄에 하나씩 출력한다.

2) 해석

- 첫 세음만으로 음을 아는 노래 맞히는 프로그램 개발

- 대소문자 구별

- 첫 줄에 노래 개수 N, 맞히기를 시도할 노래 개수 M이 공백으로 주어짐

- 두 번째 줄에 노래 제목의 길이 T, 노래 제목 S, 처음 등장하는 일곱 개의 음이름이 공백으로 주어짐

- N + 2번째 줄부터 M개의 줄에 걸쳐 맞히기를 시도할 노래 첫 세음의 음이름이 공백으로 주어짐

- 노래가 여러 개라 무슨 노래인지 알 수 없는 경우 : ?

- 저장된 노래가 없는 경우 : !

 

3) 풀이

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

const [N, M] = input[0].split(" ");

const songs = [];
for (let i = 1; i <= N; i++) {
  const [len, title, ...notes] = input[i].split(" ");
  songs.push({
    len,
    title,
    notes: notes.slice(0, 3).join(" "),
  });
}

const attempts = [];

for (let i = 1; i <= M; i++) {
  const firstThreeNotes = input[i + Number(N)];
  const result = {
    title: "",
    cnt: 0,
  };

  songs.forEach((song) => {
    if (song.notes === firstThreeNotes) {
      result.title = song.title;
      result.cnt += 1;
    }
  });

  if (result.cnt === 0) attempts.push("!");
  else if (result.cnt === 1) attempts.push(result.title);
  else attempts.push("?");
}

console.log(attempts.join("\n"));

 

songs 배열을 만들어 각 노래를 저장

> for문을 통해 문제 개수만큼 반복문 돌기

> songs 배열에서 해당하는 노래 찾아서 개수 저장

> cnt 개수에 따라 출력

 

위 순서대로 계획하고 코드를 짰다.

 

const [N, M] = input[0].split(" ");

const songs = [];
for (let i = 1; i <= N; i++) {
  const [len, title, ...notes] = input[i].split(" ");
  songs.push({
    len,
    title,
    notes: notes.slice(0, 3).join(" "),
  });
}

 

우슨 N, M에 input[0]번째 값을 넣어준다.

N은 노래 개수, M은 맞히기를 시도할 노래 개수이다.

 

그 후, 입력 받아온 데이터들을 songs 배열에 넣어준다.

for문을 통해 input에 있는 데이터들을 key, value로 가공해서 넣어준다.

 

notes에서 필요한 데이터는 첫 음 3개이기 때문에 slice로 삭제해줬다. 

문자열 그대로 비교할 것이기 떄문에 join으로 합쳐준다.

 

 

const attempts = [];

for (let i = 1; i <= M; i++) {
  const firstThreeNotes = input[i + Number(N)];
  const result = {
    title: "",
    cnt: 0,
  };

  songs.forEach((song) => {
    if (song.notes === firstThreeNotes) {
      result.title = song.title;
      result.cnt += 1;
    }
  });

  if (result.cnt === 0) attempts.push("!");
  else if (result.cnt === 1) attempts.push(result.title);
  else attempts.push("?");
}

 

attempts는 결과를 담을 배열이다.

 

이제 for문을 통해서 노래 맞히는 부분을 짜보자.

맞혀야 할 노래는 M개이므로 M만큼 반복문을 돌려준다.

 

firestThreeNotes는 문제 노래의 음 3개이다.

songs 배열에서 반복문을 돌려, 해당 음과 같은 음을 찾아서 result에 넣어준다.

title는 노래 제목을, cnt는 같은 음 노래 개수를 넣어줄 것이다.

 

반복문이 끝나면, cnt의 개수에 따라서 ! 혹은 title, ?를 출력하도록 만들어준다.

 

 

- 걸린시간

 

 

2. 리팩토링

const fs = require("fs");
const input = fs.readFileSync("./index.txt").toString().trim().split("\n");
const [N, M] = input[0].split(" ").map(Number);

// 노래 정보를 추출하여 첫 세 음을 기준으로 객체로 저장
const songs = input.slice(1, N + 1).map((line) => {
  const [_, title, ...notes] = line.split(" ");
  return { title, firstThreeNotes: notes.slice(0, 3).join(" ") };
});

// 특정 음에 대한 노래 제목을 찾는 함수
function findSongTitle(firstThreeNotes) {
  const matches = songs.filter(
    (song) => song.firstThreeNotes === firstThreeNotes
  );
  if (matches.length === 0) return "!";
  if (matches.length === 1) return matches[0].title;
  return "?";
}

// 맞히기를 시도하는 각 노래의 첫 세 음에 대한 결과를 생성
const attempts = input.slice(N + 1, N + 1 + M).map(findSongTitle);

// 결과 출력
console.log(attempts.join("\n"));

 

 

const songs = input.slice(1, N + 1).map((line) => {
  const [_, title, ...notes] = line.split(" ");
  return { title, firstThreeNotes: notes.slice(0, 3).join(" ") };
});

 

 

우선 가독성을 위해서 for문이 아닌 map을 사용해 songs 배열을 만들어준다.

그리고 len 데이터는 사용하지 않기 때문에 _로 표시해준다.

 

_ : 사용하지 않는 데이터를 표시할 때 사용

 

 

// 특정 음에 대한 노래 제목을 찾는 함수
function findSongTitle(firstThreeNotes) {
  const matches = songs.filter(
    (song) => song.firstThreeNotes === firstThreeNotes
  );
  if (matches.length === 0) return "!";
  if (matches.length === 1) return matches[0].title;
  return "?";
}

// 맞히기를 시도하는 각 노래의 첫 세 음에 대한 결과를 생성
const attempts = input.slice(N + 1, N + 1 + M).map(findSongTitle);
console.log(attempts.join("\n"));

 

findSongTitle이라는 함수를 만들어서, 각 노래에 대한 음을 찾아준다.

 

음을 찾을 때는 filter 함수를 사용해 맞는 음만 배열로 빼내준다.

forEach보다 코드의 명확성을 잘 나타낼 수 있다.

 

사실 시간복잡도와 메모리는 크게 차이나지 않지만, 코드의 명확성을 위해 map, filter, _를 사용했다.

_의 경우 이런게 존재하는지 처음 알았다

앞으로는 코드 명확성도 잘 생각하면서 짜야겠다..

이제 변수명도 의미있게 지으려고 노력중인데 영어로 어떻게 바꿔야 할지 맨날 헷갈린다ㅠ

 

 

다른 사람 코드를 보니까 replaceAll을 사용한 경우도 있었다.

내 코드는 반복문 안에 또 반복문이 들어가서 시간이 좀 걸리는데, 해당 코드는 그게 아니라서 이게 시간이 훨씬 적게 걸리는것 같다!

최대한 이중으로 반복문 돌리는 건 없애봐야겠당,,