[boj] 12927번: 배수 스위치

출처 : https://www.acmicpc.net/problem/12927

12927번: 배수 스위치

 

 

1. 문제 설명 

강호는 전구를 N개를 가지고 있다. 1번부터 N번까지 번호가 매겨져있고, 전구는 켜져있거나 꺼져있다. 전구의 개수만큼 스위치 N개를 가지며, 1번부터 N번까지 번호가 매겨져 있다. i번 스위치를 끄게 되면 i의 배수 번호를 가지는 전구의 상태를 모두 반전시킨다.

 

 

 

2. 접근 방식 

해시맵을 사용하였다. (특별한 알고리즘은 없다.)

 

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import sys
from collections import defaultdict
input = sys.stdin.readline
lights = list(input().rstrip())
dic = defaultdict(str)
for i in range(1, len(lights)+1):
    dic[i] += lights[i-1]

flag = 'Y'
idx = 1  
count = 0
while idx <= len(dic):
    if flag != dic[idx] and len(set(dic.values())) == 1: # flag가 'N'이고 dic.values()의 중복을 제거한 길이가 1인 경우 탈출!
        break

    for k, v in dic.items():
        if v == 'Y':  # => k번째가 켜져있다는 것은 -> k의 배수만큼 모든 전구를 꺼야한다.
            idx = k   # k를 idx에 넣는다. # idx 변수에 따로 저장 
            break

    for k, v in dic.items():
        if k % idx == 0:  # 배수만큼 모든 전구를 꺼준다. 
            if v == flag: 
                dic[k] = 'N'
            else:
                dic[k] = 'Y'
    count += 1

print(count)

 

 

4. 분석

1. Time : O(N^2)   => 전구의 개수는 (1 <= N <= 1000) 이므로 1000 * 1000 = 10 ^ 6. 브루트포스로 충분하다. 
2. Space :
3. 소요시간 : 20분
4. 제출 횟수 (무작정 제출하기 않기)  : 2회 
5. 어려웠던 부분과 해결한 방법 :
6. 실수가 줄어들었는가 ?