문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/17683?
2018 카카오 블라인드 3차 코딩 테스트에서 나왔던 문제단순 구현 문제라고 생각되는데,
생각보다 구현해야 하는 함수 부분이 많아서 잘 정리하는 게 중요했다.
또한 예외 케이스가 많은 문제여서 테스트 케이스를 잘 짜는 것이 중요했다.
문제 핵심 및 풀이
멜로디와 일치하는 곡 찾기의 문제
멜로디(m)가 곡(musicInfo) 안에 있는지 확인하는 과정은,
일반적으로는 문자열 비교로 하면 된다.
하지만 입출력 예시 3번에서 볼 수 있듯이 #이 문제가 된다.
일반적인 문자열 비교로 찾을 때는,
m = "ABC" , musicInfo = "ABC#" 일 때, 조건 일치로 판단한다.
그래서 C#이나 D#, F# 등 #이 붙어있는 음들이
C, D, F와 구분될 수 있도록 따로 변환해 주기로 했다.
그래서 자료구조 map을 사용하여 각각의 멜로디를 모두 소문자로 만들되,
C#이나 D#같은 것은 겹치지 않도록 다른 문자로 매핑해 준다.
이는 자유롭게 매핑해 주면 된다.
매핑을 하는 방법
매핑을 하는 방법은 음악 문자열을 #을 기준으로 생각하면 된다.
다음 문자가 #이라면, 그 앞에는 무조건 A, B, C.. 등등의 음이 있을 것이다.
그래서 #을 앞의 문자에 붙여준다.
#뒤에는 더 이상 붙을 수 있는 게 없기 때문에, 이 문자를 키로 하는 값으로 매핑한다.
만약 다음 문자가 #이 아닌 경우에는 2가지로 나뉜다.
만약 앞에 문자가 있는 경우에는, AA, BB 이런 식의 키를 존재할 수 없다.
따라서 앞의 문자를 키로 하는 값을 매핑 한 뒤, 해당 다음 문자를 넣어준다.
비어있다면 그냥 넣어준다.
재생 시간 및 그 시간 동안의 기록
여기서 시작 시간과 종료 시간이 입력으로 들어온다.
근데 "HH:MM" 형식으로 들어오기 때문에 변환을 해서 사용해야 한다.
이때 단위 통일을 위해 H * 60을 하여 모두 분으로 바꿔준다.
이렇게 해주면 (종료시간)-(시작시간)을 통해 재생 시간을 구할 수 있다.
재생 시간을 알았으면, 이제 음악을 재생시간 동안 튼다.
여기서 재생 시간이 음악의 길이보다 길면 처음으로 다시 돌아간다.
그래서 원형 큐 구조를 만들듯이 mod(%) 연산을 사용한다.
(i % 음악의 길이)로 하면 음악의 인덱스를 계속 순회하게 된다.
실수하기 쉬운 부분
조건에 맞는 것이 없는 경우에는 "(None)"을 출력하라고 하는 것을 까먹으면 안 된다.
나는 이를 까먹어서 계속 틀렸다.
또한 이 문제는 인덱스가 밖으로 벗어나는 경우가 많기 때문에 주의해야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <sstream>
#include <iostream>
using namespace std;
// 필요한 정보를 담고 있는 구조체
struct Info{
int sTime;
int eTime;
string title;
string music;
};
// 각각의 모든 음들을 매핑해둠
map<string,string> mapper{{"C","c"},{"C#","x"},
{"D","d"},{"D#","y"},
{"E","e"},
{"F","f"},{"F#","z"},
{"G","g"},{"G#","k"},
{"A","a"},{"A#","t"},
{"B","b"}};
// HH:MM을 모두 분단위로 바꿈
int toMinutes(string t){
int bash = t.find(':'); // ':'를 기준으로 나누기 위해
int hour = stoi(t.substr(0,bash));
int minutes = stoi(t.substr(bash+1,2));
return hour*60+ minutes; // 분단위로 바꿈
}
// word를 매핑함
string mapOf(string word){
string result = ""; // 매핑한 전체 음
string unit = ""; // key를 구성하기 위한 문자열 모음
for(int i = 0; i < word.length(); i++){
// '#'인 경우, unit에 붙이고 result에 매핑해서 넣음
if(word[i] == '#') {
unit.push_back(word[i]);
result.append(mapper[unit]);
unit.clear(); // unit 내용 초기화
}
// '#'이 아닌 경우 + unit에 이미 값이 있는 경우
else if(unit.size() > 0){
// 기존에 있던 것을 키로 매핑해서 넣고 난 다음 이번껄 넣음
result.append(mapper[unit]);
unit.clear();
unit.push_back(word[i]);
}
// '#'도 아니고, 안이 비어있는 경우
else unit.push_back(word[i]);
}
// 아직 unit이 비어있지 않은 경우, result에 하나 더 넣음
//word가 #으로 끝나지 않으면 unit에 문자가 하나 남음
if(unit.length() > 0) result.append(mapper[unit]);
return result;
}
// 멜로디(target)과 곡(Info)가 일치하는지 확인
Info isCorrect(string target, Info info){
int time = info.eTime-info.sTime; // 재생 시간
string playLog = ""; // 재생시간동안 쌓인 음
string music = info.music;
target = mapOf(target); // 매핑
music = mapOf(music); // 매핑
for(int i = 0; i < time; i++){
char origin = music[i%music.length()]; // 인덱스가 넘을시 처음으로 돌아감
playLog.push_back(origin); // 로그에 넣음
}
// time이 0이거나, playLog안에 target이 어 없으면 빈 info를 반환
if(time == 0 || playLog.find(target) == string::npos) return {0,0,"",""};
return info;
}
string solution(string m, vector<string> musicinfos) {
string answer = "";
vector<Info> infoList;
for(auto musicInfo : musicinfos){
istringstream ss(musicInfo);
string buf;
vector<string> tmp;
while(getline(ss,buf,',')) tmp.push_back(buf);
infoList.push_back({toMinutes(tmp[0]),toMinutes(tmp[1]),tmp[2],tmp[3]});
}
int cntDist = -1; // 최대 재생 시간
for(auto info : infoList){
Info result = isCorrect(m,info);
if(result.music == "") continue;
//최대 재생 시간이 더 긴 경우만 갱신
if(result.eTime - result.sTime > cntDist){
cntDist = result.eTime - result.sTime;
answer = result.title;
}
}
// 값이 비어있는 경우 실패로 간주
if(answer == "") answer = "(None)";
return answer;
}↑
Java 구현 코드
↓
import java.util.*;
import java.util.stream.*;
class Solution {
// 필요한 정보를 담고 있는 클래스
public class Info{
int sTime;
int eTime;
String title;
String melody;
// 생성자
Info(int sTime,int eTime,String title,String melody){
this.sTime = sTime;
this.eTime = eTime;
this.title = title;
this.melody = melody;
}
}
// 각각의 모든 음들을 매핑해둠
Map<String,String> mapper = new HashMap<>(){{
put("C","c"); put("C#","x");
put("D","d"); put("D#","y");
put("E","e");
put("F","f"); put("F#","z");
put("G","g"); put("G#","k");
put("A","a"); put("A#","t");
put("B","b");
}};
// HH:MM을 모두 분단위로 바꿈
List<Info> infoList = new ArrayList<>();
public String solution(String m, String[] musicinfos) {
String answer = "";
for(String musicInfo : musicinfos){
String[] split = musicInfo.split(",");
infoList.add(new Info
(toMinute(split[0]),toMinute(split[1]),split[2],split[3]));
}
int dist = -1; // 최대 재생 시간
for(Info info : infoList){
Info tmp = getCorrectTitle(m,info);
if(tmp == null) continue;
// 재생 시간이 더 긴게 있는 경우에만 갱신
if(tmp.eTime - tmp.sTime > dist) {
dist = tmp.eTime - tmp.sTime;
answer = tmp.title;
}
}
// 값이 비었으면 실패로 간주
if(answer.equals("")) answer = "(None)";
return answer;
}
// 값을 매핑하는 함수
String toIndex(String origin){
StringBuilder result = new StringBuilder("");
StringBuilder sb = new StringBuilder("");
// '#'인 경우, unit에 붙이고 result에 매핑해서 넣음
for(int i = 0; i < origin.length(); i++){
if(origin.charAt(i) == '#') {
sb.append("#");
result.append(mapper.get(sb.toString()));
sb.delete(0,2); // 유닛 내용 삭제
}
// '#'이 아닌 경우 + unit에 이미 값이 있는 경우
else if(sb.length() > 0){
//기존에 있던 것을 키로 매핑해서 넣고 난 다음 이번껄 넣음
result.append(mapper.get(sb.toString()));
sb.delete(0,1);
sb.append(origin.charAt(i));
}
// '#'도 아니고, 안이 비어있는 경우
else sb.append(origin.charAt(i));
}
// 아직 unit이 비어있지 않은 경우, result에 하나 더 넣음
if(sb.length() > 0) result.append(mapper.get(sb.toString()));
return result.toString();
}
// HH:MM을 모두 분단위로 바꿈
int toMinute(String time){
String[] split = time.split(":"); // ':'을 기준으로 나눔
int hour = Integer.parseInt(split[0]);
int minute = Integer.parseInt(split[1]);
return hour*60 + minute; // 분으로 합침
}
// 멜로디(target)과 곡(Info)가 일치하는지 확인
Info getCorrectTitle(String target, Info info){
int playTime = info.eTime - info.sTime; // 재생 시간
String melody = info.melody;
StringBuilder cnt = new StringBuilder(""); // 재생시간 동안 쌓인 음
target = toIndex(target);
melody = toIndex(melody);
for(int i = 0; i < playTime; i++){
//인덱스가 넘을 시 처음으로 돌아감
cnt.append(melody.charAt(i%melody.length()));
}
// time이 0이거나, playLog안에 target이 어 없으면 빈 info를 반환
if(playTime <= 0 || cnt.toString().contains(target)) return info;
return new Info(0,0,"",null);
}
}↑
시행착오
처음에는 숫자로 매핑을 했었는데,
그렇게 하면 10의 자리 수가 넘어가 매핑을 하나마나한 문제가 발생했다.
거기에 시간을 많이 쓴 것 같고, 두 번째는 "(None)"을 정확히 출력하지 못했다.
문제를 꼼꼼히 체크하자.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me