학번( 3711번 )

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

 

나의 풀이

import sys

def _main(n_list):
    answer = 1

    while True:
        check_set = set()
        for i in n_list:
            check_set.add(i % answer)
        if len(check_set) == len(n_list):
            return answer
        answer += 1

n = int(sys.stdin.readline())
for _ in range(n):
    n_ct = int(sys.stdin.readline())
    n_list = []
    for __ in range(n_ct):
        n_list.append(int(sys.stdin.readline()))
    print(_main(n_list))

 

시간 복잡도

for _ in range(n) : n 가지를 구함 ( 선형 시간 복잡도 )
    n_ct = int(sys.stdin.readline())
    n_list = []
    for __ in range(n_ct) : 학번 갯수 ( 선형 시간 복잡도 )
        n_list.append(int(sys.stdin.readline()))
    print(_main(n_list)) : 최소 나머지 구하는 함수 ( 이차형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 삼차형 시간 복잡도 ( O(n ** 3) )