프로그래머스 - [3차] 방금그곡

프로그래머스 - [3차] 방금그곡

코드

import java.time.Duration;
import java.time.LocalTime;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Solution {
	String[] musicinfos;
	Map<String, String> musicStartTime = new HashMap<>();

	public String solution(String m, String[] musicinfos) {
		this.musicinfos = musicinfos;
		String answer = null;
		// 1. Map 생성 => Key : 노래, Value : 재생된 악보
		/*
			1-1. 재생된 악보가 m의 길이보다 작으면 Map에 추가하지 않음(기억하는 멜로디가 아님)
			1-2. m이 포함되어 있지 않다면 Map에 추가하지 않음
		 */
		Map<String, List<String>> playedMelody = playMusicResult(m);
		// 1-3. Map size가 0이라면 (None) 반환
		if (playedMelody.isEmpty()) {
			return "(None)";
		}
		// 2. Map size가 1이라면 해당 노래 반환
		if (playedMelody.size() == 1) {
			return playedMelody.keySet().stream().collect(Collectors.toList()).get(0);
		}
		// 2-1. Map size가 2 이상이라면 아래 조건에 따라 반환
		/*
			 1순위 : 재생 시간 가장 긴것(Value 길이 가장 긴 것)
			 2순위 : 1순위 만족하는 노래가 여러개인 경우 먼저 시작한 노래
		 */
		answer = choiceBestMelody(playedMelody);

		return answer;
	}

	/*
		정답 후보들 중 최선의 멜로디 반환하기
		1순위 : 재생 시간 가장 긴것(Value 길이 가장 긴 것)
		2순위 : 1순위 만족하는 노래가 여러개인 경우 먼저 시작한 노래
	 */
	private String choiceBestMelody(Map<String, List<String>> playedMelody) {
		List<String> result = new ArrayList<>();
		List<String> keySet = playedMelody.keySet()
			.stream()
			// 길이 순 내림차순 정렬
			.sorted((o1, o2) -> playedMelody.get(o2).size() - playedMelody.get(o1).size())
			.collect(Collectors.toList());
		int longestMin = playedMelody.get(keySet.get(0)).size();
		for (String key : keySet) {
			List<String> s = playedMelody.get(key);
			if (s.size() != longestMin) {
				break;
			}
			// 가장 긴 길이와 같은 문자열 다 모아두기
			result.add(key);
		}

		// 1순위 : 가장 긴 길이(오래 연주)한 것이 1곡이라면 해당 곡 제목 반환
		if (result.size() == 1) {
			return result.get(0);
		}

		// 2순위 : 가장 빨리 시작한 곡 반환
		return result.stream()
			.sorted(new Comparator<String>() {
				@Override
				public int compare(String o1, String o2) {
					o1 = musicStartTime.get(o1);
					o2 = musicStartTime.get(o2);
					String[] splitO1 = o1.split(":");
					String[] splitO2 = o2.split(":");
					// Integer의 기본 comparable은 오름차순으로 양수이면 자리를 바꿈
					// 7, 5 => 5, 7로 만들기 위함
					if (Integer.parseInt(splitO1[0]) - Integer.parseInt(splitO2[0]) == 0) {
						return Integer.parseInt(splitO1[1]) - Integer.parseInt(splitO2[1]);
					}
					return Integer.parseInt(splitO1[0]) - Integer.parseInt(splitO2[0]);
				}
			})
			.collect(Collectors.toList())
			.get(0);
	}

	/*
		"방금그곡" 서비스에서 찾고자 하는 멜로디가 포함된 음악 목록을 반환하는 메서드
		반환 타입 = Key : 음악 제목 / Value : 연주된 멜로디
	 */
	public Map<String, List<String>> playMusicResult(String targetMelody) {
		Map<String, List<String>> result = new HashMap<>();
		for (String musicinfo : musicinfos) {
			// 1. 정보 추출
			String[] musicinfoArr = musicinfo.split(",");
			String startTime = musicinfoArr[0];
			String endTime = musicinfoArr[1];
			String songName = musicinfoArr[2];
			String musicalNote = musicinfoArr[3];

			// 2. 시간 추출(분)
			Duration between = Duration.between(LocalTime.parse(startTime), LocalTime.parse(endTime));
			long minDiff = between.toMinutes();
			// 3. 연주된 악보 생성
			List<String> play = new ArrayList<>();
			List<String> musicalNoteArr = noteToStringList(musicalNote);
			int idx = 0;
			int z = 1;
			while (minDiff > 0) {
				if (idx == musicalNoteArr.size()) {
					idx = 0;
				} else {
					play.add(musicalNoteArr.get(idx++));
					minDiff--;
				}
			}
			// 4. Map에 추가될 수 있는지 검증하고 조건 만족 시 추가
			// 4-1. 연주한 것이 더 길어야 기억하는 음과 비교가 가능
			List<String> transTargetMelody = noteToStringList(targetMelody);

			if (play.size() >= transTargetMelody.size()) {
				// 4-2. 연주된 것에 기억하는 멜로디가 포함되어있어야 추가
				// 2번째 인자의 리스트가 첫번째 리스트에서 연속으로 존재하는지 확인하는 메서드
				if (Collections.indexOfSubList(play, transTargetMelody) != -1) {
					result.put(songName, play);
					// 여러 정답 중 재생 시간이 같은 경우 빨리 시작한 노래 찾기 위한
					// 시작 시간 Map 저장
					musicStartTime.put(songName, startTime);
				}
			}
		}
		return result;
	}

	/*
		악보를 String 배열로 변환해주는 메서드
		#이 붙은 멜로디도 합해준다.
	 */
	private List<String> noteToStringList(String musicalNote) {
		char[] chars = musicalNote.toCharArray();
		List<String> result = new ArrayList<>();
		for (int i = 0; i < chars.length; i++) {
			// C# 등 # 같이 붙여주기
			if (chars[i] == 'C' || chars[i] == 'D' || chars[i] == 'F' || chars[i] == 'G' || chars[i] == 'A') {
				if (i + 1 < chars.length && chars[i + 1] == '#') {
					result.add(String.valueOf(chars[i]) + chars[i + 1]);
					i++;
					continue;
				}
			}
			result.add(String.valueOf(chars[i]));
		}
		return result;
	}
}

