[골드 I] 6523번. 요세푸스 한 번 더!

 문제 

https://www.acmicpc.net/problem/6523

6523번: 요세푸스 한 번 더!

 사용 언어 

Python3

 풀이 과정 

👏👏👏👏👏 일단 박수 👏👏👏👏👏

내가  골드 I  문제를 풀다니!! (사실 난이도 기여하신 분들이 많이 없어서 진짜 그 정도같진 않지만...)

그래도 기분이 좋자나~!~!!

 

사실 이 문제는 요세푸스 문제를 풀었을 때 바로 도전했던 문제인데.. 연산량이 적은 테스트케이스는 출력값이 잘 나왔지만 나머지 두 개는 계속 시간초과가 났던 문제였다.

그래서 한 달 정도 실패로 남아있었는데 너무 거슬려서! 다시 도전했더니 성공~

 

처음 내가 짰던 코드는 다음과 같다.

from sys import stdin
from collections import Counter

while True:
    try:
        N, a, b = map(int, stdin.readline().split())
        x = 0
        playing = Counter({str(x)})
        while True:
            # (a * x * x + b) % N
            x = (((a % N) * (((x % N) * (x % N)) % N)) % N + (b % N)) % N
            playing.update({str(x)})
            if playing.most_common(1)[0][1] == 3:
                break
        justOnetime = list(playing.values()).count(1)
        # print(playing)
        print(N - len(playing) + justOnetime)
    except ValueError:
        break

지금 보면 당연히 시간이 많이 걸릴 수밖에 없는 코드였다. most_common을 매 번 시행하다니...근데 다시 문제를 읽으며 깨달은건 Counter 객체를 사용할 필요가 전혀 없다는 거였다. 어차피 3번 걸린 사람이 있는 이상 모두가 집에 가야 하는데 그렇다면 1번씩 추가할 때마다 이 사람이 3번 걸렸는지를 확인하면 되니까... (아주 바보같은 로직을 짜고있었던게지;;)

 

어쨌든 그걸 깨닫고 딕셔너리로 자료구조를 바꿔서 탈출문을 만들어줬더니 문제였던 테스트 케이스들의 답이 바로 떴고! 제출했더니 맞았습니다!!

이후에 코드 개선을 해나가며 시간을 조금씩 줄인 과정을 아래에 적어보겠다.

 제출 답안 

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    while True:
        Input = input().split()
        if len(Input) == 1:
            break

        N, a, b = map(int, Input)
        x = 0
        playing = {x: 1}
        while True:
            x = (((a * x) % N) * (x % N) + b) % N
            if x in playing:
                playing[x] += 1
                if playing[x] == 3:
                    break
            else:
                playing[x] = 1
            
        justOnetime = list(playing.values()).count(1)
        print(N - len(playing) + justOnetime)

 공부한 내용 

모듈러 연산(%) 횟수 줄이기

처음에 연산량이 많았을 때, 모듈러 연산의 크기가 너무 커서 그런 것 같아가지고 대학 수업시간에 배웠던 것 같은 모듈러 연산 횟수 줄이기를 검색했다. (이 문제에서의 시간 초과는 그런 문제가 아니었지만)

 

따라서 모듈러 분배법칙을 이용해서 위의 연산을 아래 연산으로까지 분배했다.

전 : (a * x * x + b) % N
후 : (((a % N) * (((x % N) * (x % N)) % N)) % N + (b % N)) % N

근데 사실ㅋㅋㅋㅋㅋ 이렇게까지 많이 나눠버리면 또 쓸 데 없는 연산이 늘어나기 때문에 필요 없을 것 같고

"적당한" 분배법칙을 사용해야 한다.

 

어쨌든 나중에 기억하기 위한 분배법칙 종류!

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

 

출처: https://velog.io/@gidskql6671/%EB%82%98%EB%A8%B8%EC%A7%80Modulo-%EC%97%B0%EC%82%B0-%EB%B6%84%EB%B0%B0%EB%B2%95%EC%B9%99

딕셔너리 초기화

