programmers 3

프로그래머스 문제 풀기

하루에 한 문제씩.
Lv.1 부터 시작해서 언젠간 Lv.3 ~ Lv.4도 풀수 있도록 될 때까지!

Lv.1 나머지가 1이 되는 수 찾기

문제

자연수 n이 매개변수로 주어집니다.
n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요.
답이 항상 존재함은 증명될 수 있습니다.

제한 사항

3 ≤ n ≤ 1,000,000

기본코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        return answer;
    }
}

문제 풀이

이번 문제는 n을 나눈 나머지가 1이 되게하는 가장 작은 수를 구하는 문제입니다.
지난번 문제와 마찬가지로 풀이 순서를 한 번 써보겠습니다.

1. n을 나눈다.
2. 나눴을 때 나머지가 1이 되는 경우의 수를 구한다.
3. 구한 숫자 중 가장 작은 수를 return한다.

이렇게 써보았습니다.
이제 작성한 내용 1번부터 차근차근 코드로 작성해보겠습니다.

n / ? ....

우리가 흔히 알고있는 나누기는 이렇게 / 을 사용하여 작성하면 됐지만,
오늘 문제는 ‘나머지’가 1이 되는 경우가 핵심입니다.
저 코드를 변경해보면

n % ? ....

이런 식으로 변경할 수 있습니다. %연산자는 나머지를 산출하는 연산자입니다.
그럼 문제 풀이 1번은 해결했습니다.

이제 2번을 작성해볼 건데, 그전에.
오늘의 문제가 원하는 답은 입력 받는 변수 n을 나누어
나머지가 1이 산출되는 숫자 중 가장 작은 숫자를 원하고 있습니다.
그럼 나누는 수를 i라고 가정해보았을 때, i는 1부터 n을 나누기 시작해
n보다 작을 때까지만 1씩 증가시키는 게 좋을 것 같습니다.

이렇게 말로 서술하니 어디서 많이 본 코드 문법이 떠오르지 않나요?
네, 바로 for()문입니다.
어째 모든 문제를 for()문으로 푸는 느낌이지만,
가장 정확하고 간결하게 작성할 수 있는 방법이니 한 번 작성해보겠습니다.

for(int i = 1; i<n; i++) {
    ...
}

방금 제가 작성한 부분을 코드로 구현했습니다.
i는 1로 시작하여 n보다 작을때까지 증가하게 작성한 것입니다.
이제 앞서 작성한 1번 풀이 코드를 같이 구현해보면

for(int i = 1; i<n; i++) {
    n % i
}

음…
이런 식으로 작성하면 당연히 에러가 나겠죠 ㅎㅎ
우리가 원하는 건 n을 i로 나누는 게 아니라 ‘나머지 값’이 1일 때를 구하는 것입니다.
이 점에 포커스를 두고 다시 작성해보면.

for(int i = 1; i<n; i++) {
    if(n % i == 1) {
        ...
    }
}

이렇게 if()문을 사용하여 작성할 수 있습니다.
%연산자를 사용해 n과 i를 나누어 산출된 나머지가 1일 때를 실행 조건문으로 작성했습니다.
그럼 이제 구한 숫자 중 가장 작은 수를 return하면 문제 해결입니다.

for(int i = 1; i<n; i++) {
    if(n % i == 1) {
        return i;
    }
}

이렇게 작성해서 바로 해결할 수 있습니다.
i는 1부터 n을 나누기 시작하고 나머지가 1이 아닐 경우 계속 증가합니다.
그러다 나머지가 1이 나올 때 바로 i를 return하니 자연스레 최소값이 구해지는 겁니다.

정리겸 제출용 코드를 작성해보면.

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i= 1; i< n; i++) {
            if(n % i == 1) {
                return i;
            }
        }
        
        return answer;
    }
}

이렇게 작성하고서 제출하면 문제 해결입니다!
오늘도 이렇게 한 문제를 풀어보았습니다.
Lv 1 이라 간단한 느낌이 있지만, 기초부터 다시! 라는 느낌으로
당분간 Lv 1 문제풀이를 하겠습니다.