항해 99 5기 TIL_56

▶ Today I Learned

 

<알고리즘>

 

 

[방금 그곡]

 

소요시간: 3시간 30분

해결 여부: 미해결

https://programmers.co.kr/learn/courses/30/lessons/17683

 

처음 시도한 코드

 

function solution(m, musicinfos) {
    
    let sameTimeArr = []

function findSong (m, info) {

  let answer = []

for (let i = 0 ; i < info.length ; i++) {

  let songNotes =  info[i].split(',')[3] // 악보 배열 길이가 음악 재생시간
  let startTime = info[i].split(',')[0]
  let finishTime = info[i].split(',')[1]

  let sHours = startTime.substring(0,2)/1
  let sMin = startTime.substring(3,5)/1
  let fHours = finishTime.substring(0,2)/1
  let fMin = finishTime.substring(3,5)/1
  
  let mins = ((fHours - sHours)*60 + (fMin - sMin))

// 음표 #의 길이 잠깐 제거하여 비교
   let noShop = songNotes.replace('#','')
 let notesToCompare = groupNotes(Math.ceil(mins/noShop.length), songNotes)


  // 들어본 멜로디가 악보에 포함된 경우 해당 제목 답 배열에 넣기
  if(notesToCompare.includes(m)) {
    answer.push(info[i].split(',')[2])
  }
  
}

  if (1 < answer.length) {
   // 일치하는 곡이 여러 개인 경우
let j = 0
    let thatIdx = []
    let times = []
    while (true) {
      let t = 0
      while (t < info.length) {

      if (info[t].indexOf(answer[j]) !== -1) {
      thatIdx.push(t) // 그 특정 곡이 포함되어있는 음악정보 배열의 인덱스를 찾기 위함
      }
      }
      
let startTime = info[thatIdx[j]].split(',')[0]
  let finishTime = info[thatIdx[j]].split(',')[1]
    
     let sHours = startTime.substring(0,2)/1
  let sMin = startTime.substring(3,5)/1
  let fHours = finishTime.substring(0,2)/1
  let fMin = finishTime.substring(3,5)/1
  
  let mins = ((fHours - sHours)*60 + (fMin - sMin))

      times.push([mins,t])
      j++
      if(!answer[j]) {
        // 곡들이 들어있는 info의 인덱스를 모두 찾았을 경우
        break;
      }
    }

    // 1) 조건에 따라 시간끼리 비교
    let k = 0
    while (true) {

      if (time[k][0]/1 < time[k+1][0]/1) {

        time.shift()
      } else if (time[k][0]/1 > time[k+1][0]/1) {
        let temporary = time[k][0]
        time[k][0] = time[k+1][0]
        time[k+1][0] = temporary
      } else {
      sameTimeArr.push(time[k][0]/1)
        time.shift()        
      }

      if (!time[k+1]) {
        
      if (sameTimeArr.length === 0) {

        return musicinfos(time[k][1]).split(',')[2] // 가장 긴 재생시간의 노래 제목 출력
      } else {
// 재생된 시간도 같을 경우 2) 먼저 입력된 음악 제목을 반환한다.
        return answer.shift()
      }
        
              }
      
      k++
    }
    
    
  } else if (answer.length === 0) {
  // 일치하는 곡이 없는 경우
    return "(None)"
  } else {
    // 일치하는 곡이 한 개인 경우
    return answer[0]
  }
}

// m과 비교할 악보 배열 생성
function groupNotes (a, songNotes) {

  let str = ''
 for (let i = 0 ; i < a ; i++) {
  str = str + songNotes
 }

  return str
}

return findSong(m, musicinfos)
    
}

처음 시도한 결과 테스트 3개 중 2개는 맞았지만

나머지 하나에서 다음과 같은 에러가 발생했다.

 

signal: aborted (core dumped)

구글링 해본 결과 메모리에 특정 값이 저장이 되어있는 것인지 알 수 없다는 식의 답변들만 보았는데

