백준 4673 셀프 넘버 (Swift/Algorithm)

Swift로 PS 공부하기

프로그래밍 학습자 입장으로서 PS공부는 여러모로 도움이 많이 되는 것 같다. 문제를 풀면서 언어에 대해 몰랐던 부분을 좀 더 찾아보며 공부하게 되고 알고리즘에 대한 사고력도 키워진다. 무엇보다 책만 계속 보는 것보다는 훨씬 재미있는 활동이다. 아직 프로젝트를 시작하지 못한 나로서는 코딩 공부에 흥미를 더할 수 있는 것이 PS공부를 하는 것이다. 문제를 풀 때는 힘들지만 풀어냈을 때의 그 쾌감이란...

---

 

4673 셀프 넘버

우선 문제를 정리해보자

1. n이 주어졌을 때 n과 n의 각 자릿수를 더하는 함수가 존재한다 ex) d(75) = 75 + 7 + 5 = 87
2. 위 함수를 여러 번 사용해서 무한수열을 만들 수 있다 ex) 33, 39, 51, 57, 69...
3. n을 d(n)의 생성자라고 한다. 생성자가 없는 숫자는 셀프 넘버라고 한다.
4. 10000 이하의 셀프 넘버를 모두 출력하라

 

이 문제는 특이하게도 입력이 없고 출력만 존재했다. 그리고 출력하는 수 또한 정해져 있어서 값을 받을 필요 없이 내부적으로 계산만 잘해서 출력하면 되는 문제였다.

우선 문제를 보자마자 든 생각은 다음과 같았다

1. d(n) 함수를 구현해야 한다
2. 셀프 넘버를 어떻게 구하지?

눈앞이 막막했지만 하나하나 차근차근 풀어보기로 했다...

---

d(n) 함수 구현하기

우선 함수를 만들어내기 위해서 숫자가 주어졌을 때 각 자릿수에 해당하는 수를 얻어내는 법을 알아야 한다. 처음에는 String으로 바꿔서 잘라야 하나 생각했지만 그보다 훨씬 쉬운 방법을 찾아내서 정리해보았다.

첫 번째 자릿수 : ( 수 % 10 )
두 번째 자릿수 : ( 수 % 100 ) / 10
세 번째 자릿수 : ( 수 % 1000 ) / 100

% 는 나머지를 구하는 연산자이다.

예를 들어서 157이라는 수가 주어졌을 때 각 자릿수의 수를 구해보자

157 % 10 은 7이다
157 % 100 은 57이다 이 수를 10으로 나누면 5가 된다 (Int형이므로 소수점 뒤의 수는 자동으로 사라진다)
157 % 1000 은 157이다 이 수를 100으로 나누면 1이 된다

먼저 이 방식을 이해하고 아래 함수를 만들어보았다.

func selfNum(number: Int) -> (Int) {
    let range = String(number).count
    let result = number
    var tmp = 0

    for i in 1...range {
        let j = i - 1
        let add = (result % 10^^i) / (10^^j)

        tmp += add
    }

    return result + tmp
}

우선 number라는 매개변수로 Int를 받는다. 해당 Int의 크기를 String(number). count로 확인한다.
반복문을 통해 Int의 각 자릿수에 해당하는 숫자를 뽑아내어 add에 할당하고 tmp를 통해 모두 합산한다.
마지막으로 처음 Int값과 각 자릿수의 합인 tmp를 더하여 return 시켰다.

---

셀프 넘버 구해서 출력하기

문제의 셀프 넘버 구해서 출력하기는 고민을 참 많이 했다. 결론부터 이야기하자면 단순 무식한 방법으로 접근했다.

우선 10000으로 최댓값이 정해져 있으니 1부터 10000을 할당하는 배열을 생성한다. 그리고 앞서 만든 함수를 통해 셀프 넘버 중 가장 작은 값인 1을 대입한다. 그렇다면 1 2 4 8 16... 10000까지 셀프 넘버가 아닌 값들이 나오는데 이 값을 배열에서 제거한다.

