https://school.programmers.co.kr/learn/courses/30/lessons/87389
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제
자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다.
제한사항
- 3 ≤ n ≤ 1,000,000
발상
나머지가 1이 되게하는 수를 구하는 문제이다.
나눈다는 로직에 소인수분해가 떠올라서 주어진 문제와 맞지 않는 방향으로 알고리즘을 짰다가 테스트케이스가 실패하는 부분이 나와서 디버깅에 시간이 걸렸다.
의사코드
실패케이스
1. 초기값 세팅, 목표값 선언 (주어진 값 -1)
2. 반복(목표값 >= 기준값^2)
{
1. 나누어 떨어지면 기준값을 임시반환값으로
2. 목표값을 소인수분해하여 값을 줄임
3. 나누어 떨어지지 않으면 기준값 ++
}
성공케이스
1. 2부터 시작하여 나머지가 1인 값이 나올 때가지 전체반복
개선
초기 케이스의 문제는 소인수분해와 관계없는 문제였는데 주어진 값을 소인수분해하면서 계속 값을 변형시켰더니 발생한 문제처럼 보인다.
정확히 실패한 케이스의 값을 확인할 수 없지만 최대한 단순한 방법으로 먼저 풀고 그 뒤 개선하는 절차를 익혀야 겠다.
'IT > Algorithm' 카테고리의 다른 글
| [programmers] 서울에서 김서방 찾기 (0) | 2022.07.08 |
|---|---|
| [programmers] 부족한 금액 계산하기 (0) | 2022.07.07 |
| [programmers] 평균 구하기 (0) | 2022.07.05 |
| [programmers] 하샤드 수 (0) | 2022.07.05 |
| [programmers] 핸드폰 번호 가리기 (0) | 2022.07.05 |