[프로그래머스] 방금그곡 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다.

네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다. 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다. 그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다. 다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라.

• 방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.
• 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.
• 각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.
• 음악이 00:00를 넘겨서까지 재생되는 일은 없다.
• 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.
• 조건이 일치하는 음악이 없을 때에는 “(None)”을 반환한다.

2. 입력

입력으로 네오가 기억한 멜로디를 담은 문자열 m과 방송된 곡의 정보를 담고 있는 배열 musicinfos가 주어진다.

• m은 음 1개 이상 1439개 이하로 구성되어 있다.
• musicinfos는 100개 이하의 곡 정보를 담고 있는 배열로, 각각의 곡 정보는 음악이 시작한 시각, 끝난 시각, 음악 제목, 악보 정보가 ','로 구분된 문자열이다.
  • 음악의 시작 시각과 끝난 시각은 24시간 HH:MM 형식이다.
  • 음악 제목은 ',' 이외의 출력 가능한 문자로 표현된 길이 1 이상 64 이하의 문자열이다.
  • 악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.

3. 예제

m	musicinfo	answer
"ABCDEFG"	["12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"]	"HELLO"
"CC#BCC#BCC#BCC#B"	["03:00,03:30,FOO,CC#B", "04:00,04:08,BAR,CC#BCC#BCC#B"]	"FOO"
"ABC"	["12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"]	"WORLD"

4. 풀이

해당 문제는 가장 문제가 되는 부분이 바로 음에서 C, C#, A, A#과 같이 #이 있는 문자와 없는 문자로 구분되는 부분 일 것입니다.

 

그래서 #이 있는 문자를 입력으로 받는 음과 겹치지 않도록 1개의 문자로 치환하는 작업을 먼저 진행하여 #이 있는 문자와 없는 문자가 서로 다른 문자라는 것을 구분하기 쉽도록 하여야 합니다.

 

public String changeStr(String str) {
	str = str.replace("A#", "H");
	str = str.replace("G#", "I");
	str = str.replace("F#", "J");
	str = str.replace("D#", "K");
	str = str.replace("C#", "L");

	return str;
}

위 코드의 changeStr 메소드를 통해 Parameter로 전달받은 문자열의 A#은 H로 G#은 I로 F#는 J로 D# K로 C#는 L로 치환하여 반환하는 함수를 생성하였습니다.

 

이제 입력으로 주어진 음을 changeStr 메소드를 통해 #음의 문자를 치환하여 줍니다.

 

이후 입력받은 음악들을 순환하면서 해당 음악의 음을 위와 동일하게 changeStr 메소드를 통해 #음의 문자를 치환하여 줍니다.

 

입력으로 주어지는 시간은 HH:MM이므로 ":" 문자를 기준으로 split하여 시간과 분을 구합니다.

 

이후 각 음은 1분이라고 하였으므로 현재 필요한 것은 시간이 아닌 분 입니다.

 

int startTime = Integer.parseInt(info[0].split(":")[0]) * 60 + Integer.parseInt(info[0].split(":")[1]);
int endTime = Integer.parseInt(info[1].split(":")[0]) * 60 + Integer.parseInt(info[1].split(":")[1]);

위 코드처럼 시작 시간과 종료 시간의 분의 차이를 알기 위해 시간 * 60 + 분을 통해 단위를 분으로 변경하고 종료 시간에서 시작 시간을 빼주어 두 시간의 분차이를 구합니다.

 

StringBuilder stringBuilder = new StringBuilder();
for (int j = 0; j < endTime - startTime; j++)
	stringBuilder.append(musicM.charAt(j % musicM.length()));

위 코드 처럼 이제 음악이 틀어진 시간만큼 음을 만들기 위해 위에서 구한 분만큼 반복문을 수행합니다.

 

만약 음악의 재생 시간이 음의 길이보다 큰 경우 음악을 반복 재생한 것이므로 음악의 음 길이만큼 나눈 나머지를 이용하여 Index를 구하여 해당 음을 추가하여 음악 재생시간 동안 만들어지는 음을 문자열로 만듭니다.

 

if (stringBuilder.toString().contains(m))
	priorityQueue.offer(new Music(endTime - startTime, info[2], i));

위 코드처럼 입력으로 주어진 음이 해당 음악의 음에 포함이 된다면 Music객체로 만들어 PriorityQueue에 추가합니다.

 

Music Class는 Comparable 인터페이스를 구현하여 Music객체의 크기(우선순위) 비교를 구현합니다.

 

문제에서는 재생시간이 길수록 우선순위가 높으며 만약 재생시간이 같다면 먼저 재생된 음악이 우선이라고 하였으므로

해당 부분을 compareTo 메소드에 구현합니다.

 

@Override
public int compareTo(Music o) {
	if (this.time == o.time) {
		return Integer.compare(this.index, o.index);
	}

	return Long.compare(o.time, this.time);
}

위 코드는 compareTo 메소드를 구현한 것입니다.

 

모든 음악을 확인하였다면 Queue가 비었다면 만족하는 음악이 없는 것이므로 (None)을 반환합니다.

 

만약 Queue에 Music객체가 있다면 최 상단에 있는 Music객체가 우선순위가 가장 높은 것이므로 해당 Music객체의 name 속성의 값을 반환합니다.

 

5. 코드

전체 코드는 Git에 있습니다.

public String solution(String m, String[] musicinfos) {
	m = changeStr(m);

	PriorityQueue<Music> priorityQueue = new PriorityQueue<>();

	for (int i = 0; i < musicinfos.length; i++) {
		String[] info = musicinfos[i].split(",");

		String musicM = changeStr(info[3]);

		int startTime = Integer.parseInt(info[0].split(":")[0]) * 60 + Integer.parseInt(info[0].split(":")[1]);
		int endTime = Integer.parseInt(info[1].split(":")[0]) * 60 + Integer.parseInt(info[1].split(":")[1]);

		StringBuilder stringBuilder = new StringBuilder();
		for (int j = 0; j < endTime - startTime; j++)
			stringBuilder.append(musicM.charAt(j % musicM.length()));

			if (stringBuilder.toString().contains(m))
				priorityQueue.offer(new Music(endTime - startTime, info[2], i));
		}

		if (priorityQueue.isEmpty())
			return "(None)";
		else
			return priorityQueue.poll().name;
	}

public String changeStr(String str) {
	str = str.replace("A#", "H");
	str = str.replace("G#", "I");
	str = str.replace("F#", "J");
	str = str.replace("D#", "K");
	str = str.replace("C#", "L");

	return str;
}

public class Music implements Comparable<Music> {
	private long time;
	private String name;
	private int index;

	public Music(long time, String name, int index) {
		this.time = time;
		this.name = name;
		this.index = index;
	}

	@Override
	public int compareTo(Music o) {
		if (this.time == o.time) {
			return Integer.compare(this.index, o.index);
		}

		return Long.compare(o.time, this.time);
	}
}