혹시나해서 replit에도 돌려보니 다음과 같은 알림이 떴다.

 

repl process died unexpectedly: signal: killed

통과못한 세번째 예제의 경우 입력 예제의 길이가 짧기 때문에 시간 초과 문제는 아닌 듯 하다.

원인을 좀 더 찾아보아야겠다.

그리고 추가적으로 하나의 문제를 또 발견했다.

let m = "ABC"
let musicinfos = ["12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"]

// 지정된 악보는 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 이렇게 12개 이다.

입력 값이 이럴 경우 현재 로직에서는 C#DEFGABC#DEFGAB 와 같이 재생된 악보에서 ABC를 인식하고 노래제목이 HELLO도 있다고 인식할 수 있다! 하지만 C와 C#은 다른 음이므로 ABC와 ABC#는 엄연히 달라 HELLO가 아닌 WORLD만 나와야 한다.

 

그래서 다음과 같이 코드에 조건을 추가해주었다.

// 기존 코드의 조건
notesToCompare.includes(m)

// 바꾼 조건
notesToCompare.includes(m) && notesToCompare[notesToCompare.search(m) + m.length] !== '#'

어차피 #이라는 건 음표의 뒤에만 붙는다. 문자열 첫부분은 신경쓸 필요가 없고 문자열 중간에도 #이 들어가있다면 애초에 includes(m)

조건에서 걸릴 것이다. 지금 감지하지 못하는 것은 문자열의 마지막 바로 뒤어 #이 있는 경우도 있다는 거니까 조건을 저렇게 바꾸어 주었다.

 

그랬더니 통과하지 못했던 세번째 케이스도 통과했다! 유후! ;)

 

하지만 제출한 결과,

시간 초과와 실패, 그리고 아까보았던 signal: aborted (core dumped) 까지 있었다.

내 생각에는 아마 1) 고려하지 못한 케이스가 있는 점 2) 시간 복잡도가 높다는 것 때문인 것 같다.

당장은 더 우선순위로 해야할 것들이 많아서 지금은 이 정도로 해두었다가 나중에 꼭 다시 풀어보고 해설도 찾아보면서 공부해보아야 겠다.

 

 

[설탕 배달]

 

소요시간: 30분

해결여부: 해결

백준 2839번

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

 

초반에는 단순히 5로 나누고 3으로 나눈 다음 각각의 몫을 더하거나 반대로 3으로 나눈다음 5로 나눈 몫을 더하는 걸 생각했다.

하지만 생각해보면 11과 같은 수는 ((11%5)%3 === 0 || (11%3)%5 ===0 가 될 수 없었다.

그레서 아래와 같이 3을 하나씩 빼가면서 5로 나누는 방법을 택했다.

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ')

let n = input[0]/1
let bags = 0
    
pack = n => {
 while(true) {
   if (n%5 === 0) {
     return n/5 + bags
   }
   if ( n <= 0 ) {
     return -1
   }
   n = n - 3
   bags++
 }
}
console.log(pack(n))

 

 

▶ 느낀 점

 

저런 문제를 40분 만에 풀어야 한다면 정말 쉽지 않을 것 같다.

문제를 보았을 때 핵심로직들이 바로바로 떠오르지 않는다면 아마 힘들지 않을까 생각한다.

그래도 확실히 처음 개발을 할 때 보다는 문제 해결 능력이 올라간 것 같다.

과거에 삼각형 구현 만으로도 힘들어하던 때가 있었는데 이제는 더욱 복잡한 문제들도 보면

무엇을 고려해야 하는지, 무엇이 중요한지가 좀 더 잘 보이게 되었다.

아직은 느리고 서툴지만, 아는 것이 많지 않지만, 스스로 고민해보고 다른 이들의 풀이법을 연구하며

나날이 발전해가는 나 자신이 되고 있고 앞으로도 그럴 것이다.

 

▶ 공부 시 참고 링크들

 

상단 페이지 내용 참조