[프로그래머스] JavaScript Lv2 - [3차] 방금그곡(17683)

개요

문제 이름: [3차] 방금그곡 (17683)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/17683
플랫폼: 프로그래머스
알고리즘 분류: 일반
소요 시간: 7시간

 

문제 전문

설명

입출력

 

 

문제 풀이

해설

이 문제는 네오가 기억하고 있는 멜로디를 바탕으로 실제로 방송된 음악을 찾는 문제입니다. 문제 해결을 위해서는 주어진 음악 정보를 바탕으로 실제로 재생된 멜로디를 구하고, 네오가 기억하고 있는 멜로디가 그 안에 포함되어 있는지를 확인해야 합니다.

 

문제 해결을 위한 접근 방식은 다음과 같습니다.

1. 네오가 기억하고 있는 멜로디와 음악 정보의 멜로디에서 '#'이 붙은 음을 소문자로 변환합니다.
   1. 이는 같은 음임에도 불구하고 '#'의 유무에 따라 다른 음으로 인식되는 것을 방지하기 위함입니다.
2. 음악 정보를 하나씩 확인하면서 다음 작업을 수행합니다.
   1. 시작 시간과 종료 시간을 분 단위로 변환하여 재생 시간을 계산합니다.
   2. 재생 시간과 멜로디 길이를 이용하여 실제로 재생된 멜로디를 구합니다.
   3. 네오가 기억하고 있는 멜로디가 실제 재생된 멜로디에 포함되어 있는지 확인합니다.
3. 포함되어 있다면, 해당 음악의 재생 시간과 이전에 찾은 음악의 재생 시간을 비교하여 더 긴 경우에 결과를 업데이트합니다. 재생 시간이 같다면 먼저 입력된 음악을 선택합니다.
4. 모든 음악 정보를 확인한 후, 찾은 음악의 제목을 반환합니다. 만약 찾지 못했다면 "(None)"을 반환합니다.

이 문제의 핵심은 주어진 정보를 바탕으로 실제로 재생된 멜로디를 구하는 것과 기억한 멜로디와의 포함 관계를 확인하는 것입니다. 또한, 재생 시간을 계산하여 가장 긴 재생 시간을 가진 음악을 선택해야 합니다.

 

시도

1차 시도  (실패)

