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

🔥개인 취미 목적으로 프로그래머스 문제를 정리한 게시글입니다.

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

프로그래머스

✏️ 문제설명

자연수 n이 매개변수로 주어집니다.

n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해 주세요.

답이 항상 존재함은 증명될 수 있습니다.

💡 제한사항

3 ≤ n ≤ 1,000,000

📚 입출력 예

n	result
10	3
12	11

---

💻 소스 코드

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

주어진 코드는 정수 n을 입력으로 받아서, 1부터 n까지의 모든 정수를 순회하면서 n을 해당 정수로 나누었을 때 나머지가 1인 첫 번째 정수를 반환하는 함수입니다.

코드의 동작을 다음과 같이 설명할 수 있습니다.

1. for 루프를 사용하여 1부터 n까지의 모든 정수를 순회합니다. 이때, i 변수가 순회하는 정수를 나타냅니다.
2. 각 반복에서, 현재 i 값으로 n을 나눈 나머지를 계산합니다. n % i 연산을 통해 나머지를 구합니다.
3. 나머지가 1인 경우, 즉, n % i == 1 조건이 참인 경우, 해당 i 값을 반환합니다.
4. 모든 정수를 순회한 후에도 나머지가 1인 i가 없다면, -1을 반환합니다.

이 코드는 1부터 n까지의 모든 정수를 순회하면서 n을 나누었을 때 나머지가 1인 첫 번째 정수를 찾고, 그 값을 반환합니다. 따라서 반환되는 값은 n을 나누었을 때 나머지가 1인 정수 중 가장 작은 정수입니다.

시간 복잡도

위 코드의 시간 복잡도는 1부터 n까지 반복문을 실행하기 때문에 시간 복잡도는 O(n)입니다.

여기서 n은 입력된 정수 n의 값에 비례합니다.

공간 복잡도

사용된 메모리 공간은 상수이기 때문에 입력된 값 n에 상관없이 사용되는 변수는 i 하나뿐이기 때문에 공간 복잡도도 O(1)입니다. 입력값 n의 크기와 관계없이 항상 일정한 메모리 공간을 사용합니다.