들어서기

안녕하세요
코딩테스트편으로 돌아온 Minter입니다.

골드5인줄 알았는데, 놀랍게도 실버1이었슨;;;

암튼 잡소리 그만하고, Java로 코딩테스트 준비를 시작했습니다.
원래 python, Swift로만 했었는데, 자바로 하려니까 정말 미치겠슨...
단기간에 준비하는 것보다 꾸준하게 매일매일 준비하려고 합니다.

아.무.튼
시작합니다

문제

Trail2/Lesson3. 흰검 칠하기

---

분석

(입력 형태 분석은 생략)

우리는 일직선으로 무한히 나열된 타일의 색칠 놀이를 하는 것입니다.
변수 x는 칸의 수를, L,R은 수직선 상에서의 방향을 의미합니다.

L일 경우

x칸 만큼 왼쪽으로 이동하며 흰색으로 색칠

R일 경우

x칸 만큼 오른쪽으로 이동하며 검은색으로 색칠

제약조건을 분석해보겠습니다.
1. 색은 덧칠해지만 마지막으로 칠한 색으로 바뀐다 => 색 상태 저장이 필요하겠군
2. 순서 상관 없이 흰,검으로 각각 두 번 이상 칠해지면 회식으로 바뀌고 더이상 바뀌지 않는다 => 각 색상이 칠해진 횟수를 기억해야함

---

혼동 포인트

01. 첫 접근법

저의 첫 접근법은 다음과 같습니다.

1. 객체 배열 생성
2. 해당 객체의 현재 색상이 지금 칠해야하는 색상과 다른경우

• 색상을 변경시킴
• 색상 변경 횟수를 기억함

하지만 위의 접근법의 치명적인 오류는...
검흰검흰 번갈아 들어오면 횟수로 회색이 되어야 할 것을 판별할 수 있음
하지만 흰흰검검으로 들어오면 색상 변경회수는 1회이므로, 회색으로 판별할 수 없다.

02. 칸과 구간을 구분하자?

현재 지점에서 2만큼 이동해야하는 경우를 생각해보자.
현재 지점이 3이라고 하면 수직선 상에선 3,4,5 점이 포함될 것이다.

하지만 배열상에서는 3,4 칸만이 2만큼 이동하는 경우에 해당된다.

case 2가 바로 그 예시다
3,4,5를 모두 포함하여 사실상 3칸을 이동해버린것이다..

고급지게 얘기해보자면..
.
.
.

현재 위치와 이동 거리를 해석할 때, 점 기준으로 볼지 칸(타일) 기준으로 볼지 구분해야 한다.

특히 2만큼 이동이라는 표현은

• 점의 개수로 보면 시작점 포함 3개의 점이 나타남
• 실제로 지나가는 타일 또는 구간의 개수로 보면 2칸으로 해석

나는 칸으로 봐야하는 문제를 많이 접했다.
그래서 점으로 봐야하는 문제는 딱히 생각은 안나는데... BFS,DFS,그래프 등.. 이런 탐색, 방문 쪽에서 많이 나올 것 같다.

결론은 모델링 할 때, [start, end) 이것을 잊지 말자.
왼쪽으로 (숫자가 작아지는)경우에도 해당된다. start는 작은 수, end에는 큰 수를 넣어주자.

Solution 1. 객체를 활용하기

최종 접근법은 아래와 같다.

1. 현재 색상, 흰색 카운트, 검은색 카운트 필드를 생성한다.
2. 해당 객체 타입의 배열을 만든다.
3. 흰색 카운트 >= 2 && 검은색 카운트 >=2 이면 회색으로 판정한다

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        State[] arr = new State[200001];
        int idx = 100000;

        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            char d = sc.next().charAt(0);

            // 방향
            if (d == 'R') {
                for (int j = idx; j < idx + x; j++) {
                    if (arr[j] == null) {
                        arr[j] = new State(1);
                    }

                    if (arr[j].whiteCount >= 2 && arr[j].blackCount >=2) continue;

                    arr[j].whiteCount++;
                    arr[j].tmp = 1;
                }
                idx = idx + x - 1;

            } else {
                for (int j = idx; j > idx - x; j--) {
                    if (arr[j] == null) {
                        arr[j] = new State(2);
                    }

                    if (arr[j].whiteCount >= 2 && arr[j].blackCount >=2) continue;

                    arr[j].blackCount++;
                    arr[j].tmp = 2;
                }

                idx = idx - x + 1;
            }
        }

        countColor(arr);
        
    }

    static void countColor(State[] arr) {
        int white = 0, black = 0, gray = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == null) continue;

            if (arr[i].whiteCount >=2 && arr[i].blackCount >= 2) {
                gray++;
            } else if (arr[i].tmp == 1) {
                black++;
            } else {
                white
            }
        }

        System.out.println(white + " " + black + " " + gray);
    }

    // 객체
    static class State {
        int whiteCount, blackCount, tmp;
        
        public State(int tmp) {
            this.tmp = tmp;
            this.whiteCount = 0;
            this.blackCount = 0;
        }
    }
}

Solution 2. 3개의 배열을 활용하기

다른 분들의 풀이를 보니 3개의 배열을 활용하는 접근법도 있었다.
다음에 직접 구현해보겠다.

3개의 배열을 같은 사이즈로 관리하며 공통된 인덱스를 공유해서 접근하면 된다.

• 현재 색상을 저장할 배열
• white 색상을 저장할 배열
• black 색상을 저장할 배열

마치며

첨언하자면 예전엔 문제에서 제공하는 제한 조건을 보지 않았는데, 요즘은 보려고 노력함!!!

(1000 * 100 * 2) + 1 사이즈의 배열로 선언했음~