[BOJ] 2816번 - 디지털 티비

👀 문제 분석

백준 - 디지털 티비

입력된 채널의 순서를 'KBS1'이 첫 번째, 'KBS2'가 두 번째로 오게 바꾼다.

아래 4가지 방법으로 순서를 조정할 수 있다.

1. 화살표를 한 칸 아래로 내린다. (채널 i에서 i+1로)
2. 화살표를 위로 한 칸 올린다. (채널 i에서 i-1로)
3. 현재 선택한 채널을 한 칸 아래로 내린다. (채널 i와 i+1의 위치를 바꾼다. 화살표는 i+1을 가리키고 있는다)
4. 현재 선택한 채널을 위로 한 칸 올린다. (채널 i와 i-1의 위치를 바꾼다. 화살표는 i-1을 가리키고 있다)

가장 처음에 화살표는 제일 첫 번째 채널을 가리킨다. 채널 리스트가 범위를 벗어날 경우 명령은 무시된다. 또한, 입력 값에 'KBS1'과 'KBS2'의 위치가 첫 번째, 두 번째로 올 경우는 없다.

⚒️ 설계

1. N과 N만큼의 채널을 입력받는다.
2. 입력받은 크기로 채널 배열을 초기화한다. (화살표도 0 인덱스로 초기화)
3. 입력받은 채널 내에서 'KBS1'과 'KBS2'의 위치를 찾는다.
4. 명령을 통해 원하는 리스트의 순서를 만든다.
   • 이때, 순서를 만들기 위해 사용된 명령을 기록한다.
5. 기록된 명령어들을 반환한다. (결과)

📝 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int n = Integer.parseInt(br.readLine());
        String[] channels = new String[n];
        for (int i = 0; i < n; i++) {
            channels[i] = br.readLine();
        }

        int pointer = 0;
        StringBuilder commands = new StringBuilder();

        int kbs1Index = findIndex(channels, "KBS1");

        movePointer(commands, pointer, kbs1Index);
        pointer = kbs1Index;

        moveToTop(commands, channels, kbs1Index);
        pointer = 0;

        int kbs2Index = findIndex(channels, "KBS2");

        movePointer(commands, pointer, kbs2Index);
        pointer = kbs2Index;

        moveToSecond(commands, channels, kbs2Index);
        pointer = 1;

        System.out.println(commands);
        br.close();
    }

    private static int findIndex(String[] channels, String target) {
        for (int i = 0; i < channels.length; i++) {
            if (channels[i].equals(target)) {
                return i;
            }
        }
        return -1;
    }

    private static void movePointer(StringBuilder commands, int currentIdx, int targetIdx) {
        int moveCount = Math.abs(currentIdx - targetIdx);
        commands.append("1".repeat(moveCount));
    }

    private static void moveToTop(StringBuilder commands, String[] channels, int index) {
        moveToPosition(commands, channels, index, 0);
    }

    private static void moveToSecond(StringBuilder commands, String[] channels, int index) {
        moveToPosition(commands, channels, index, 1);
    }

    private static void moveToPosition(StringBuilder commands, String[] channels, int currentIdx, int targetIdx) {
        while (currentIdx > targetIdx) {
            commands.append('4');
            swap(channels, currentIdx, currentIdx - 1);
            currentIdx--;
        }
    }

    private static void swap(String[] channels, int i, int j) {
        String temp = channels[i];
        channels[i] = channels[j];
        channels[j] = temp;
    }

}

⌛️ 시간복잡도

• 인덱스를 찾기 위해 배열을 순회하는데 O(n)
• 모든 이동 O(n)
• 배열 순서 바꾸기 O(1)

최종 시간 복잡도 : O(n)

👩🏻‍💻 느낀점

처음에 문제를 보고 같은 입력에 다른 출력이 나오는 것을 보았다.
생각할게 많을 거 같아 겁이 났고 계속 그려가면서 코드를 구현했다.
하지만 여러 답이 있는 문제임을 알고 1과 4로만 순서를 바꾸는 것으로 접근했다.

완성을 하고 예제 문제에 올바르게 작동해서 제출하니 '틀렸습니다' 나오는 거 보고 한 100번은 왜지?왜지??? 하고 생각했다.
다른 예제를 실행하니 출력이 올바르지 않다는 것을 알게 되었다.
잘 안풀려서 gpt한테 슬쩍 질문했는데 그때 추가된 조건문으로 인해 틀리는 것이었다... 차분하게 다시 보면 금방 풀릴 문제를 돌고돌아 해결한 기분이다🥺

이제는 gpt를 사용하지 않을 것이다.

✔️ 소요시간 : 2시간