[코드트리] 신기한 타일 뒤집기

https://www.codetree.ai/missions/5/problems/strange-flipping-tiles/description

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

public class Main {
    public static final int OFFSET = 100000, WHITE = 1, BLACK = 2;
    public static int[] tiles = new int[OFFSET * 2 + 1];
    public static int white = 0, black = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int inputCount = Integer.parseInt(br.readLine());

        int cur = OFFSET;
        for (int i = 0; i < inputCount; i++) {
            String[] input = br.readLine().split(" ");
            int flipCount = Integer.parseInt(input[0]);
            String direction = input[1];

            if (direction.equals("L")) {
                while (flipCount > 0) {
                    tiles[cur] = WHITE;
                    flipCount--;
                    if (flipCount > 0) cur--;
                }
            } else {
                while (flipCount > 0) {
                    tiles[cur] = BLACK;
                    flipCount--;
                    if (flipCount > 0) cur++;
                }
            }
        }

        white = (int) Arrays.stream(tiles).filter(ele -> ele == WHITE).count();
        black = (int) Arrays.stream(tiles).filter(ele -> ele == BLACK).count();
        System.out.println(white + " " + black);
    }
}

풀이

1. OFFSET 정하기

전체 타일을 배열로 관리하려고 했다. 하지만 오른쪽 뿐만 아니라 왼쪽으로도 이동하는데 배열의 인덱스로 음수를 사용할 수 없으므로, 뒤집은 타일의 인덱스가 모두 0이상의 정수가 되도록 일정 OFFSET을 더해서 전체 타일 배열 길이를 설정해야 한다.

입력 횟수는 최대 1,000번이고 한 번에 뒤지는 타일 갯수가 100개이므로 최대 100,000 개의 타일을 왼쪽으로만 뒤집을 수도 있는 상황이 존재하기 때문에 OFFSET을 100,000으로 정한다.

2. 뒤집은 타일 색깔 체크하기

왼쪽으로 뒤집을 때는 타일 색깔을 WHITE로 오른쪽으로 뒤집을때는 타일 색깔을 BLACK으로 하여 배열 요소를 변경한다.

시간 복잡도

입력 횟수(N)만큼 반복하며 매 반복마다 최대(X)번 뒤집을 수 있으므로 시간복잡도는 O(NX)가 된다.