• #이 붙은 악보 처리에 시간이 훌쩍 가버렸는데, 다른사람 풀이보니 악보에 포함되지 않은 다른 문자열로 바꿔버리더라..하하 레벨1할때 그런 방법으로 했던 것 같은데 깜빡했다.
• 그래도 바꾸지 않고 명확하게 #이 붙은 방법으로 해결했다.
• 각 동작들을 메서드화 하니 String에서 List<String> 등 반환타입을 변경하더라도 수정할 부분이 적어 좋았다.
• String으로 네오가 기억하는 멜로디가 있는지 파악할 때 #때문에 리스트로 바꿔서 명확하게 했지만, 리스트가 연속으로 있어야 함을 어떻게 보장하고 확인하지.. 고민하다가 뤼튼에게 Help..!
• 나처럼 푼 사람이 있을까.. 3시간 걸린듯 하하

배열, 리스트 연속적으로 포함되었는지 확인하기

• 배열 : Apache Commons Lang 라이브러리의 ArrayUtils 클래스는 indexOf 메서드이용
  • 첫 번째 인자로 받은 배열에서 두 번째 인자로 받은 부분 배열이 처음으로 나타나는 위치의 인덱스를 반환
  • 없으면 -1 반환

import org.apache.commons.lang3.ArrayUtils;

public class Main {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6};
        int[] subArray = {3, 4, 5};

        int index = ArrayUtils.indexOf(array, subArray);
        System.out.println(index); // 출력: 2
    }
}

• 리스트 : Collections.indexOfSubList 활용
  • 첫 번째 인자로 받은 리스트에서 두 번째 인자로 받은 리스트가 처음으로 나타나는 위치의 인덱스를 반환
  • 없으면 -1 반환

List<Integer> source = Arrays.asList(1, 2, 3, 4, 5, 6);
List<Integer> target = Arrays.asList(3, 4, 5);

int index = Collections.indexOfSubList(source, target);
System.out.println(index); // 출력: 2