[SWEA 코딩] 주기 찾기 - PYTHON #11316

소스 코드

# tc
T = int(input())

for tc in range(1,1+T):
    s,p,q,m = map(int,input().split())

    # Ai값이 존재했는지(방문) 여부를 확인
    visited = [0]*m
    
    # 중복된 값을 발견했을 때, 그 값의 index값을 찾기 위해 Ai 값을 저장
    check = [0]*m

    # A0
    temp = s
    
    # A0 방문 확인
    visited[temp] = 1
    
    # A0의 값 0번 index에 저장
    check[0] = temp

    # m+1 안하면 0,0,0,1 케이스 오류 발생
    for x in range(1,m+1):
        temp_sum = (p * temp + q) % m
        temp = temp_sum
        
        # 중복 없으면
        if visited[temp] == 0:
            
            # 체크
            visited[temp] = 1
            
            # 해당 index에 저장
            check[x] = temp

        else:
            break

    # break 걸린 x값 - 중복된 정수의 index 값
    res = x - check.index(temp)

    print('#{} {}'.format(tc,res))

 

---

해결 방법

1. 처음 중복이 발생하면, 발생한 위치와 값을 저장(x,temp)

 

2. check에서 temp와 같은 값을 찾음(.index() 사용하면 가장 먼저 발견되는 index 값 나타냄)

 

3. x(주기가 다시 시작되는 지점) - check.index(temp)(주기가 시작되는 지점)

 

4. 처음에는 문제의 예시로 나온 2이상인 모든 정수를 조건으로 잘못이해함

 

5. 사실은 어떤 정수 n0 이상인 모든 n에 대한 주기를 찾는 것임

 

---

느낀 점

문제를 대충 읽지 말자!!

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.