프로그래머스 1단계
-
[프로그래머스/JavaScript] 나머지가 1이 되는 수 찾기IT Study/프로그래머스 2023. 11. 2. 11:26
이 문제를 처음 봤을 때는 굉장히 쉽다고 생각했습니다. 그저 for문을 돌려 나머지가 1이 되는 수를 찾으면 되니까... 너무 쉽잖아?라고 생각했는데요. 그러나 이제는 시간복잡도를 고려해 코드를 작성해야겠다는 생각에 조금 더 고민하는 시간을 갖게 되었습니다. 🤔 생각의 흐름 (1) n을 x로 나눈 나머지가 1이 되도록 하는 가장 자연수를 찾기 위해 n % x === 1을 꼭 사용해야 할까? (2) 새로운 변수 m을 m = n - 1로 선언하고, 나머지가 0이 되는 가장 작은 자연수를 찾아보자. (3) for문으로 전체를 돌린다면 시간복잡도는 O(n)이 될 텐데... 어떻게 하면 시간복잡도를 줄일 수 있을까? (4) m이라는 수를 기준으로 중간 값, 혹은 제곱근 값 이하에서 찾으면 어떨까? 💻 결과 코드 ..