방금그곡

Posted on Edited on In , ,

문제정의

네오가 기억하는 계이름과 음악의 계이름 재생시간이 주어질 때, 네오가 들은 곡을 알아내는 문제이다. 음악의 길이보다 재생기간이 길면 반복하여 재생하는 것이고, 짧다면 중간에 끊어진 것이라고 봐야한다. 만약 네오가 기억하는 계이름을 가지고 있는 곡이 여러 개라면 재생 시간이 긴 것을 우선으로 하고, 재생 시간도 같은 경우 먼저 들어온 곡을 반환한다.

문제 링크

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
package level2;

public class PreviousSong {

    //프로그래머스 문제풀이 Level2 방금그곡

    public static void main(String[] args) {

        String[] musicinfos = {
            "12:00,12:05,HI,ABC#ABC",
            "13:00,13:05,WORLD,ABCDEF"
        };
        String m = "ABC";
        String answer = "(None)";
        int last_time = 0;
        for(String info : musicinfos)
        {
            
            String[] info_arr = info.split(",");
            String[] start_t = info_arr[0].split(":");
            String[] end_t = info_arr[1].split(":");
            int start_m = Integer.parseInt(start_t[0])*60 + Integer.parseInt(start_t[1]);
            int end_m = Integer.parseInt(end_t[0])*60 + Integer.parseInt(end_t[1]);
            int duration = end_m - start_m;
            
            
            String[] split_by_pound_arr = info_arr[3].split("#");
            int code_cnt = 1;
            for(String pound_str : split_by_pound_arr)
            {
                String[] codes = pound_str.split("");
                for(String code : codes)
                    code_cnt++;
            }
            code_cnt--;
            
            int repeat = duration/code_cnt;
            int song_end = duration%code_cnt;
            String song = "";
            for(int i = 0; i < repeat; i++)
            {
                song += info_arr[3];
            }
            
            char[] song_arr = info_arr[3].toCharArray();
            int song_idx = 0;
            for(int i = 0; i < song_arr.length; i++)
            {
                if(song_idx == song_end)
                    break;
                StringBuilder buff = new StringBuilder();
                buff.append(song_arr[i]);
                if((i < song_arr.length-1) && (song_arr[i+1] == '#'))
                    buff.append(song_arr[++i]);
                song += buff.toString();
                
                
                song_idx++;   
            }
            
            int idx = song.indexOf(m);
            
            if((last_time < duration) && (idx != -1))
            {
                while(idx != -1)
                {
                    if(song.length() > idx+m.length())
                    {
                        if(song.charAt(idx+m.length()) == '#')
                        {
                            idx = song.indexOf(m, idx+m.length());
                            continue;
                        }
                    } 
                    idx = song.indexOf(m, idx+m.length());
                    answer = info_arr[2];
                    last_time = duration;
                }
                
            }
            
        }

        System.out.println(answer);
    }
}
곡을 찾아내기 위해 크게 3가지 과정을 거칠 것이다. 1. 재생 시간을 계산한다. 2. 곡을 재생 시간만큼 만든다. 3. 네오가 기억하는 음과 비교하여 그 곡이 맞는지 확인한다.

우선 1번과정부터 살펴보자.

1
2
3
4
5
6
String[] info_arr = info.split(",");
String[] start_t = info_arr[0].split(":");
String[] end_t = info_arr[1].split(":");
int start_m = Integer.parseInt(start_t[0])*60 + Integer.parseInt(start_t[1]);
int end_m = Integer.parseInt(end_t[0])*60 + Integer.parseInt(end_t[1]);
int duration = end_m - start_m;

재생 시간을 계산하는 방법은 쉽다 모두 분 단위로 변환한 뒤, 종료시각에서 재생시각을 빼면 된다.

2번과정으로 넘어가보자

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
String[] split_by_pound_arr = info_arr[3].split("#");
int code_cnt = 1;
for(String pound_str : split_by_pound_arr)
{
    String[] codes = pound_str.split("");
    for(String code : codes)
        code_cnt++;
}
code_cnt--;

int repeat = duration/code_cnt;
int song_end = duration%code_cnt;
String song = "";
for(int i = 0; i < repeat; i++)
{
    song += info_arr[3];
}

char[] song_arr = info_arr[3].toCharArray();
int song_idx = 0;
for(int i = 0; i < song_arr.length; i++)
{
    if(song_idx == song_end)
        break;
    StringBuilder buff = new StringBuilder();
    buff.append(song_arr[i]);
    if((i < song_arr.length-1) && (song_arr[i+1] == '#'))
        buff.append(song_arr[++i]);
    song += buff.toString();
    
    
    song_idx++;   
}

곡을 재생시간만큼 만들기 위해서 #에 대한 처리가 필요하다. 일단 #을 제외하면 전체 계이름 개수를 알 수 있다. #을 기준으로 문자열을 쪼갠 뒤, 전체 계이름 개수를 구한다. 그리고 repeat와 song_end를 구한다. repeat는 전체 노래가 몇 번 반복하는지 알려주는 변수이다. 나누기 연산을 통해 구할 수 있다. song_end는 중간에서 노래가 멈출 경우 몇번째 음에서 멈추는지 알려주는 변수이다. 이는 나머지 연산을 통해 구할 수 있다.

repeat수 만큼 전체 문자열을 song에 더해주고 두번째 for문은 song_idx가 song_end에 도달할 때까지 #을 고려하여 song에 계이름을 더해준다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int idx = song.indexOf(m);
            
if((last_time < duration) && (idx != -1))
{
    while(idx != -1)
    {
        if(song.length() > idx+m.length())
        {
            if(song.charAt(idx+m.length()) == '#')
            {
                idx = song.indexOf(m, idx+m.length());
                continue;
            }
        } 
        idx = song.indexOf(m, idx+m.length());
        answer = info_arr[2];
        last_time = duration;
    }
    
}

이제 만든 노래를 비교해보면 된다. 여태까지 제일 길었떤 재생 시간을 저장한 last_time이 duration보다 작고, 네오가 기억한 음이 포함되어 있다면 if문 안으로 들어간다. 이 때, 처리해주지 못하는 케이스가 있는데 맨 마지막에 #이 붙는 경우이다. 이 경우 indexOf로 찾은 값에 m의 길이를 더해 #이 있으면 불일치로 간주하면 된다. 네오의 음과 일치하는 구절이 여러 곳일 수 있기 때문에 idx는 루프를 돌 때 마다 업데이트한다.

테스트



categories: [Problem Solving, Programmers, Level2]

#을 처리하는 것에서 많이 헤맸는데, 다른 사람들의 풀이를 보니 C#같은 문자열을 c로 바꾸어 문제를 간단하게 풀었다. 나도 그런 아이디어가 나도록 훈련해야겠다.