[알고리즘] Swift 나머지가 1이 되는 수 찾기

문제 설명

자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다.

---

제한사항

• 3 ≤ n ≤ 1,000,000

---

입출력 예

n	result
10	3
12	11

---

입출력 예 설명

입출력 예 #1

• 10을 3으로 나눈 나머지가 1이고, 3보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 3을 return 해야 합니다.

입출력 예 #2

• 12를 11로 나눈 나머지가 1이고, 11보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 11을 return 해야 합니다.

---

풀이 과정1

1. for ~ in 구문을 사용해 값을 반복해서 넣어줄 수 있도록 한다.
2. 1부터 n까지의 수를 1씩 증가시키면서 x에 할당해 조건을 만족하는지 확인한다.
3. n을 x로 나눴을 때의 나머지가 1이 나오면 조건을 만족하는 것이므로 x값을 반환해준다.
4. 나머지가 1이 아니라면 0을 반환한다.

여기서 내가 쓸 데 없이 생각이 많았던 포인트!
조건을 만족하는 x 값들 중 가장 작은 자연수를 어떻게 뽑아낼 것인가?
하는 고민이었는데, 코드를 보면 알 수 있듯이
어차피 가장 작은 수부터 순서대로 1씩 더하면서 넣어주기 때문에
조건을 만족하는 순간 값을 반환해버리면
그 값이 나머지가 1이 되도록 하는 가장 작은 자연수가 된다!!
따라서 고민할 필요가 없는 문제였다 ~ :>

import Foundation

    func solution(_ n:Int) -> Int {
        for x in 1...n {
            if n % x == 1 {
                return x
            }
        }
        return 0
    }
/*
이건 플레이그라운드에서 출력값을 확인해보고 싶어서 적어봤다.
let result = solution(9)
print(result)
*/

---

풀이 과정2

근데 위 코드에서 놓친 부분이 있다.
바로 for in 구문에서 x에 할당할 수의 범위 부분이다.
범위를 1부터 n까지로 설정했는데,
자연수는 1로 나눴을 때 나머지가 무조건 0이 나오기 때문에
굳이 넣을 필요 없는 수가 된다!
그래서 범위를 2부터 n까지로 수정해주었다.

---

Solution

import Foundation

    func solution(_ n:Int) -> Int {
        for x in 2...n {
            if n % x == 1 {
                return x
            }
        }
        return 0
    }

---

Another Solution

다른 풀이 보니까 while 구문 사용해서도 풀었길래 한 번 공부해보았다!

While 구문?
특정 조건을 만족하는 동안 내부 로직을 반복해서 수행해주는 구문이다.

1. 변수 x 만들어준다. 초기값은 2 (2로 시작하는 이유는 풀이과정2 참고)
2. n을 x로 나눴을 때 나머지가 1이 아닐 경우 x에 1을 더해 할당해주는 로직을 반복하고
3. 나머지가 1이 나올 경우 x 값을 반환하도록 한다.

import Foundation

func sol(_ n:Int) -> Int {
    var x = 2
    while n % x != 1 {
        x += 1
        }
    return x
    }

---

느낀점

분명 간단한 문제였는데!!!! 혼자 생각이 많아서 헤맸다.
그래도 길을 찾아 다행이다. 사실 GPT 친구의 도움을 좀 받았다.
GPT 친구 아니었으면 범위 설정에서 놓친 부분 있는지 몰랐을 것 같다.
스스로 놓친 부분 없이 할 수 있을 때까지 더 열심히 해보자 으쌰 :> !