function solution(m, musicinfos) {
	// 결과를 저장할 변수를 초기화
	let result = "(None)";
	let maxPlayTime = 0;

	// '#'이 붙은 음을 변환하는 함수
	function convertSharpNotes(melody) {
		return melody.replace(/C#/g, "c").replace(/D#/g, "d").replace(/F#/g, "f").replace(/G#/g, "g").replace(/A#/g, "a");
	}

	// 기억한 멜로디를 변환
	m = convertSharpNotes(m);

	// 각 음악 정보를 하나씩 확인
	for (let info of musicinfos) {
		// 음악 정보를 쉼표로 구분하여 분리
		let [startTime, endTime, title, melody] = info.split(",");

		// 시작 시간과 종료 시간을 분 단위로 변환
		let [startHour, startMin] = startTime.split(":").map(Number);
		let [endHour, endMin] = endTime.split(":").map(Number);
		let playTime = endHour * 60 + endMin - (startHour * 60 + startMin);

		// 멜로디에서 '#'이 붙은 음을 변환
		melody = convertSharpNotes(melody);

		// 실제 재생된 멜로디를 만듦
		let playedMelody = "";
		for (let i = 0; i < playTime; i++) {
			playedMelody += melody[i % melody.length];
		}

		// 기억한 멜로디가 재생된 멜로디에 포함되는지 확인
		if (playedMelody.includes(m)) {
			// 재생 시간이 더 길거나, 같은 경우 먼저 입력된 음악을 선택
			if (playTime > maxPlayTime) {
				result = title;
				maxPlayTime = playTime;
			}
		}
	}

	// 찾은 음악의 제목을 마지막으로 반환
	return result;
}

이 코드에서는 convertSharpNotes 함수를 사용하여 '#'이 붙은 음을 소문자로 변환합니다.

 

그리고 각 음악 정보를 확인하면서 시작 시간과 종료 시간을 분 단위로 변환하여 재생 시간을 계산하고, 재생 시간만큼 멜로디를 반복하여 실제로 재생된 멜로디를 만듭니다. 이때, 재생된 멜로디에 기억한 멜로디가 포함되어 있는지 확인하고, 포함되어 있다면 재생 시간과 입력 순서를 고려하여 결과를 업데이트합니다.

 

하지만 이 코드는 34번 테스트 케이스를 통과하지 못했습니다. 정확한 이유는 알 수 없지만... 아마도 멜로디를 반복하여 실제로 재생된 멜로디를 만드는 부분에서 문제가 있었을 것으로 추측됩니다...

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(n * m)
• 공간 복잡도: O(m)

위의 부족한 점을 개선하여 2차 시도를 진행했습니다.

 

2차 시도  (성공)

function solution(m, musicinfos) {
	// '#'이 붙은 음을 소문자로 변환하는 함수
	const convertSharp = (melody) => melody.replace(/(\w)#/g, (_, p) => p.toLowerCase());

	// 멜로디를 변환
	m = convertSharp(m);

	// 결과를 저장할 변수 초기화
	let result = { title: "(None)", playTime: 0 };

	musicinfos.forEach((info) => {
		// 음악 정보를 분해
		let [start, end, title, melody] = info.split(",");

		// 재생 시간 계산
		const [startHour, startMin] = start.split(":").map(Number);
		const [endHour, endMin] = end.split(":").map(Number);
		const playTime = endHour * 60 + endMin - (startHour * 60 + startMin);

		// 멜로디를 변환
		melody = convertSharp(melody);

		// 실제 재생된 멜로디 생성
		let playedMelody = melody.repeat(Math.floor(playTime / melody.length)) + melody.slice(0, playTime % melody.length);

		// 기억한 멜로디가 재생된 멜로디에 포함되는지 확인
		if (playedMelody.includes(m)) {
			// 조건에 맞는 경우 결과 업데이트
			if (playTime > result.playTime) {
				result = { title, playTime };
			}
		}
	});

	return result.title;
}

이 코드에서는 convertSharp 함수를 사용하여 '#'이 붙은 음을 소문자로 변환합니다. 이때, 정규식을 사용하여 변환하는데, (\w)#은 알파벳 문자 뒤에 '#'이 오는 패턴을 찾습니다. 그리고 (_, p) => p.toLowerCase()는 찾은 알파벳 문자를 소문자로 변환합니다.

 

그리고 각 음악 정보를 확인하면서 시작 시간과 종료 시간을 분 단위로 변환하여 재생 시간을 계산하고, 멜로디를 변환합니다. 그 다음, repeat와 slice 메서드를 사용하여 실제로 재생된 멜로디를 만듭니다. 구체적으로는 멜로디를 재생 시간을 멜로디의 길이로 나눈 몫만큼 반복하고, 나머지만큼 멜로디의 앞부분을 잘라서 붙입니다.

 

마지막으로, 재생된 멜로디에 기억한 멜로디가 포함되어 있는지 확인하고, 포함되어 있다면 재생 시간을 비교하여 결과를 업데이트합니다.

 

사용된 주요 메서드

• replace(): 문자열에서 특정 패턴을 다른 문자열로 Replace 합니다. 정규식을 사용할 수 있습니다.
• split(): 문자열을 지정된 구분자를 기준으로 나누어 배열로 반환합니다.
• map(): 배열의 각 요소에 대해 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환합니다.
• repeat(): 문자열을 주어진 횟수만큼 반복한 새로운 문자열을 반환합니다.
• slice(): 문자열의 일부를 추출하여 새로운 문자열을 반환합니다.
• includes(): 문자열이 특정 문자열을 포함하는지 확인하여 Boolean 값을 반환합니다.
• forEach(): 배열의 각 요소에 대해 주어진 함수를 실행합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(n * m)
  여기서 n은 음악 정보의 개수, m은 음악 정보의 멜로디 길이입니다.
• 공간 복잡도: O(m)
  여기서 m은 가장 긴 멜로디의 길이의 비례입니다.