[백준] 1244 - 스위치 켜고 끄기

승래·2025년 11월 16일

1244 - 스위치 켜고 끄기

문제

입력

첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 있다. 셋째 줄에는 학생수가 주어진다. 학생수는 100 이하인 양의 정수이다. 넷째 줄부터 마지막 줄까지 한 줄에 한 학생의 성별, 학생이 받은 수가 주어진다. 남학생은 1로, 여학생은 2로 표시하고, 학생이 받은 수는 스위치 개수 이하인 양의 정수이다. 학생의 성별과 받은 수 사이에 빈칸이 하나씩 있다.

출력

스위치의 상태를 1번 스위치에서 시작하여 마지막 스위치까지 한 줄에 20개씩 출력한다. 예를 들어 21번 스위치가 있다면 이 스위치의 상태는 둘째 줄 맨 앞에 출력한다. 켜진 스위치는 1, 꺼진 스위치는 0으로 표시하고, 스위치 상태 사이에 빈칸을 하나씩 둔다.

요구사항

문제의 요구사항은 크게 3가지로 나눌 수 있다.

초기 상태: N개의 스위치 상태가 0(꺼짐) 또는 1(켜짐)으로 주어진다.
학생별 로직:

남학생 (1): 자신이 받은 수의 '배수'가 되는 스위치들을 모두 토글(0->1, 1->0)한다.
여학생 (2): 자신이 받은 수를 중심으로, '좌우 대칭'이면서 '가장 긴 구간'을 찾아 그 구간의 스위치를 모두 토글한다.

최종 출력: 모든 학생의 조작이 끝난 스위치 상태를 '한 줄에 20개씩' 출력한다.
접근 방식

접근방식

2.1. 자료구조 및 기본 세팅

스위치 배열: 문제에서 스위치 번호가 1번부터 시작(1-based)하므로, 인덱스 관리를 편하게 하기 위해 int[N+1] 크기로 배열을 선언했다.
토글 함수: 스위치 상태를 바꾸는 toggle() 함수를 따로 분리했다.

// 0이면 1로, 1이면 0으로 바꾸는 함수
static void toggle(int pos, int[] arr) {
    if (arr[pos] == 1) {
        arr[pos] = 0;
    } else {
        arr[pos] = 1;
    }
}

2.2. 남학생 로직 (🐞 첫 번째 함정)
요구사항은 "받은 수의 배수"였다. 처음에는 for (int i = p.pos; i <= N; i = i 2)라고 잘못 작성했다. 예제 입력(N=8, 남학생=3)에서는 3, 6만 해당되어 i2와 i+p.pos의 결과가 우연히 같았고, 이게 '틀렸습니다'의 첫 번째 원인이었다.

// 잘못된 코드 (거듭제곱)
// for (int i = p.pos; i <= N; i = i * 2) { ... }

// 수정된 코드 (배수)
if (p.gender == 1) {
    for (int i = p.pos; i <= N; i += p.pos) {
        toggle(i, arr);
    }
}

2.3. 여학생 로직 (꼼꼼한 경계값 체크)
이 문제의 핵심 로직.

일단 자신이 받은 번호(p.pos)의 스위치는 무조건 토글한다.
while(true) 루프를 돌면서 좌우(lPos, rPos)로 한 칸씩 범위를 넓혀간다.
(경계값 체크) while문 안에서 가장 먼저 lPos < 1 또는 rPos > N인지 (배열 범위를 벗어나는지) 체크해서 break 해야 한다. (PCCP에서 겪었던 ArrayIndexOutOfBounds를 피하기!)
(대칭 체크) 경계값에 문제가 없다면, arr[lPos] == arr[rPos]인지 (대칭인지) 확인하고, 대칭이 깨졌다면 break 한다.
두 조건을 모두 통과하면 lPos와 rPos 스위치를 토글한다.

} else { // 여학생
    toggle(p.pos, arr); // 1. 중심은 일단 토글
    int lPos = p.pos;
    int rPos = p.pos;

    while (true) {
        lPos--;
        rPos++;

        // 3. 경계값 체크 (가장 중요)
        if (lPos < 1 || rPos > N) {
            break;
        }

        // 4. 대칭 체크
        if (arr[lPos] != arr[rPos]) {
            break;
        }

        // 5. 통과 시 토글
        toggle(lPos, arr);
        toggle(rPos, arr);
    }
}

코드

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

class Point {
    int gender;
    int pos;

    public Point(int gender, int pos) {
        this.gender = gender;
        this.pos = pos;
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        int[] arr = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        int students = Integer.parseInt(st.nextToken());

        Point[] student = new Point[students];
        for (int i = 0; i < students; i++) {
            st = new StringTokenizer(br.readLine());
            int gender = Integer.parseInt(st.nextToken());
            int pos = Integer.parseInt(st.nextToken());
            student[i] = new Point(gender, pos);
        }

        for (Point p : student) {
            if (p.gender == 1) {
                for (int i = p.pos; i <= N; i = i + p.pos) {
                    toggle(i, arr);
                }
            } else {
                toggle(p.pos, arr);
                int lPos = p.pos;
                int rPos = p.pos;
                while (true) {
                    lPos--;
                    rPos++;
                    if (lPos < 1 || rPos > N) {
                        break;
                    }

                    if (arr[lPos] != arr[rPos]) {
                        break;
                    }

                    toggle(lPos, arr);
                    toggle(rPos, arr);
                }
            }

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

    static void toggle(int pos, int[] arr){
        if(arr[pos] == 1) {
            arr[pos] = 0;
        }
        else{
            arr[pos] = 1;
        }
    }
}