프로그래머스 - 나머지가 1이 되는 수 찾기 java :: 월간 코드 챌린지 시즌3

87389번

https://programmers.co.kr/learn/courses/30/lessons/87389?language=java 

코딩테스트 연습 - 나머지가 1이 되는 수 찾기

---

풀이

• 풀이1

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

n의 입력값은 무조건 3 이상입니다.

그러므로 1이 아닌 다른 값이 나오려면 최솟값은 2입니다.

2부터 n까지 순회하며 나머지가 1인 가장 작은 값을 찾으면 됩니다.

수학적으로 공식을 만들 수 있을까 고민했는데 모르겠어요... 정말 없는 건지ㅜㅜ

 

✔️ 테스트 케이스 처리속도: 평균 0.02ms / 최대 4.7ms

한 케이스의 경우만 4.7ms가 나오고 나머진 0.02ms 정도였습니다. 저 케이스는 아마 n=1,000,000 겠죠?

 

• 풀이2

public int solution2(int n) {
	return IntStream.range(2, n).filter(i -> n % i == 1).min().getAsInt();
}

너무 쉬운 문제라 이렇게만 끝내면 아쉬워서 Stream으로도 하나 풀어봤어요.

아무래도 2~n까지 전부 순회하다보니 처리속도는 완전 똥입니다...^^

 

✔️ 테스트 케이스 처리속도: 1.20ms ~ 12.57ms

처리속도도 아주 제각각입니다... n의 값에 따라 확 달라지네요