[240219] 알고리즘 리부트 11일차 - 백준 2840 자바

[Part1-Chapter04-Clip08]

- 백준 2840 행운의 바퀴

 

 

자료구조를 사용하지 않고 배열로 처리하고자 했다. 문제에서 요구하는 제한이 좀 있어서 애를 먹었다. 시계방향이지만 결국 반시계 방향으로 값을 꺼내야 한다는 점이나(반시계방향으로 넣었으면 시계방향으로 꺼내면 된다) 같은 알파벳이 같은 자리에 들어가는 건 가능하지만 같은 알파벳이 다른 자리에 들어가게 된다면 존재할 수 없는 바퀴이다.

 

이번 문제를 풀면서 복잡한 조건은 어떻게 잘 이해하고 구현했지만 아직 인덱스를 활용하는데 어려움을 겪었다. 내가 작성한 코드와 아래 리팩토링 코드(다른 분의 인덱스를 참고했다)를 비교해보면 결국 같다. 모드 연산한 값이 경계를 벗어나면 다시 배열의 범위로 들어오게 하는 것. 나의 경우는 순서대로 값을 넣었기 때문에 모드 연산한 값과 기존의 인덱스를 더한 값이 경계를 벗어나게 되면(n 이상) '-n'을 해준 것이고 리팩토링 코드는 역순으로 값을 넣었기 때문에 모든 연산한 값과 기존의 인덱스를 더한 값이 경계를 벗어나게 되면(음수) '+n'을 해준 것이다. 

 

배열을 출력하는 것도 그렇다. 인덱스가 존재하는 범위를 넘어가더라도 모드 연산을 해주면 동일한 범위 내의 인덱스를 가진다는 것을 명확히 이해하고 있지 못했다. 그래서 저런 길고 긴 코드가 나온 것이다. 하지만! 종이에만 써봐도 아는 것을... 모드 연산하면 마지막 pointer에서 시작해서 배열의 크기 만큼 출력하더라도 배열의 범위 내에서 출력할 수 있는 것이다. 그래도 고생했다. 

 

아 그리고 저 11% 에서 계속 틀린 것은 결국 나의 사소한 실수였다. 

writeAlpha[alpha-'A'] = true;

 

이 처리를 빼먹어서.. 머리로는 알고 있지만 조건문을 복잡하게 구현하다보니 빼먹었다. 이걸 넣으니 한방에 해결

 

초기 코드

package BaekJoon.simulation;


import java.util.Scanner;

public class BJ2840 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        char[] wheel = new char[n];

        for (int i = 0; i < n; i++) wheel[i] = '?';


        boolean[] writeAlpha = new boolean[26];

        StringBuilder sb = new StringBuilder();

        int spin = sc.nextInt();
        char alpha = sc.next().charAt(0);

        wheel[0] = alpha;

        writeAlpha[alpha - 'A'] = true;

        int pointer = 0;

        boolean exist = true;

        while (k-- > 1) {

            spin = sc.nextInt();
            alpha = sc.next().charAt(0);

            if (pointer + spin % n > n - 1) {
                pointer = spin % n - (n - pointer);
            } else {
                pointer += spin % n;
            }
            // 입력 절차
            if (wheel[pointer] == '?') { // 빈칸이고
                if (!writeAlpha[alpha - 'A']) { // 아직 이 알파벳 입력한 적 없으면
                    wheel[pointer] = alpha;
                    writeAlpha[alpha-'A'] = true;
                } else { // 근데 입력한 적 있으면 -> 다른 위치에 같은 알파벳 입력하는 거니까 존재할 수 없는 바퀴
                    exist = false;
                }
            } else if (wheel[pointer] == alpha) {
                continue;
            } else { // 빈칸도 아니고 지금 입력하려는 알파벳도 아닌 애가 있어 그럼 존재할 수 없는 바퀴
                exist = false;
            }
        }

        if (exist) {

            for (int i = n-1; i >=0; i--) {
                sb.append(wheel[(pointer + i+1) % n]);
            }

//            // 역순으로 출력하기
//            for (int i = pointer; i >= 0; i--) {
//                sb.append(wheel[i]);
//                //System.out.println("i: "+i);
//            }
//            if (pointer != n - 1) {
//                for (int i = n - 1; i > pointer; i--) {
//                    sb.append(wheel[i]);
//                    //System.out.println("i: "+i);
//                }
//            }
            System.out.println(sb.toString());
        } else {
            System.out.println("!");
        }
    }
}

 

리팩토링 코드

package BaekJoon.simulation;


import java.util.Scanner;

public class BJ2840_1 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        char[] wheel = new char[n];

        for (int i = 0; i < n; i++) wheel[i] = '?';
        // Arrays.fill(wheel,'?');

        boolean[] writeAlpha = new boolean[26];

        StringBuilder sb = new StringBuilder();

        int spin = sc.nextInt();
        char alpha = sc.next().charAt(0);

        wheel[0] = alpha;

        writeAlpha[alpha - 'A'] = true;

        int pointer = 0;

        boolean exist = true;

        while (k-- > 1) {

            spin = sc.nextInt();
            alpha = sc.next().charAt(0);

            pointer = (pointer + n - (spin % n)) % n;

            // 입력 절차
            if (wheel[pointer] == '?') { // 빈칸이고
                if (!writeAlpha[alpha - 'A']) { // 아직 이 알파벳 입력한 적 없으면
                    wheel[pointer] = alpha;
                    writeAlpha[alpha-'A'] = true;
                } else { // 근데 입력한 적 있으면 -> 다른 위치에 같은 알파벳 입력하는 거니까 존재할 수 없는 바퀴
                    exist = false;
                }
            } else if (wheel[pointer] == alpha) {
                continue;
            } else { // 빈칸도 아니고 지금 입력하려는 알파벳도 아닌 애가 있어 그럼 존재할 수 없는 바퀴
                exist = false;
            }
        }

        if (exist) {

            for (int i = 0; i < n; i++) {
                sb.append(wheel[(i + pointer) % n]);
            }


            System.out.println(sb.toString());
        } else {
            System.out.println("!");
        }
    }
}