[BaekJoon] 2034 반음 JAVA

🔗 백준 2034 문제 https://www.acmicpc.net/problem/2034

문제

서양 음악의 음계는 도레미파솔라시의 칠음계이다. 각각의 음은 차례로 영어 알파벳 CDEFGAB에 대응된다(도다레라미마파바솔사라가시나도다를 생각하면 됨). 이 문제에서는 이러한 일곱 음만을 다루기로 한다.

 

하지만 모든 음이 이 일곱으로만 구성된 것은 아니다. 피아노에는 위의 그림과 같이 검은 건반이 있으며, 검은 건반은 인접한 흰 건반과 반음의 차이가 난다. 즉, C와 D 사이에 있는 검은 건반은 C, D와 반음 차이가 난다. 검은 건반이 사이에 없는 경우에는, 붙어 있는 두 흰 건반이 반음 차이가 난다. 예를 들어 B, C 는 반음 차이가 나며, E, F는 반음 차이가 난다.

 

이러한 반음 차이를 이용하여, 두 음 사이의 거리를 정의할 수 있다. F로부터 -1만큼 떨어진 (왼쪽으로 반음) 음은 E이고, F로부터 4만큼 떨어진(오른쪽으로 반음 네 번) 음은 A이다. 이 문제에서는 칠음(흰 건반)만을 따지므로, F로부터 1만큼 떨어진 음은 없다.

 

이러한 거리들을 모으면 하나의 악보가 된다. 예를 들어 2 2 1 2 2 2 1과 같은 악보는, 차례로 CDEFGABC를 누르는 악보이다. 즉, 이 악보는 첫 음이 C이고 끝 음이 C인 악보가 된다. 하지만 이 악보는 첫 음이 D일 수는 없는데, 그 경우 DE 다음에 검은 건반이 눌리게 되기 때문이다. 악보가 주어졌을 때, 가능한 첫 음과 끝 음의 쌍을 모두 구해내는 프로그램을 작성하시오. 피아노는 좌우로 무한히 길다고 가정한다.

 

---

입력

첫째 줄에 악보의 길이를 나타내는 정수 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 n개의 줄에는 절댓값이 20을 넘기지 않는 정수로 악보가 주어진다.

---

출력

첫째 줄로부터 차례로 첫 음과 끝 음을 출력한다. 여러 경우가 가능할 때에는 알파벳이 작은 경우부터 출력한다,

---

풀이

일단.. 매우 어려운 문제로 느껴졌다.

그래도 천천히 하나씩 풀어보기 시작했고 처음 통과한 코드는 그야말로 난장판..이었다.

먼저, 시간 제한이 있으니 BufferedReader로 입력을 받기로 했다.

그리고 scale이라는 리스트에 영어 음계를 넣어줬는데, 그냥 넣어주지 않고 반음 올렸을 때 검은 건반이라면 null값을 넣어주었다.

결과를 출력할 때, 첫 음과 끝 음을 출력해야하고, 여러 경우가 가능할 때 알파벳이 작은 순으로 정렬해야하기에 HashMap을 선언해주었다.

그 후, for문을 돌리면서 각 음계마다 입력들어온 악보만큼 이동을 시켜주었다.

 

