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

문제 설명

주어진 자연수 n을 어떤 자연수 x로 나눈 나머지가 1이 되는 가장 작은 자연수 x를 찾는 문제입니다.

---

1. Java 코드 풀이

class Solution {
    public int solution(int n) {
        for (int x = 2; x < n; x++) {
            if (n % x == 1) {
                return x;
            }
        }
        return -1;  // 조건 상 이 부분은 실행되지 않음
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.solution(10));  // 출력: 3
        System.out.println(sol.solution(12));  // 출력: 11
    }
}

설명:

• x = 2부터 시작해서 n-1까지 반복문을 돌며, n % x == 1이 되는 가장 작은 x를 찾습니다.
• 첫 번째로 조건을 만족하는 x가 가장 작은 값이므로 즉시 반환합니다.

---

2. Python 코드 풀이

def solution(n):
    for x in range(2, n):
        if n % x == 1:
            return x

# 테스트
print(solution(10))  # 출력: 3
print(solution(12))  # 출력: 11

설명:

• for 루프를 사용하여 2부터 n-1까지 탐색하며, 조건에 맞는 가장 작은 값을 찾습니다.
• 찾는 즉시 값을 반환합니다.

---

3. 시간 복잡도 분석

• 시간 복잡도: O(n)
  • 최악의 경우, x를 n-1까지 탐색해야 하므로 반복문이 n번 실행됩니다.
  • 즉, 시간 복잡도는 O(n)입니다.

---

4. 공간 복잡도 분석

• 공간 복잡도: O(1)
  • 추가적인 배열이나 데이터 구조 없이 상수 공간만 사용하므로, 공간 복잡도는 O(1)입니다.

---

5. 다른 자바 코드 풀이 방법

방법 1: Stream API를 사용한 풀이

import java.util.stream.IntStream;

class Solution {
    public int solution(int n) {
        return IntStream.range(2, n)
                        .filter(x -> n % x == 1)
                        .findFirst()
                        .orElse(-1);  // 조건 상 항상 해답이 있음
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.solution(10));  // 출력: 3
        System.out.println(sol.solution(12));  // 출력: 11
    }
}

설명:

• IntStream.range(2, n)을 사용하여 2부터 n-1까지의 범위를 생성합니다.
• filter(x -> n % x == 1)을 통해 조건을 만족하는 값을 필터링하고, findFirst()로 가장 첫 번째 값을 반환합니다.

방법 2: while문을 사용한 반복 풀이

class Solution {
    public int solution(int n) {
        int x = 2;
        while (n % x != 1) {
            x++;
        }
        return x;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.solution(10));  // 출력: 3
        System.out.println(sol.solution(12));  // 출력: 11
    }
}

설명:

• while 루프를 사용하여 n % x == 1이 될 때까지 x를 1씩 증가시킵니다.
• 조건을 만족하는 첫 번째 x 값을 반환합니다.

---

6. Java 코드 풀이 방법들 간의 비교

방법	장점	단점
기본 for 루프	직관적이고 간단함	다른 방식에 비해 코드가 덜 간결할 수 있음
Stream API 사용	함수형 스타일로 코드가 매우 간결함	성능적으로 아주 미세한 오버헤드 발생 (스트림 처리 때문)
while문 반복	비교적 간결하고 효율적	다른 방식에 비해 직관적이지 않을 수 있음

• Stream API 방식: 코드가 간결하며 함수형 스타일을 선호하는 사람들에게 적합합니다. 하지만 작은 성능 차이로 인해 반복문 방식이 조금 더 효율적일 수 있습니다.
• while문 방식: while을 사용한 반복 방식은 필요 조건만을 처리하여 효율적이지만, 일반적인 for 루프보다 가독성이 떨어질 수 있습니다.

---

결론

• 이 문제는 기본적인 탐색 문제로, 가장 직관적인 방법은 for 또는 while을 이용해 조건을 만족하는 값을 찾는 것입니다.
• Stream API는 코드를 간결하게 만들 수 있지만, 작은 성능 오버헤드가 발생할 수 있습니다.
• 시간 복잡도는 O(n), 공간 복잡도는 O(1)로, 문제의 제한 조건 내에서는 성능적으로 충분히 효율적인 해결 방법입니다.