[Java] 코드트리_흰검칠하기

Updated: 2024.12.04

📌 개인적인 공간으로 공부를 기록하고 복습하기 위해 사용하는 블로그입니다.
정확하지 않은 정보가 있을 수 있으니 참고바랍니다 :😸
[틀린 내용은 댓글로 남겨주시면 복받으실거에요]

흰검 칠하기

내가 작성한 코드의 문제점과 수정

import java.util. *;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 타일의 색상을 저장할 map
        Map<Integer, int[]> map = new HashMap<>();
        int loc = 0;

        for (int i = 0; i < n; i++) {
            int d = sc.nextInt();
            String direction = sc.next();

            if (direction.equals("L")) { // 왼쪽 흰색
                for (int j = loc; j > loc - d; j--) {
                    int[] counts = map.getOrDefault(j, new int[3]); // counts[0]: 흰색 칠한 횟수, counts[1]: 검은색 칠한 횟수, counts[2]: 마지막 색상
                    if (counts[2] != 2) {
                        counts[0]++;
                        if (counts[0] >= 2 && counts[1] >= 2) {
                            counts[2] = 2; // 회색으로 변경
                        } else {
                            counts[2] = 0; // 마지막 색상을 흰색으로 설정
                        }
                    }
                    map.put(j, counts);
                }
                loc -= d;
            } else { // 오른쪽 검은색
                for (int j = loc; j < loc + d; j++) {
                    int[] counts = map.getOrDefault(j, new int[3]);
                    if (counts[2] != 2) {
                        counts[1]++;
                        if (counts[0] >= 2 && counts[1] >= 2) {
                            counts[2] = 2;
                        } else {
                            counts[2] = 1;
                        }
                    }
                    map.put(j, counts);
                }
                loc += d;
            }
        }

        int whiteCount = 0, blackCount = 0, grayCount = 0;
        for (int key : map.keySet()) {
            int[] counts = map.get(key);
            if (counts[2] == 2) {
                grayCount++;
            } else if (counts[2] == 1) {
                blackCount++;
            } else if (counts[2] == 0) {
                whiteCount++;
            }
        }

        System.out.println(whiteCount + " " + blackCount + " " + grayCount);
    }
}

문제점 분석

카운트 로직 오류
- 코드에서 counts[0]과 counts[1]은 각 타일이 흰색과 검은색으로 칠해진 횟수인데 counts[2] == 2(타일이 회색인 경우)일 때 counts[0]과 counts[1]의 업데이트가 이루어지지 않는다.
회색 타일로 변경 조건 미충족
- 타일이 회색이 되기 위한 조건은 흰색과 검은색으로 각각 두 번 이상 칠해지는 것이지만
- 코드에서는 타일이 회색이 되면 이후로는 counts[0]과 counts[1]이 증가하지 않으므로, 이후에 추가로 칠해지는 횟수가 누락되어버림
- 이로 인해 일부 타일이 실제로는 회색이 되어야 하지만 코드에서는 회색으로 처리되지 않는 문제가 발생하게 된다.

수정 방안

타일의 칠해진 횟수(counts[0], counts[1])는 타일이 회색이 되었더라도 계속해서 업데이트되어야 합니다. 다만, 타일의 색상(counts[2])은 회색이 된 이후로는 변경되지 않아야 한다.

수정된 코드

if (direction.equals("L")) { // 왼쪽으로 이동하며 흰색으로 칠함
    for (int j = loc; j > loc - d; j--) {
        int[] counts = map.getOrDefault(j, new int[3]);
        counts[0]++; // 흰색으로 칠한 횟수 증가
        if (counts[0] >= 2 && counts[1] >= 2) {
            counts[2] = 2; // 회색으로 변경
        } else if (counts[2] != 2) { // 회색이 아닌 경우에만 색상 업데이트
            counts[2] = 0; // 마지막 색상을 흰색으로 설정
        }
        map.put(j, counts);
    }
    loc -= d;
} else { // 오른쪽으로 이동하며 검은색으로 칠함
    for (int j = loc; j < loc + d; j++) {
        int[] counts = map.getOrDefault(j, new int[3]);
        counts[1]++; // 검은색으로 칠한 횟수 증가
        if (counts[0] >= 2 && counts[1] >= 2) {
            counts[2] = 2; // 회색으로 변경
        } else if (counts[2] != 2) { // 회색이 아닌 경우에만 색상 업데이트
            counts[2] = 1; // 마지막 색상을 검은색으로 설정
        }
        map.put(j, counts);
    }
    loc += d;
}

counts[0]과 counts[1]은 타일이 회색이 되었더라도 항상 업데이트된다.
타일의 색상(counts[2])은 회색(2)이 아닌 경우에만 업데이트합니다.
회색으로 변경되는 조건(counts[0] >= 2 && counts[1] >= 2)은 계속해서 체크하여 회색 타일을 정확히 판단

수정된 코드 전체