내가 푼 코드 1 (리팩토링 전)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        List<String> scale = Arrays.asList("C", null, "D", null, "E", "F", null, "G", null, "A", null, "B");
        Map<String, String> result = new HashMap<>();
        int n = Integer.parseInt(br.readLine());
        int[] play = new int[n];

        for (int k = 0; k < n; k++) play[k] = Integer.parseInt(br.readLine());
        for (int i = 0; i < scale.size(); i++) {

            // 악보를 따라 이동할 음
            int sum = i; 
            
            // 시작 음이 검은 건반일 경우 밑 로직을 실행하지 않는다
            if (scale.get(i) == null) continue; 

            for (int j = 0; j < n; j++) {
            
                // sum이 음계 list의 크기를 벗어나는지 확인한다
                sum = sumSize(sum + play[j], scale.size()); 

                if (sum >= scale.size()) sum = sumSize(sum, scale.size());
                else if (sum < 0) sum = sumSize(sum, scale.size());

                // 음이 도착한 지점이 검은 건반일 경우 해당 for문을 벗어난다
                if (scale.get(sum) == null) break; 
            }
            
            // 끝 음이 검은 건반일 경우 밑 로직을 실행하지 않는다
            if (scale.get(sum) == null) continue; 
            
            // 첫 음, 끝 음이 모두 흰 건반이라면 hashmap에 넣는다
            result.put(scale.get(i), scale.get(sum)); 
        }

        // hashmap의 첫 음을 꺼내어 작은 순으로 정렬시켜준다
        Object[] mapKey = result.keySet().toArray(); 
        Arrays.sort(mapKey); 

        // 정렬시킨 첫 음을 사용하여 출력한다
        for (Object key : mapKey) { 
            System.out.println(key + " " + result.get(String.valueOf(key)));
        }
    }

    // sum의 크기가 scale의 범위를 벗어날 때
    public static int sumSize(int sum, int size) {

        if (sum >= size) sum -= size;
        else if (sum < 0) sum += size;

        return sum;
    }
}

 

---

일단 리팩토링 전 코드는 딱 봐도 난잡하다.

 

리팩토링을 하기 위해 수정할 부분을 추려보았다.

 

1. scale은 굳이 list로 할 필요가 없다. 다른 타입을 사용해보자.

2. scale을 C부터 시작하여 정렬이 필요했으나 A부터 시작한다면 굳이 정렬을 할 필요가 없어진다.

3. null로 검은 건반을 확인해야할까? 위치로 확인할 수는 없을까?

4. 어차피 scale의 길이는 12로 고정되어있는데 굳이 length?

5. 반복되는 연산이 존재하는데 재귀를 사용해보는건 어떨까

6. BufferedWriter로 시간을 더 단축시켜보자

 

내가 푼 코드 2

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 리스트를 String 타입으로 변경하였다
        String scale = "A_BC_D_EF_G_";
        
        // 불필요한 연산을 줄이기 위해 흰 건반의 위치를 리스트로 선언해두었다
        List<Integer> pos = Arrays.asList(0, 2, 3, 5, 7, 8, 10); 

        int n = Integer.parseInt(br.readLine());
        int[] play = new int[n];

        for (int k = 0; k < n; k++) play[k] = Integer.parseInt(br.readLine());

        for (int i = 0; i < 12; i++) {

            int sum = i;
            
            // 선언한 위치 리스트를 통해 첫 음이 흰 건반 위치가 아니라면 다음 반복문으로 넘어간다
            if (!pos.contains(i)) continue; 

            for (int j = 0; j < n; j++) {
                sum = sumSize(sumLen(sum + play[j])); // 재귀
                
                // 선언한 위치 리스트를 통해 마지막 음이 흰 건반 위치가 아니라면 반복문을 빠져나온다
                if (!pos.contains(sum)) break; 
            }

            // 선언한 위치 리스트를 통해 마지막 음이 흰 건반 위치가 아니라면 다음 반복문으로 넘어간다
            if (!pos.contains(sum)) continue; 

            bw.write(scale.charAt(i) + " "
                    + scale.charAt(sum) + "\n");
        }
        bw.close();
    }

    private static int sumSize(int sum) {
        // 재귀 탈출조건
        // 이동한 음이 scale의 범위를 넘어가지 않으면 재귀를 탈출한다
        if (sum < 12 && sum >= 0) {
            return sum;
        }

        if (sum < 0) sum = sumSize(sum + 12); 
        if (sum >= 12) sum = sumSize(sum - 12);
        return sum;
    }

    // 재귀 돌입 전, 처음에 필요한 연산을 해 준다
    private static int sumLen(int sum) { 
        if (sum >= 12) sum -= 12;
        if (sum < 0) sum += 12;
        return sum;
    }
}