문제 정리❗️

알고리즘에 개념 학습도 좋지만 어제, 오늘은 kakao의 구현문제를 학습했다. kakao의 문제를 풀다보니 level2와 level3의 차이를 알 거 같다. level2는 시간복잡도를 크게 신경쓰지 않고 구현이 가능하면 통과하도록 문제를 내주신 거 같다. 그런데 level3는 시간복잡도까지 고려를 해서 문제를 해결해야 통과 할 수 있다. 오늘은 level2의 문제를 해결했다..!
이 문제를 풀며 map, split, reduce등 배열을 다루는 메서드를 자유롭게 써볼 수 있었고 정규식을 활용한 string type data 변환도 할 수 있었다.
그럼 먼제 문제를 보겠다!

방금그곡❗️

문제에 대한 설명은 흠 .. 네오는 라디오에서 나온 노래를 듣고있다. 그러다 좋은 노래를 발견했지만 흥얼거릴 수 만 있다. 라디오를 듣다보면 종종있는 일이다! 이런 상황을 문제로 내는 게 참 재미있다ㅎㅎ 카카오는 문제를 약간 흥미롭게 잘 만드는 거 같다. 그렇게 라디오에 나온 노래정보

[라디오 시작 시간 , 라디오 끝난 시간, 노래이름, 노래 코드]

그리고 네오가 흥얼거리는 노래코드

[네오가 들었던 코드]

이렇게 2개의 Input이 주어지고 Input의 최대 크기는 약 1000이다. (10^3)

먼저 다음과 같은 로직으로 생각을 했다.

1. 라디오 시간 정보를 분으로 변경하자. 왜냐하면 라디오에 나온 노래 길이 순서로 정렬해서 첫 번째에 오는 것이 답이고 또, 라디오 시간만큼 music의 코드를 가져올 수 있기 때문이다.

시간을 변환하기 ❓

필자가 변환한 방법은 split메서드와 map메서드 그리고 reduce를 활용해서 변경했다.

배열에서 시간 정보를 담고있는 [0][1] index를 뽑아서 ":"를 기준으로 다시 한번 배열을 만들어 그 안의 배열에서 [0]번 Index는 *60을 해주고 [1]번 Index는 1을 곱해서 반환한 후 reduce를 사용해 더해주었다. 코드는 다음과 같다.

musicinfos = musicinfos.map((musicinfo) =>
                            // 첫 번째 배열로 진입
      //["12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"]
    musicinfo.split(",").map((arr, index) => {
  // 내부의 string으로 이루어진 데이터를 배열로 만들어준다.
  // 그 후 0번 1번 인덱스에 접근 
      if (index === 0 || index === 1) {
        return arr
        // 해당 index의 arr은 한 번 더 배열화 되어 ":"를 기준으로 분리된다. 
          .split(":")
          .map((i, index) => {
            if (index === 0) {
              return i * 60;
              //이 때 시간에 해당하는 index 0은 *60을 해서 분으로 만들고
            }
            return i * 1;// 이 때 분에 해당하는 index 1은 그대로 return 한다.
          })
          .reduce((cur, acc) => acc + cur);
      }
  //그럼 index===0일 때 즉 [12:00]은 => 60 x 12 + 0으로 720이 return 된다.
  // index===1일 때는 [12:14] => 60 x 12 + 14 
    
      return arr;
    })
  );

필자가 사용한 방법은 사실 순회를 많이해야해서 시간복잡도에서는 불리하다.
따져보면 map이 총 3번 사용됨으로 n^4의 시간복잡도를 갖을 것이다.

2. 변경된 시간을 기준으로 sort(정렬)하자!
   문제 조건에서 라디오 나온 노래길이가 가장 긴 것이 정답이라고 나와있다!

3 실제 방송된 노래의 코드를 구하자!
그렇게해야 네오가 들었던 코드와 실제 방송된 코드를 비교하여 일치한 노래를 찾을 수 있다.

첫 번째 시도 ❗️(실패)

function solution(m, musicinfos) {
  const answer = [];
  //시간을 변환시키는게 가장 먼저 할일
  musicinfos = musicinfos.map((musicinfo) =>
    musicinfo.split(",").map((arr, index) => {
      if (index === 0 || index === 1) {
        return arr
          .split(":")
          .map((i, index) => {
            if (index === 0) {
              return i * 60;
            }
            return i * 1;
          })
          .reduce((cur, acc) => acc + cur);
      }
      return arr;
    })
  );
  // 분으로 변경뒤 그 차이를 알 수 있게 됨

  musicinfos.sort((a, b) => b[1] - b[0] - (a[1] - a[0]));

  let fullSongArr = [];

  for (let i = 0; i < musicinfos.length; i++) {
    let songLength = musicinfos[i][1] - musicinfos[i][0];
    let sshapCount = musicinfos[i][3]
      .split("")
      .filter((item) => item === "#").length;
    let fullSong = musicinfos[i][3];
    const originSongLength = [...fullSong].length;
    if (fullSong.length - sshapCount < songLength) {
      while (fullSong.length - sshapCount < songLength) {
        for (let j = 0; j < originSongLength; j++) {
          if (fullSong.length - sshapCount === songLength) {
            break;
          }
          fullSong = fullSong + fullSong[j];
          if (fullSong[j] === "#") {
            sshapCount = sshapCount + 1;
          }
        }
      }
    }

    fullSongArr.push(fullSong);
  }

  fullSongArr.forEach((item, index) => {
    if (item.includes(m)) {
      answer.push(musicinfos[index][2]);
    }
  });

  return answer;
}

