Byung Wook Park (박병욱)

Byung Wook Park (박병욱)

[프로그래머스] 방금그곡

✔️ 문제

✔️ 문제 이해

  • 네오는 라디오에서 방금 나왔던 음악을 찾으려고 한다.

  • 다음 포털의 방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.

  • 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.

  • 각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.

  • 음악이 00:00를 넘겨서까지 재생되는 일은 없다.

  • 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.

  • 조건이 일치하는 음악이 없을 때에는 “(None)” 을 반환한다.

  • 입력으로 네오가 기억한 멜로디를 담은 문자열 m과 방송된 곡들의 정보를 담고 있는 배열 musicinfos가 주어질때 네오가 찾으려는 음악의 제목을 구하여라.

  • 값 범위

    • 1 ≤ m ≤ 1439
    • musicinfos 는 100개 이하의 곡 정보를 담고 있는 배열이다.
    • 악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.

✔️ 알고리즘 설계

  1. 네오가 들은 멜로디와 방송된 곡 정보를 하나씩 비교하며 조건에 맞는 음악의 제목을 반환한다.

✔️ 상세 구현설명

  • 음악 제목, 재생이 시작되고 끝난 시각, 악보를 ‘,’ 을 기준으로 파싱한다.
  • 네오가 들은 멜로디와 악보에 있는 “대문자#” 형태의 음표를 “소문자” 형태로 바꿔줘 비교를 용이하게 한다.
  • 재생 시작, 종료 시간을 배열에서 정보를 얻어와 분단위로 계산한 다음 그 차이를 구해서 재생 시간을 구한다.
  • 재생시간과 악보를 통해 실제 재생된 악보 정보를 만든다.
  • 재생된 악보에 네오가 들은 멜로디가 포함 되는지 찾아본다. ( find 함수를 사용한다. )
  • 조건에 맞는 음악이 여러개일 경우 재생 시간이 긴 음악 제목을 반환한다. ( 이를 수행하기 위해 재생 시간을 음악 제목과 함께 저장해둔다.)
  • 조건에 맞고, 재생 시간까지 같은 음악이 여러개일 경우 먼저 재생된 음악 제목을 반환해야 하는데, 곡 정보를 앞에서부터 순차 접근하면 고려를 할 필요가 없다.

👨🏻‍💻 소스 코드

#include <string>
#include <vector>

using namespace std;

// "대문자#" 형태의 음표를 "소문자" 형태로 바꿔주는 함수.
string convert(string str) {
	string ret = "";
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '#') {
			ret.back() = tolower(ret.back());
		}
		else
			ret += str[i];
	}
	return ret;
}

string solution(string m, vector<string> musicinfos) {

	string answer = "";
	int answerTime = 0;

	string listen = convert(m); // 네오가 들은 멜로리 변환.

	for (int i = 0; i < musicinfos.size(); i++) { // 방송된 곡 정보를 하나씩 조회
		string st = "", et = "", title = "", note = "";

		// ','을 기준으로 곡 정보를 파싱한다. 
		int check = 0;
		for (int j = 0; j < musicinfos[i].size(); j++) { 
			if (musicinfos[i][j] == ',') check++;
			if (musicinfos[i][j] != ',' && check == 0)
				st += musicinfos[i][j];
			else if (musicinfos[i][j] != ',' && check == 1)
				et += musicinfos[i][j];
			else if (musicinfos[i][j] != ',' && check == 2)
				title += musicinfos[i][j];
			else if (musicinfos[i][j] != ',' && check == 3)
				note += musicinfos[i][j];
		}

		// 시작, 종료 시간을 분단위로 변환한 다음 그 차를 구해 재생시간을 구한다. 
		int start = ((st[0] - '0') * 10 + (st[1] - '0')) * 60 
            + ((st[3] - '0') * 10 + (st[4] - '0'));
        
		int end = ((et[0] - '0') * 10 + (et[1] - '0')) * 60 
            + ((et[3] - '0') * 10 + (et[4] - '0'));
        
		int playTime = end - start;

		if (playTime < listen.size()) continue;

		note = convert(note); // 악보 변환.
		string playNote = ""; // 재생된 악보 변수.

		// 재생시간과 악보를 통해 재생된 악보 정보를 만든다.
		for (int j = 0; j < playTime; j++) {
			if (j > note.size() - 1) { 
				playNote += note[j % note.size()];
			}
			else {
				playNote += note[j];
			}
		}

		// find 함수를 사용해 재생된 악보에 네오가 들은 멜로디가 있는지 찾는다. 
		if (playNote.find(listen) != string::npos) {

			if (answer.size() == 0) {
				answer = title;
				answerTime = playTime;
			}
			else { // 조건에 맞는 음악 제목이 여러개라면, 재생 시간이 긴 음악 제목이 정답이다.
				if (playTime > answerTime) { 
					answer = title;
					answerTime = playTime;
				}
			}
		}
		// 추가로, 곡 정보를 앞에서부터 순차 접근하므로 먼저 입력된 음악 제목이 반환된다. 
	}

	if (answer.size() == 0) return "(None)"; // 일치하는 곡이 없을 경우.
	return answer;
}

✔️ 문제 회고

  • 문제 자체는 특별한 알고리즘을 요구하지 않는다. 하지만 문자열 파싱 능력이 요구됐다.
  • 문자열 find 함수를 사용하여 어떤 문자열에 특정 문자열이 포함되는지 쉽게 판별할 수 있었다.
  • 강력한 문자열 조작이 가능한 파이썬을 사용하면 훨씬 쉽게 풀 수 있는 문제라고 생각했다. 나중에 파이썬으로 풀어봐야겠다.