셀프 넘버는 다른 생성자로부터 생성되지 않는다는 점을 생각해보자. 그렇게 했을 때 남은 값 중 가장 작은 값은 3이 된다. 마찬가지로 셀프 넘버이다. 이 셀프 넘버를 이용해서 또 값을 제거하고 다음 셀프 넘버를 함수에 대입한다... 이를 반복해서 가장 작은 값이 10000을 넘어갔을 때 함수를 종료했다.

var numArr = [Int](repeating: 0, count: 10000)

for i in 1...numArr.count{
    numArr[i - 1] = i
}

var counter = 1
numArr[0] = 10001

while(true) {
    guard counter < 10000 else {
        break
    }
    print(counter)
    
    while(true) {
        let index = selfNum(number: counter)

        guard index < 10000 else {
            break
        }
        
        numArr[index - 1] = 10001

        
        counter = index
    }
    
    counter = numArr.min()!
    numArr[counter - 1] = 10001
}

결론적으로 작동은 성공하기는 했다. 하지만...

128ms를 찍어버리는 기염을 토했다 Java로 문제를 푼 사람들과 비슷한 시간이 나왔다. Swift로 풀었다고 봤을 때 상당히 느린 시간이라고 생각한다. 단순 무식하게 배열의 값을 계속 수정하다 보니 이렇게 오랜 시간이 걸린 것으로 생각된다.

---

다른 사람들은 어떻게 풀었을까?

시간대가 이렇게 나오다 보니 다른 사람들의 알고리즘이 궁금해졌다 8ms대로 끊으신 아이디 kciter님의 소스 코드가 오픈되어있어서 공유해보았다.

func constructor(_ number: Int) -> Int {
  var n = number
  var sum = n
  while n != 0 {
    sum += n % 10
    n /= 10
  }
  return sum
}

var array = Array(repeating: true, count: 10001)
for index in 1...10000 {
  let number = constructor(index)
  if number <= 10000 {
    array[number] = false
  }
}
for index in 1...10000 {
  if array[index] == true {
    print(index)
  }
}

우선 코드 길이 수에 한번 놀랐다. 엄청나게 깔끔한 코드로 한눈에 봐도 알아보기 쉬웠다. 특히 Int배열이 아니라 Bool배열을 이용했다는 점이 새롭게 다가왔다. 어차피 index로 어떤 수인지 파악할 수 있으니 셀프 넘버가 아닌 수는 false처리를 해 줌으로써 간단하게 셀프 넘버와 그렇지 않은 수를 구별한 것이다.

함수 또한 변수의 수를 훨씬 줄여 깔끔하게 계산했고 변수 두 개로 반복문을 구성했는데 n이 0이 될 때까지 나머지를 구해서 쉽게 각 자릿수를 구하는 방법 또한 배울 수 있었다.

---

백준 문제를 풀면서 느끼는 것은 잘 풀리는 문제도 있고 조금 힘들게 푸는 문제들도 있지만 모두 풀었을 때 쾌감이 좋다는 것이다. 이는 프로그래밍 공부를 지속하게 하는 힘이 되어주는 것 같다. 그리고 다 풀고 나서 다른 사람들의 코드와 내 코드를 비교해보면서 새롭게 많은 것을 배울 수 있다는 점이 참 유익하다.

아직 갈 길이 멀다. 아직 30문제 정도밖에 풀지 못했지만 부족함이 많이 느껴진다. 언어 공부와 더불어서 알고리즘 책 또한 열심히 보고 공부해야겠다. 앞으로도 문제를 풀고 나서 블로그에 글을 써야겠다. 그러면서 한번 더 복기하는 시간을 가지고 성장의 계단을 한층 한층 올라가야겠다고 다짐한다.

혹시 지적할 부분이나 도움을 주고싶다면 언제나 댓글로 남겨주길바란다. 질문또한 있다면 남겨주었으면 좋겠다 같은 초보자의 입장으로서 함께 고민해보고싶다.

---