[알고리즘 || 프로그래머스] 나머지가 1이 되는 수 찾기 + 🏆 고수의 풀이법

https://school.programmers.co.kr/learn/courses/30/lessons/87389

프로그래머스

 

function solution(n) {
    for (let i = 0; i < n; i++) {
        if (n % i === 1) {
            return i;
        }
    }
}

단순한 나의 풀이.

아마 알고리즘 스터디를 안했더라면 잘 한 줄 알고 그냥 넘어갔겠지..!

 

 

<나의 기존 공부 방식>

1. 어떻게든 풀어본다.

2. 맞춘다.

3. 다른 사람의 풀이를 참고해 모르는 방식, 참고 할만한 방식, 메서드 등을 공부한다.

4. 다른 문제를 푼다.

5. 가독성 면에서 짧은 코드가 좋다고 생각했다.

 

 

<고수들의 풀이>

 

첨엔 암것도 모르고 왜 코드를 이렇게 길게 짰지? 생각했다.

하지만 고수들은 다 생각이 있었던 거시다...

굳이 안해도 되는 계산은 하지 않는다. 

 

1. x의 초기 값 3부터 진행
==> n이 짝수면 2로 나누면 나머지가 1이 될 수 없기 때문에 x는 3부터 시작합니다. 그리고 n이 1을 제외한 홀수 일 경우 무조건 2를 반환하기 때문에 홀수는 체크할 필요 없습니다. 즉 짝수만 고려하면 됩니다.
2. 짝수 n을 반복문으로 체크할 경우 x는 n-1까지 검사할 필요 없습니다.
n % n-1 === 1이므로 반복문의 조건은 x < n-1까지 !

 

이번 프로그래머스 문제는 입출력 예 1, 2의 설명이랑 제한 사항을 보면 최적화 할 수 있을 겁니다

제한사항
3 ≤ n ----> 3 % 2 === 1 -> return 23보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 3을 return 해야 합니다. 짝수(4, 10) % 3 === 1 --> return 3부터 시작12를 11로 나눈 나머지가 1이고, 11보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로 ----> n % n-1 === 1

 

 

1번 문제에서 확연히 속도 차이가 나는 걸 볼 수 있다.

 

내가 짠 코드 : 5.21ms

고수님의 코드 : 3.99 ms

 

시간 복잡도는 0(n) 보다 줄일 수 없는 문제지만 같은 O(n) 일지라도 시간 속도는 최소 2배정도 차이 납니다. 왜냐하면 처음에 짝수냐 홀수냐 판단으로 짝수만 고려하면 되기때문입니다

 

이런 코드가 엄청 많다면...?! 

프로그램이 엄청 느려질 수도 있겠다...!

 

 

+

break 문은 자주 쓰지 않는게 좋다?

- 코드를 강제로 끊고 나오는 거기 때문에

- 가독성이 떨어진다.

 

라는 의견도 있다는걸 알려주심.