[프로그래머스] #15 나머지가 1이 되는 수 찾기 (MB, ms 성능확인)

▶ 문제

자연수 n이 매개변수로 주어진다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하는 solution 함수 만들기. 

 

▶ 제한사항

 3 ≤ n ≤ 1,000,000

 

▶ 풀이

어떻게 짜야할지 전혀 모르겠다.... 일단 종이에 써서 대강 그려보기

코드 그리기 끝!

이제 이걸 보면서 그대로 코드를 짜보기

def solution(n):

    if n % 2 == 1:           # n이 홀수면
        return 2             # 답은 항상 2
                             # n이 짝수면        
    for i in range(2, n):    # 1제외, n-1까지
        if (n-1) % i == 0:   # (n-1)을 나눠봄
            return i

헉 통과.....

글씨로 쓴 다음에 보고하니까 되게 막막했던게 엄청 쉽게 풀렸다!

 

근데 생각해보니 굳이 홀수,짝수 안나눠도 되고,

% 연산자를 좀더 효율적으로 사용할 수도 있음.

def solution(n):
    for i in range(2, n):
        if n % i == 1:        # 그냥 == 1 쓰면되네
            return i

 

또 별것도 아닌걸로 성능 확인해보기...

 

짝수홀수 나눠서 하면 메모리는 적고 시간은 오래걸린다. 연산이 나눠져서 그런가?

반대로 한번에 %연산자에 집어넣어버리면 메모리는 많고 시간은 짧아짐. 나눗셈한 나머지를 어딘가에 기억해야 1과 비교할 수 있기 때문인가?..

사실 너무 미세한 차이기 때문에 의미 없을 것 같지만 그냥 궁금해서 확인해봤다

 

중요한건

코드짜기가 막막할때는 종이에 대강 코드그리기부터 시작하기!

 

 

 

---