import java.util. *;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Map<Integer, int[]> map = new HashMap<>();
        int loc = 0;

        for (int i = 0; i < n; i++) {
            int d = sc.nextInt();
            String direction = sc.next();

            if (direction.equals("L")) { // 왼쪽 흰색
                for (int j = loc; j > loc - d; j--) {
                    int[] counts = map.getOrDefault(j, new int[3]);
                    counts[0]++; // 흰색 칠한 횟수 증가
                    if (counts[0] >= 2 && counts[1] >= 2) {
                        counts[2] = 2; // 회색으로 변경
                    } else if (counts[2] != 2) { // 회색이 아닌 경우에만 색상 업데이트
                        counts[2] = 0; // 흰색으로 설정
                    }
                    map.put(j, counts);
                }
                loc -= d;
            } else { // 오른쪽 검은색
                for (int j = loc; j < loc + d; j++) {
                    int[] counts = map.getOrDefault(j, new int[3]);
                    counts[1]++; // 검은색 칠한 횟수 증가
                    if (counts[0] >= 2 && counts[1] >= 2) {
                        counts[2] = 2; // 회색으로 변경
                    } else if (counts[2] != 2) {
                        counts[2] = 1; // 검은색으로 설정
                    }
                    map.put(j, counts);
                }
                loc += d;
            }
        }

        int whiteCount = 0, blackCount = 0, grayCount = 0;
        for (int[] counts : map.values()) {
            if (counts[2] == 2) {
                grayCount++;
            } else if (counts[2] == 1) {
                blackCount++;
            } else if (counts[2] == 0) {
                whiteCount++;
            }
        }

        System.out.println(whiteCount + " " + blackCount + " " + grayCount);
    }
}

풀이 코드

import java.util.Scanner;

public class Main {
    public static final int MAX_K = 100000;

    public static int n;
    public static int[] a = new int[2 * MAX_K + 1]; // 타일의 현재 색상을 저장하는 배열
    public static int[] cntB = new int[2 * MAX_K + 1]; // 각 타일이 검은색으로 칠해진 횟수
    public static int[] cntW = new int[2 * MAX_K + 1]; // 각 타일이 흰색으로 칠해진 횟수
    public static int b, w, g; // 검은색, 흰색, 회색 타일의 개수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        int cur = MAX_K; // 초기 위치 설정 (중앙 위치)
        for(int i = 1; i <= n; i++) {
            int x = sc.nextInt();
            char c = sc.next().charAt(0);
            if(c == 'L') { // 왼쪽으로 이동하며 흰색으로 칠함
                while(x-- > 0) {
                    a[cur] = 1; // 현재 타일을 흰색으로 설정
                    cntW[cur]++; // 흰색으로 칠한 횟수 증가
                    if(x > 0) cur--; // 다음 타일로 이동
                }
            }
            else { // 오른쪽으로 이동하며 검은색으로 칠함
                while(x-- > 0) {
                    a[cur] = 2; // 현재 타일을 검은색으로 설정
                    cntB[cur]++; // 검은색으로 칠한 횟수 증가
                    if(x > 0) cur++; // 다음 타일로 이동
                }
            }
        }

        // 모든 타일에 대해 색상 결정
        for(int i = 0; i <= 2 * MAX_K; i++) {
            if(cntB[i] >= 2 && cntW[i] >= 2) g++; // 흰색과 검은색으로 각각 두 번 이상 칠해진 경우 회색
            else if(a[i] == 1) w++; // 흰색 타일
            else if(a[i] == 2) b++; // 검은색 타일
        }

        System.out.print(w + " " + b + " " + g);
    }
}

코드 설명

타일 배열 (a[])과 카운트 배열 (cntB[], cntW[])
- a[]: 각 타일의 현재 색상을 저장합니다. 0은 칠해지지 않음, 1은 흰색, 2는 검은색
- cntB[], cntW[]: 각 타일이 검은색 또는 흰색으로 칠해진 횟수를 저장
현재 위치 (cur)
- 중앙 위치인 MAX_K에서 시작하여 명령에 따라 이동
이동
- 각 명령에 대해 x만큼 반복하면서 타일의 색상과 칠해진 횟수를 업데이트한다.
- 왼쪽(L)으로 이동할 때는 cur를 감소시키고, 오른쪽(R)으로 이동할 때는 cur를 증가시킴
최종 색상 결정
- 모든 타일을 순회하며 cntB[i]와 cntW[i]를 확인하여 회색 타일을 결정
- 회색이 아닌 타일은 마지막으로 칠해진 색상인 a[i]를 참고하여 흰색 또는 검은색 타일의 개수를 증가시킨다.

풀이에서는 cur을 배열의 인덱스가 음수가 되지 않도록 100000으로 설정한 것 같은데 처음에 cur을 이해하느라고 애먹었다, 나는 HashMap 사용했는데, 정답 풀이가 깔끔하고 간단해보이긴 한데 배열의 크기가 있어서 메모리상의 이점은 내가 더 좋을 듯 하다.

Hezzi