[Python] 1244. 스위치 켜고 끄기

문제

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

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

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

스위치 번호스위치 상태

①	②	③	④	⑤	⑥	⑦	⑧
0	1	0	1	0	0	0	1

<그림 1>

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

스위치 번호스위치 상태

①	②	③	④	⑤	⑥	⑦	⑧
0	1	1	1	0	1	0	1

<그림 2>

스위치 번호스위치 상태

①	②	③	④	⑤	⑥	⑦	⑧
1	0	0	0	1	1	0	1

<그림 3>

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

만약, 랭킹 리스트가 꽉 차있을 때, 새 점수가 이전 점수보다 더 좋을 때만 점수가 바뀐다. 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보다 작거나 같은 자연수 또는 0이다. 둘째 줄에는 현재 랭킹 리스트에 있는 점수가 비오름차순으로 주어진다. 둘째 줄은 N이 0보다 큰 경우에만 주어진다.

---

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

 

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

풀이

list를 사용할지 dictionary를 사용할지 고민하다가 스위치의 번호는 인덱스를 사용해서 충분히 표현할 수 있을 것 같았고, 또 마지막에 print(*list)를 사용하여 한 번에 쉽게 출력하기 위해 list를 사용하기로 했다. 남학생의 규칙은 for문 range에서 값을 건너뛸 수 있는 특징을 이용해 구현하였고, 여학생의 규칙은 리스트 슬라이싱을 적극 활용해 구현하였다. 이 문제의 함정은 스위치 값을 한 줄에 20개씩 출력한다는 것이었기 때문에 마지막에 for문을 활용해 출력 규칙을 맞춰주었다.

첫 번째 코드

import sys

input = sys.stdin.readline
n = int(input())
switch = list(map(int, input().split()))
s = int(input())
for _ in range(s):
    gen, num = map(int, input().split())
    if gen == 1:  # 남자
        for i in range(num - 1, n, num):
            switch[i] = 1 - switch[i]
    else:  # 여자
        ran = 0
        while num - 1 - ran - 1 >= 0 and num - 1 + ran + 1 < n:
            if switch[num - 1 - ran - 1] == switch[num - 1 + ran + 1]:
                ran += 1
            else:
                break
        switch[num - 1 - ran : num - 1 + ran + 1] = [
            1 - x for x in switch[num - 1 - ran : num - 1 + ran + 1]
        ]
for i in range(0, n, 20):
    print(*(switch[i : i + 20]))

꽤 깔끔하게 잘 구현하였다!크게 건드릴 부분은 없고, 반복적으로 사용되는 값들만 변수로 선언해주고 1과 0을 변환하는 방법을 수정하였다.

 

1. XOR(^) 연산 사용

: 기존의 x=1-x로 1과 0을 변환하던 방법 대신 XOR 연산 기호를 활용하여 변환하도록 수정하였다. x^=1

 

2. 반복되는 값들 변수로 선언

: idx=num-1, start=idx-ran, end=idx+ran+1로 선언하여 반복 계산되는 부분을 줄였다.

최종 코드

import sys

input = sys.stdin.readline
n = int(input())
switch = list(map(int, input().split()))
s = int(input())
for _ in range(s):
    gen, num = map(int, input().split())
    if gen == 1:  # 남자
        for i in range(num - 1, n, num):
            switch[i] ^= 1
    else:  # 여자
        ran = 0
        idx = num - 1
        while idx - ran - 1 >= 0 and idx + ran + 1 < n:
            if switch[idx - ran - 1] == switch[idx + ran + 1]:
                ran += 1
            else:
                break
        start, end = idx - ran, idx + ran + 1
        switch[start:end] = [x ^ 1 for x in switch[start:end]]
for i in range(0, n, 20):
    print(*(switch[i : i + 20]))

코드의 가독성이 조금 더 좋아졌다. 실행시간도 36ms에서 32ms로 줄어들었다.이제 점점 문제를 푸는 감이 잡혀가는 것 같다. 깔끔하고 효율적인 알고리즘을 구상하기 위해 더 노력해야겠다.

 

배운 것

• x^1:x와 1의 XOR 연산을 한다.