[Swift] 백준 4673번 셀프 넘버

문제 출처: 백준 4673번 셀프 넘버

문제

---

풀이

---

처음에 이해가 잘 가지 않던 문제였는데요… 문제를 잘 읽어보시면 생각보다 쉽게 답을 구하실 수 있습니다.
셀프 넘버를 출력하는 문제인데 여기서 설명하는 셀프 넘버는 “생성자가 없는 숫자”를 말합니다.
그래서 저 같은 경우 10000번의 반복문을 실행해 각 수의 생성자가 있는지 없는지 판단하여 풀었습니다.

/// 반복문을 실행할 횟수
let N = 10000
/// 1부터 10000까지 셀프넘버인지 체크하는 배열
/// 1부터 연산하기 위해 길이를 10001으로 설정
var arr = Array(repeating: false, count: N + 1)

/// d(n)을 구하는 함수
func selfNumber(n : Int) -> Int {
  var num = n
  var sum = num
    
  while true {
    if num == 0 {
      break
    }
    // 입력받은 1의자리 더하기
    sum += num % 10
    // 자리수 감소
    num = num / 10
  }

  return sum
}

for i in 1..<N {
  let idx = selfNumber(n: i)
  
  if idx <= N {
    // idx에 해당하는 숫자는 생성자가 있으므로 d(n) -> 셀프 넘버 X
    arr[idx] = true
  }
}

// 정답 출력
for i in 1..<N {
  // arr[i]가 true면 생성자 있음(셀프 넘버 X), false면 생성자 없음(셀프 넘버 O)
  if !arr[i] {
    print(i)
  }
}

1. 반복문 실행할 횟수 N과 각 수가 셀프 넘버인지 체크할 Bool 배열을 생성합니다.
2. 1부터 생성자를 구해 해당 index에 해당하는 요소를 true로 변경합니다.
   • selfNumber: 자신의 값을 sum에 저장한 후 각 자릿수를 sum에 합산합니다.
3. 정답을 출력합니다.

문제를 풀면서 10000까지 전부 반복문을 실행하는 게 비효율적이라는 생각이 들어 규칙을 찾아보려 했으나 시간이 생각보다 짧게 나와 포기했습니다…

이렇게 풀 경우 메모리: 69096 KB, 시간: 8 ms 결과가 나오게 됩니다.