위 코드는 "#"이 문제였다.. #을 count에서 제거하여 진짜 노래길이를 찾아낼 수는 있었지만 후에 includes를 사용하려면 #이 분간이 되지 않았다. 왜냐하면 "ABC#" 의노래가 있고 내가 들은 노래가 "ABC"라면 이는 같은 노래가 아님에도 includes는 true를 return하여 잘못된 결과를 가져온다.
그렇다면 어떻게 할 수 있을까?

정규식으로 변경하기 ❗️

코딩테스트를 해오며 정규식을 잘 쓰지 않았었다. 이유는 정규식의 사용방법이 외울때쯤 까먹고 외울때쯤 까먹고해서 결국 늘 까먹은 상태여서 사용할 수가 없었다..ㅎ 그런데 부담을 내려놓고 그냥 간단한 replace메소드에 정규식을 사용한다고 생각하니 생각보다 별게 아니었다.

도움을 받은 정규식 사용 블로그

replace(바꿀거,뭐로바꿀껀데)

이게 다였다.. 바꿀거에 정규식이 들어가면 원하는 string으로 변경이 가능하다.

그런데 replace를 그냥 위와 같이 쓰면 처음 target만 변경이 되고 전체가 변경되진 않는다. 이때 정규식을 사용햇 전체를 바꾸어 줄 수 있다.

let str = 'Hello world, Java, Java, Java';
str = str.replace(/Java/g, 'JavaScript');
console.log(str);
// `Hello world, JavaScript, JavaScript, JavaScript`

그렇게 #이 붙은 코드는 다른 코드로 아예 변경을 해버렸고 includes를 사용할 수 있게 됐다..!

두 번째 시도 ❗️ (성공 😁)

function solution(m, musicinfos) {
  m = m.replace(/C#/g, "Z");
  m = m.replace(/D#/g, "X");
  m = m.replace(/F#/g, "V");
  m = m.replace(/G#/g, "N");
  m = m.replace(/A#/g, "M");
// 각 코드를 변경할 수 있다. 

  const answer = [];
  musicinfos = musicinfos.map((musicinfo) =>
    musicinfo.split(",").map((arr, index) => {
      if (index === 0 || index === 1) {
        return arr
          .split(":")
          .map((i, index) => {
            if (index === 0) {
              return i * 60;
            }
            return i * 1;
          })
          .reduce((cur, acc) => acc + cur);
      }
      // 시간을 분으로 변경 후 더해주고
      if (index === 3) {
        arr = arr.replace(/C#/g, "Z");
        arr = arr.replace(/D#/g, "X");
        arr = arr.replace(/F#/g, "V");
        arr = arr.replace(/G#/g, "N");
        arr = arr.replace(/A#/g, "M");
        return arr;
      }
      // 코드는 #이 붙었다면 변경을 해주고
      return arr;
    })
  );

  musicinfos.sort((a, b) => b[1] - b[0] - (a[1] - a[0]));
// 라디오에 많이 나온 노래 순서대로 정렬해주고

  let fullSongArr = [];

  for (let i = 0; i < musicinfos.length; i++) {
    let songLength = musicinfos[i][1] - musicinfos[i][0];
    let fullSong = musicinfos[i][3];
    const originSongLength = [...fullSong].length;
    //  노래 길이가 라디오에 나온 노래길이보다 작을 경우는 
    // 내가 들었던 노래의 길이를 모두 알아야 하니까 라디오에 나왔던 코드를 똑같이 만들어주어야한다.
    if (fullSong.length < songLength) {
      while (fullSong.length < songLength) {
        for (let j = 0; j < originSongLength; j++) {
          if (fullSong.length === songLength) {
            break;
          }
          fullSong = fullSong + fullSong[j];
        }
      }
    } else if (fullSong.length >= songLength) {
      fullSong = musicinfos[i][3].slice(0, songLength);
      // 노래길이보다 라이도에 나온 노래길이가 짧다면 라디오에 나온 즉 내가 들었던 노래 길이만큼만 짤라야한다.
    }

    fullSongArr.push(fullSong);
  }

  fullSongArr.forEach((item, index) => {

    if (item.includes(m)) {
      answer.push(musicinfos[index][2]);
    }
    // 라디오에 나온 노래길이와 내가 들었던 노래길이가 같고 그 내용이 같다면
    // 정답으로 간주한다
  });

  return answer.length === 0 ? "(None)" : answer[0];
}

이번 구현 문제는 로직을 세우는 것 보다 시간을 변경하거나 또 "#"을 처리하는 등 디테일한 부분을 잘 캐치해야 풀 수 있는 문제같았다. 결국 위 문제에 대한 독해가 잘 이루어져야 풀 수 있는 문제라고 생각한다. 문제를 더욱 주의 깊게 읽는 연습도 필요하다 !