그 다음에 사용한 방법은 딕셔너리를 N의 개수만큼 0으로 초기화해놓고 걸릴 때마다 1을 증가시키는 것이었다. 파이썬에는 list comprehension이 있으니 비슷하게 딕셔너리에서 사용하는 방법을 찾아봤다. (이것도 결국 이 문제에서는 사용하지 않음)

dic1 = {i: 0 for i in range(10)}
dic1[1] += 100
print(dic1)
# {0: 0, 1: 100, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}

dic2 = {i: [] for i in range(10)}
dic2[1].append("hello world")
print(dic2)
# {0: [], 1: ['hello world'], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: [], 9: []}

혹은 대안으로 collections의  defaultdict( ) 를 사용할 수 있는데,

아래와 같이 defaultdict( ) 인자로 주어진 객체의 기본 값을 딕셔너리의 초기값으로 지정할 수 있다.

# int
dic_int = defaultdict(int)
dic_int['key'] # 0

# list
dic_list = defaultdict(list)
dic_list['key'] # []

자세한 내용은 출처를 참고하는 걸로.

출처: https://ebbnflow.tistory.com/306 

 코드 개선 

1. 먼저 저번 시간(?)에 배운  if __name__ == "__main__":  을 추가해보았다.

➡ 한 줄을 추가했을 뿐인데 연산량이 좀 있는 코드라 그런지 꽤 유의미한 차이를 보였다.

 

2. 그리고 이번에 시도해 본 try ~ catch문으로 입력값 검증하기를 그냥 len으로 변경했다.

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    while True:
        Input = input().split()
        if len(Input) == 1:
            break

➡ 아무래도 try ~ catch에서 오류를 처리하는 과정이 더 오래 걸릴 것 같아 바꿔봤는데 또 조금 줄어들었다.

 

3. values( )에서 1번 걸린 경우를 추출하는 것도 시간이 좀 걸리지 않을까 싶어서 변수 하나에 +- 하는 로직을 추가해봤다.

justOnetime = 1
        while True:
            x = (((a % N) * (((x % N) * (x % N)) % N)) % N + (b % N)) % N
            if x in playing:
                playing[x] += 1
                if playing[x] == 2:
                    justOnetime -= 1
                if playing[x] == 3:
                    break
            else:
                playing[x] = 1
                justOnetime += 1

➡ 그랬더니 지금까지 중 제일 오래걸렸다...! 연산량이 많다 보니까 마지막에 한 번만 계산하는게 훨씬 낫나 보다.

 

4. 그러고 나서 생각해보니 내가 과하게 분배법칙으로 늘려놓은 모듈러 연산이 생각났다. 그래서 그 연산을 조금 더 간결하게 줄였다.

전 : (((a % N) * (((x % N) * (x % N)) % N)) % N + (b % N)) % N
후 : (((a * x) % N) * (x % N) + b) % N

➡ 가장 유의미한 변화가!! ㅋㅋㅋㅋㅋㅋㅋㅋ 괜히 늘리고 늘렸자나... 괄호 갯수 머리아팠는데....

 

 

---

어쨌든 여기까지 개선하고  맞힌 사람 을 봤더니

흐히히흐힣 기분좋아✨ 짜릿해⚡

 

 

+) 2022-08-13

 

오랜만에 이 문제를 우연히 봤다가 어? 이거 이제 defaultdict로 풀 수 있겠는데 싶어서 코드를 수정해봤다.

from collections import defaultdict
from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    while True:
        Input = input().split()
        if len(Input) == 1:
            break

        N, a, b = map(int, Input)
        x = 0
        playing = defaultdict(int)
        while True:
            x = (((a * x) % N) * (x % N) + b) % N
            playing[x] += 1
            if playing[x] == 3:
                break
            
        justOnetime = list(playing.values()).count(1)
        print(N - len(playing) + justOnetime)

 

근데 나는 이렇게 변경하면 if문을 없앨 수 있어 깔끔하고 시간 역시 줄어들 거라고 예상했는데... 시간이 꽤나 늘어났다!!(반전)

defaultdict도 탐색은 dictionary랑 같은 시간복잡도를 가진다고 했는데, 그렇다면 선언하는 부분에서 시간이 더 걸리나보다. 새로운...발견!