[swift] 백준 - 2231번: 분해합

2231번: 분해합

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

문제 설명

 

브루트포스 알고리즘에 관련한 문제로

여러 경우의 수를 대입하여

원하는 값을 구할 수 있다.

 

T란 숫자가 있고

T의 각 자릿수를 더해서

N이라는 값이 나온다면

T와 T의 각자리수들은 N의 분해합이라고 한다.

 

입력값으로 N이 주어졌을 때 T에 해당하는 최솟값을 구해야 한다.

만약 분해합이 없다면 0을 리턴한다.

 

---

 

나의 풀이

var input = readLine()!
var num = Int(input)!
var figure = input.map { $0 }.count * 9
var start = num-figure >= 0 ? num-figure : 0
var result = 0
for i in start...num {
    let temp = i
    let sum = String(temp).map { Int(String($0))! }.reduce(0,+) + temp
    if sum == num {
        result = temp
        break
    }
}
print(result)

 

0부터 백만까지 반복문을 돌려서

입력값의 분해합을 찾을 수 있겠지만

비효율적인 시간이 걸립니다.

 

그래서 반복문을 돌리기 위한 최소조건의 값을 찾아야 합니다.

그건 입력값의 자릿수에서 찾을 수 있었는데요

 

입력값이 256이라면

3 자릿수이기 때문에

각 자릿수마다 최대 9개의 숫자가 나오겠죠? (1~9)

0은 더하나 마나 상관없으니까요.

 

입력값 - 각자릿수 * 9를 시작으로

입력값까지 분해합을 찾기 위한 반복문을 돌렸습니다.

 

풀면서 마주쳤던 오류는

입력값이 반복시작값(입력값 - 각자릿수 * 9) 보다 작다면

음수가 되면서 map을 도는 과정에서 오류가 발생했습니다.

 

따라서 start값이 0보다 작다면 아예 0으로 명시했습니다.

 

---

 

참고할만한 풀이

let input = Int(readLine()!)!
var result = 0
for i in input-String(input).count*9...input {
	var num = i
	var sum = 0
	while num > 0 {
		sum += num%10
		num /= 10
	}

	if sum + i == input {
		result = i
		break
	}
}
print(result)

 

---