[Java] 나머지가 1이 되는 수 찾기 Lv1

나머지가 1이 되는 수 찾기

문제 프로그래머스 FAQ 내용을 보니 카카오나 기업의 문제들은 저작권이 있으니 풀이를
github나 개인블로그에 올리지 말라고 되어 있어서 링크로 대체합니다.

출처: Programmers
나머지가 1이 되는 수 찾기

문제의 이해

처음에 Lv1인데 문제 푼 수가 너무 적길래 왜? 라고 생각했다가. 문제를 보니까 알 수 있었다. 문제가 문제같지 않아서… 그런거 같다. 문제 들어오기전에 약간 쉬운 문제니까 제한사항이나 요구조건이 엄청나게 큰 수 일거라 생각했는데 굉장히 작은 숫자였다. 물론 이런 간단한 문제를 깔끔하게 푸는 것도 실력이라고 생각한다.

내가 생각한 풀이 방법

조건

1. 주어진 자연수 n (3 <= n <= 1,000,000)
2. n % a = 1 을 만족하는 가장 작은 자연수 x를 구해라
3. 여기서 x는 항상 존재한다는 것을 증명될 수 있다.(무슨 말인가 했는데, 1,000,000,000,000,000,000,000,000,000,000,000,001 이 있다고 가정하고 저기에 -1해서 나누면 나머지는 1이 나오니 증명이 가능하다는 말인듯)

문제가 조건이 많이 있는 게 아니라서 쉬울 것 같아서 몇가지로 풀어보았다. 먼저 입력되는 숫자가 3부터이고 나누어서 1이 나오는 가장 작은 수를 찾으려면 2부터 +1 해가면서 나누면 되겠다고 생각했다.

풀이

첫 번째 풀이

반복문으로 2부터 주어진 n/2 전까지 나눠보면 되겠다 했는데 생각해보니 n이 3이라면 반복문의 조건이 시작부터 1이라서 처음부터 시작이 안되어서 그냥 조건은 n으로 주었다. 그리고 다시 생각해보니 어차피 조건의 맞는 i가 나오면 바로 return이니 n/2는 의미가 없었다.

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

실행결과는 통과했지만 풀고 나서 뭔가 더 나은 코드가 있지 않을까 생각해서 두 번째 풀이를 해봤다.

두 번째 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        int smallerX = 2;
        int modValue = 0;
        
        while(modValue != 1){
            modValue = n % smallerX;
            answer = smallerX++;
        }
        return answer;
    }
}

이 코드도 결국 통과는 했지만 맘에 안들었다. 그래서 세 번째 풀이를 해봤다.

세 번째 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        int smallerX = 2;
        
        do
        {
            answer = smallerX;
        }while(n % smallerX++ != 1);
        
        return answer;
    }
}

통과지만, 다시 첫 번째 풀이를 보니 그닥 나은 코드 같지는 않았다. 역시 코드를 잘 쓰는 건 어렵다.