[프로그래머스] 방금그곡 (2018 KAKAO BLIND RECRUITMENT)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/17683

 

 

이번 문제는 시간복잡도를 고려할 필요없는 파씽문제이다. 

그렇기에 연산적인 효율보다는 그냥 구현하기 편한대로 구현하였다.

 

<전체적인 알고리즘> 

1. 우선 파씽을 한다,  파씽을 하여 재생시간을 구해준 후 재생시간 동안만큼의 악보를 재작성한다.

2. 재작성한 악보에 주어진 음계m이 포함되어 있다면 조건과 일치하는 음악이다.

  2-1 조건과 일치한 음악 중에 재생 시간이 가장 긴 것을 고른다.

  2-2 재생 시간이 가장 긴 것 중에선 제일 앞쪽 제목을 선택

 

<전체 코드>

#include<iostream>
#include<vector>
#include<string>

using namespace std;

string m;
vector<string> musicinfos;

string time_to_minute(string tmp)  //시간을 분으로 바꿔줌
{
	string hour_str = tmp.substr(0, 2);
	string minute_str = tmp.substr(3, 2);
	int hour = stoi(hour_str);
	int minute = stoi(minute_str);
	int total= hour * 60 + minute;
	return to_string(total);
}
string changing_sheet(string sheet)  //#음계를 소문자로 변경(분당 소문자 하나 맞추기 위해)
{                                    // 물론 그냥 이 함수 안쓰고 #고려하며 바로 계산해줘도 됨
	string tmp = "";
	string score = "";
	for (int i = 0; i < sheet.size(); i++)
	{
		if (sheet[i] == '#')
		{
			score += tolower(tmp[0]);
			tmp = "";
		}
		else 
		{
			score += tmp;
			tmp = sheet[i];
		}	
	}
	if (tmp.size() > 0)score += tmp;
	return score;
}

vector<string> parsing(string str)   
{
	vector<string> v;
	string tmp = str.substr(0, 5);
	v.push_back(time_to_minute(tmp));  //시작 시간을 분으로 vector에 저장
    tmp = str.substr(6, 5);
	v.push_back(time_to_minute(tmp));   //끝나는 시간을 분으로 vector에 저장

	tmp = "";
	int i = 12;
	for (;str[i]!=','; i++)
	{
		tmp += str[i];
	}
	i++;
	v.push_back(tmp);  //음악 제목을 vector에 저장
	tmp = "";
	for (; i < str.size(); i++)
	{
		tmp += str[i];
	}
	tmp = changing_sheet(tmp);  //#음계는 소문자로
	int playing_time = stoi(v[1]) - stoi(v[0]);  //재생 시간
  
	string sheet = "";
	int index = 0;
	for (int i = 0; i < playing_time; i++)  //재생시간동안의 악보 작성
	{
		sheet += tmp[index];
		index++;

		if (index == tmp.size())index = 0;
	}
	
	v.push_back(sheet);  //재생된 만큼의 악보를 저장

	return v;
}

string solution(string m2, vector<string> musicinfos2) {
    
    m=m2;
    musicinfos=musicinfos2;
    
    m = changing_sheet(m); //#붙은 건 소문자로 바꿔줌
    int max_playing_time = 0;
	string answer = "";
	for (int i = 0; i < musicinfos.size(); i++)
	{
		vector<string> v = parsing(musicinfos[i]);

		int index = v[3].find(m);
		if (index >= 0)
		{
			if (stoi(v[1]) - stoi(v[0]) > max_playing_time)
			{
				max_playing_time = stoi(v[1]) - stoi(v[0]);
				answer = v[2];
			}
		}
	}
    
	if (answer.empty())answer = "(None)";
    
    return answer;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.