문제 간단 해석
기억한 멜로디와 악보를 비교하여, 네오가 들은 곡이 무엇인지를 찾는 문제. 문자열을 잘 변환해야 한다.
Java
풀이 코드
import java.util.*;
class Solution {
public String makeMelody(String st) {
List<String> list = new ArrayList<>();
boolean flag = false;
for (int i = st.length() - 1; i >= 0; i--) {
char c = st.charAt(i);
if (c == '#') {
flag = true;
continue;
}
list.add(Character.toString(flag ? Character.toLowerCase(c) : c));
flag = false;
}
Collections.reverse(list);
return String.join("", list);
}
public int getMinute(String t1, String t2) {
int[] startTime = Arrays.stream(t1.split(":")).mapToInt(Integer::parseInt).toArray();
int[] endTime = Arrays.stream(t2.split(":")).mapToInt(Integer::parseInt).toArray();
int time = endTime[0] - startTime[0];
int minute = endTime[1] - startTime[1];
return time * 60 + minute;
}
public String solution(String m, String[] musicinfos) {
m = makeMelody(m);
int maxMinute = 0;
String answer = "(None)";
for (String musicInfo: musicinfos) {
String[] info = musicInfo.split(",");
int minute = getMinute(info[0], info[1]);
if (maxMinute >= minute)
continue;
String melody = makeMelody(info[3]);
melody = melody.repeat(minute / melody.length()) + melody.substring(0, minute % melody.length());
if (melody.contains(m)) {
maxMinute = minute;
answer = info[2];
}
}
return answer;
}
}
해석
public String makeMelody(String st) {
List<String> list = new ArrayList<>();
boolean flag = false;
for (int i = st.length() - 1; i >= 0; i--) {
char c = st.charAt(i);
if (c == '#') {
flag = true;
continue;
}
list.add(Character.toString(flag ? Character.toLowerCase(c) : c));
flag = false;
}
Collections.reverse(list);
return String.join("", list);
}문자열 변환. # 글자는 특정 글자 뒤에 나오므로, 뒤부터 검사하여 #이 나왔다면 그 이전 글자를 소문자로 변환한 후 넣어주도록 했다.
뒤부터 넣었으니 거꾸로 배치한 다음 join을 통해 내부 문자열들을 하나로 합쳐 반환.
public int getMinute(String t1, String t2) {
int[] startTime = Arrays.stream(t1.split(":")).mapToInt(Integer::parseInt).toArray();
int[] endTime = Arrays.stream(t2.split(":")).mapToInt(Integer::parseInt).toArray();
int time = endTime[0] - startTime[0];
int minute = endTime[1] - startTime[1];
return time * 60 + minute;
}걸린 시간 확인. :를 기준으로 시와 분을 나눈 후 t1에서 t2까지 걸린 시간 계산.
m = makeMelody(m);
int maxMinute = 0;
String answer = "(None)";주어진 m을 정리. 초기값을 잡는다.
for (String musicInfo: musicinfos) {
String[] info = musicInfo.split(",");
int minute = getMinute(info[0], info[1]);
if (maxMinute >= minute)
continue;
String melody = makeMelody(info[3]);
melody = melody.repeat(minute / melody.length()) + melody.substring(0, minute % melody.length());
if (melody.contains(m)) {
maxMinute = minute;
answer = info[2];
}
}
return answer;musicinfos에서 하나씩 가져와 ,를 기준으로 쪼갠다.
걸린 시간을 구한다.
만약 걸린 시간이 현재 구한 시간보다 같거나 작다면 다음 곡 정보를 가져온다.
악보를 구하고, 걸린 시간만큼 악보를 반복해서 길게 만든다.
만약 해당 악보 안에 멜로디가 있었다면, 시간과 답을 갱신한다.
Python
보이어무어 알고리즘을 직접 구현해봤다. 때문에 Java 코드만큼의 길이가 나왔다.
풀이 코드
def music_code(music):
code = []
for m in music:
if m != '#':
code.append((ord(m) - ord('A')) * 2)
else:
code[-1] += 1
return code
def solution(m, musicinfos):
answer = "(None)"
answer_time = 0
m = music_code(m)
m_ch_idx = {}
for i in range(len(m)):
ch = m[i]
try:
m_ch_idx[ch].append(i)
except:
m_ch_idx[ch] = [i]
for musicinfo in musicinfos:
start, end, title, code = musicinfo.split(',')
start = list(map(int, start.split(':')))
end = list(map(int, end.split(':')))
time = (end[0] - start[0]) * 60 + end[1] - start[1]
if answer_time >= time:
continue
code = music_code(code)
code = code * (time // len(code)) + code[:time % len(code)]
now = 0
while now + len(m) <= len(code):
unmatch = len(m) - 1
jump = len(m)
for i in range(len(m) - 1, -1, -1):
if code[now + i] != m[i]:
unmatch = i
break
jump -= 1
else:
answer_time = time
answer = title
break
idx_list = []
try:
idx_list = m_ch_idx[code[now + unmatch]]
except KeyError:
now += jump
continue
for j in range(len(idx_list) - 1, -1, -1):
if unmatch > idx_list[j]:
now += unmatch - idx_list[j]
break
else:
now += jump
return answer
해석
def music_code(music):
code = []
for m in music:
if m != '#':
code.append((ord(m) - ord('A')) * 2)
else:
code[-1] += 1
return code문자열을 정리. 만약 #이 나오면 이전 문자에 +1을 해 준다.
따라서 값들이 중복되지 않게, 문자를 치환할 때는 A부터 0, 2, 4, 6, ... 으로 넣는다.
for i in range(len(m)):
ch = m[i]
try:
m_ch_idx[ch].append(i)
except:
m_ch_idx[ch] = [i]보이어무어 알고리즘의 편의를 위해, m 글자들의 인덱스를 기록한다.
for musicinfo in musicinfos:
start, end, title, code = musicinfo.split(',')
start = list(map(int, start.split(':')))
end = list(map(int, end.split(':')))
time = (end[0] - start[0]) * 60 + end[1] - start[1]
if answer_time >= time:
continue
code = music_code(code)
code = code * (time // len(code)) + code[:time % len(code)]Java 코드처럼, 하나씩 가져오며 시간과 전체 악보를 구성한다.
now = 0
while now + len(m) <= len(code):
unmatch = len(m) - 1
jump = len(m)
for i in range(len(m) - 1, -1, -1):
if code[now + i] != m[i]:
unmatch = i
break
jump -= 1
else:
answer_time = time
answer = title
break
idx_list = []
try:
idx_list = m_ch_idx[code[now + unmatch]]
except KeyError:
now += jump
continue
for j in range(len(idx_list) - 1, -1, -1):
if unmatch > idx_list[j]:
now += unmatch - idx_list[j]
break
else:
now += jump글자의 끝에서부터 매칭을 한다. 일치하지 않으면 해당 글자와 일치하는 글자가 현재보다 얼마나 앞쪽에 있는지 찾는다. 만약 없다면 글자열의 크기 - 일치한 글자수만큼 건너뛴다.
자세한 방식은 이곳 참조.
시험삼아 구성해본 거고.. 그냥 in으로 우리가 찾는 글자가 내부에 있는지 확인하자.
나누며 타오르는 프로그래머, 타프입니다.