알고리즘🅰/프로그래머스

[프로그래머스] 나머지가 1이 되는 수 찾기

개발조각 2022. 2. 15. 13:34
728x90
반응형

2021.11.20에 푼 문제입니다.

 

이번 문제는 해결방안을 설명하기도 부끄러울 정도로 쉬운 문제라 해결방안 쓰기도 머쓱하네요;;

 

이 문제에서는

문제 설명에서 "자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요."문장에서

  1. n을 x로 나눈 나머지가 1 이 되도록
  2. 가장 작은 자연수 x를 return

이 두 문장이 중요합니다.

 

이 두 문장을 설명하자면

  1. n을 x로 나눈 나머지가 1 이 되도록 : n % x === 1
  2. 가장 작은 자연수 x를 return : 나머지가 1이 되는 자연수를 다 구할 필요 없고 가장 작은 자연수만 찾으면 된다.

이렇게 됩니다.

이 두 문장을 활용해서 코드로 작성해 보겠습니다.

해결방안

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

 

for(let i=0; i<n; i++)

이번에도 역시 for문을 사용해서 풀었습니다.

여기서 for문을 쓴 이유는 1~n-1까지 차례대로 n % i === 1을 해주기 위해서입니다.

그래서 n % i === 1값이 나오는 가장 작은 수를 구할 수 있게 됩니다.

 

여기서 for문안에서 i=2, i<n으로 한 이유는

n에서 0, 1, n으로 나누면 무조건 0이 나오기도 하고

제한 사항에서 3 ≤ n ≤ 1,000,000도 있기 때문에

 i=2, i<n으로 넣어주어 2~n-1까지 반복하게 했습니다.

 

if(n % i === 1) return i;

여기서 가장 중요한 것은 가장 작은 수를 return 하라고 했습니다.

그러기 위해서 return을 써주는 것이 중요한데요.

 

작은 수부터 차례대로 "if(n % i === 1)"를 해주고, for문을 다 실행할 필요 없이 조건에 맞으면 바로 끝내면 되는 거잖아요?

이미 for문에서 작은 수부터 차례대로 넣어주고 있기도 하고요.

그래서 조건에 맞으면 바로 끝내기 위해 "return"을 사용했습니다.

 

테스트 1 (n = 10)
for(let i=2; i<n; i++) -> 2, 3, 4, 5, 6, 7, 8, 9 반복
i =2일 때
if(n % i === 1) -> if(10 % 2 === 1) -> false -> i=3실행
=> 10 % 2 = 2

i =3일 때
if(n % i === 1) -> if(10 % 3 === 1) -> true

답 : 3

테스트 2 (n = 12)
for(let i=2; i<n; i++) -> 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 반복
i = 2일 때
if(n % i === 1) -> if(12 % 2 === 1) -> false -> i=3실행
=> 12 % 2 = 0

i = 3일 때
if(n % i === 1) -> if(12 % 3 === 1) -> false -> i=4실행
=> 12 % 3 = 0

i = 4일 때
if(n % i === 1) -> if(12 % 4 === 1) -> false -> i=5실행
=> 12 % 4 = 0

i = 5일 때 if(n % i === 1) -> if(12 % 5 === 1) -> false -> i=6실행
=> 12 % 5 = 2

i = 6일 때
if(n % i === 1) -> if(12 % 6 === 1) -> false -> i=7실행
=> 12 % 6 = 0

i = 7일 때
if(n % i === 1) -> if(12 % 7 === 1) -> false -> i=8실행
=> 12 % 7 = 5

i = 8일 때
if(n % i === 1) -> if(12 % 8 === 1) -> false -> i=9실행
=> 12 % 8 = 4

i = 9일 때
if(n % i === 1) -> if(12 % 9 === 1) -> false -> i=10실행
=> 12 % 9 = 3

i = 10일 때
if(n % i === 1) -> if(12 % 10 === 1) -> false -> i=11실행
=> 12 % 10 = 2

i = 11일 때
if(n % i === 1) -> if(12 % 11 === 1) -> true

답 : 11

여기까지 프로그래머스 나머지가 1이 되는 수 찾기 해결방안에 대해 설명해보았습니다.

728x90
반응형