[백준 13909번 파이썬]'창문닫기' 모든 풀이 비교 분석

오늘은 백준 13909번 창문닫기를 풀어보았다.

문제

논리 및 아이디어

먼저 짠 나의 코드

먼저 든 생각은 '에라토스테네스의 체 알고리즘에서 했던 것처럼 배수 인덱스에 접근하여 창문의 상태를 바꿔주면 되겠다 '였다.

1. 딕셔너리를 통해 창문의 이름(즉, n의 배수)과 창문의 상태(0 또는 1)를 만들어준다.
2. 1부터 N까지 숫자를 증가시키면서 N의 배수에 접근하여 창문을 열고 닫는다.
3. 열려있는 창문의 갯수를 센다.

시간초과 실패 후 찾은 최적의 코드

1. 1의 배수는 모든 창문을 연다.
2. 창문은 열고 닫는다. 즉, 해당 숫자에 짝수 번 접근하면 창문은 닫혀있다. 반대로 홀수 번 접근하면 창문은 열려있다.
3. 숫자에 접근하는 횟수는 약수와 관련된다. 가령, 4는 1번째 사람, 2번째 사람, 4번째 사람이 열고 닫으므로 마지막에 열려있을 것이다. 6은 1번째, 2번째, 3번째, 6번째 사람이 열고 닫으므로 닫혀있을 것이다.
4. 제곱수는 약수가 홀수이므로 열려있을 것이고 창문의 개수 N까지에서 제곱수를 찾으면 된다.

나의 코드

num=int(input())
list=[i for i in range(1,num+1)]
doors=dict.fromkeys(list,1)        #1이 열린 상태, 0이 닫힌 상태
for number in range(2,num+1):    #이미 열린 상태로 시작하므로 2부터 시작
    start=1
    while start*number<=num:
        if doors[start*number]==0:     #열려있다면
            doors[start*number]=1    #닫고
        else:                        #닫혀있다면
            doors[start*number]=0    #열기
        start+=1
cnt=0
for key,val in doors.items():        #열려있는 창문 갯수 세기
    if val==1:
        cnt+=1
print(cnt)

결과는 메모리초과

최대 창문 개수가 21억까지이므로 메모리초과는 어쩌면 당연한 것이었다.

최적의 코드

num=int(input())
cnt=0
start=1
while start**2<=num: #제곱수가 입력한 수를 넘지 않을 때까지
    cnt+=1
    start+=1
print(cnt)

질문게시판에서 뒤적이다 누군가 21억개까지라고 리스트 21억 개까지 만들면 뒤져요 라는 댓글을 보고 이 문제가 약수, 배수, 소수 단계에 들어가 있는 이유를 생각해 보았다.

해서 떠올린 아이디어(위 논리 및 아이디어 파트에 적어놓았습니다.)

코드별 차이점

1. 알고리즘

알고리즘 자체가 다르다는 것이 차이점이다.

나의 코드는 정직하게 풀었다. 하지만 제한된 자원을 가지고는 역부족이었다.

최적의 코드에서는 원하는 결과를 얻었으나 간접적으로 풀었다.

창문의 개수를 N이라 할 때, 나의 코드의 시간복잡도는 대략 $O(\sum_{n=2}^{N}\left\lfloor\frac {N}{n}\right\rfloor\times N^2)$

최적의 코드의 시간복잡도는 대략 $O(log_2N)$

배운 점 및 보완할 점

1. fromkeys 함수

딕셔너리를 한 번에 만들 함수를 고민하다 fromkeys 함수를 찾았다.

fromkeys(arr, default_value)

리스트의 요소를 키 값으로 하는 딕셔너리를 한 번에 만들어주고, 기본값도 정할 수 있다.

출처

백준 홈페이지 13909번

University > 서강대학교 > 2016 Sogang Programming Contest > Master B번