백준 - 1244번(스위치 켜고 끄기)

문제 출처: https://www.acmicpc.net/problem/1244

문제

• 1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치는 켜져 있거나 꺼져있는 상태이다. <그림 1>에 스위치 8개의 상태가 표시되어 있다. ‘1’은 스위치가 켜져 있음을, ‘0’은 꺼져 있음을 나타낸다. 그리고 학생 몇 명을 뽑아서, 학생들에게 1 이상이고 스위치 개수 이하인 자연수를 하나씩 나누어주었다. 학생들은 자신의 성별과 받은 수에 따라 아래와 같은 방식으로 스위치를 조작하게 된다.

• 남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다. 즉, 스위치가 켜져 있으면 끄고, 꺼져 있으면 켠다. <그림 1>과 같은 상태에서 남학생이 3을 받았다면, 이 학생은 <그림 2>와 같이 3번, 6번 스위치의 상태를 바꾼다.

• 여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다. 이때 구간에 속한 스위치 개수는 항상 홀수가 된다.

• 예를 들어 <그림 2>에서 여학생이 3을 받았다면, 3번 스위치를 중심으로 2번, 4번 스위치의 상태가 같고 1번, 5번 스위치의 상태가 같으므로, <그림 3>과 같이 1번부터 5번까지 스위치의 상태를 모두 바꾼다. 만약 <그림 2>에서 여학생이 4를 받았다면, 3번, 5번 스위치의 상태가 서로 다르므로 4번 스위치의 상태만 바꾼다.

• 입력으로 스위치들의 처음 상태가 주어지고, 각 학생의 성별과 받은 수가 주어진다. 학생들은 입력되는 순서대로 자기의 성별과 받은 수에 따라 스위치의 상태를 바꾸었을 때, 스위치들의 마지막 상태를 출력하는 프로그램을 작성하시오.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int switchCount = Integer.parseInt(reader.readLine());
        int[] switches = new int[switchCount + 1];
        StringTokenizer token = new StringTokenizer(reader.readLine());
        for (int i = 1; i <= switchCount; i++) {
            switches[i] = Integer.parseInt(token.nextToken());
        }
        int studentCount = Integer.parseInt(reader.readLine());
        int[][] studentList = new int[studentCount][2];
        for (int i = 0; i < studentCount; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            studentList[i][0] = Integer.parseInt(tokenizer.nextToken());
            studentList[i][1] = Integer.parseInt(tokenizer.nextToken());
        }
        // 배열 인덱스 1부터 센다. 마지막은 switchCount 이다.
        for (int i = 0; i < studentCount; i++) {
            int card = studentList[i][1];
            if (studentList[i][0] == 1) { // 남자일 경우
                while (card <= switchCount) {
                    switches[card] = (switches[card] + 1) % 2;
                    card += studentList[i][1];
                }
            } else { // 여자일 경우
                if (card > 1 && card < switchCount) {
                    int left = card - 1;
                    int right = card + 1;

                    while (left > 0 && right <= switchCount) {
                        if (switches[left] == switches[right]) {
                            if (left == 1 || right == switchCount) {
                                break;
                            } else {
                                left--;
                                right++;
                            }
                        } else { // 서로 다른 경우
                            left++;
                            right--;
                            break;
                        }
                    }

                    for (int j = left; j <= right; j++) {
                        switches[j] = (switches[j] + 1) % 2;
                    }

                } else {
                    // card만 수정
                    switches[card] = (switches[card] + 1) % 2;
                }
            }
        }

        for (int i = 1; i <= switchCount; i++) {
            System.out.print(switches[i] + " ");
            if (i % 20 == 0) {
                System.out.println();
            }
        }
    }

}

• 인덱스 처리의 간편함을 위해 입력되는 스위치의 수 + 1 크기의 배열을 생성하였다.
• 남학생의 경우 큰 어려움 없이 처리할 수 있었다.
• 여학생의 경우, 인덱스 처리를 하는데 있어 조금 까다로움이 있었다.
• 우선 card가 양 끝단에 위치하는 경우, 다른 걸 볼 필요도 없이 해당 카드만 교환해서 끝낸다.
• 양 끝단이 아닐 경우, left와 right 좌표를 한칸씩 이동시키며 값이 같은지 비교한다.
• left와 right가 양 끝단이 되는지를 판별하며 이동시키고, 양 끝단에 위치할 경우 증감없이 종료한다.
• 값이 같을 경우는 계속 증감하며 진행하지만, 다를 경우 이전의 left와 right 값까지 처리하기 위해 left는 오른쪽으로 한 칸, right는 왼쪽으로 한 칸 이동하여 해당 범위의 스위치를 toggle 한다.