TIL231128 D07 문제풀이

오늘은 알고리즘 문제 몇 개를 다뤄보겠다.

약수의 합

정수를 입력받으면 모든 약수의 합을 반환하는 문제다.
for문을 돌려 나머지 0인 수를 더해주면 된다.

fun solution(n: Int): Int {
    var answer = n
    for (i in 1..n / 2) if (n % i == 0) answer += i
    return answer }

약간의 성능을 위해 n/2 까지만 for문을 돌렸다.

그런데 여기에 filter 라는 것을 적용할 수 있다.

fun solution(n: Int): Int =
    (1..n / 2).filter { n % it == 0 }.sum() + n

filter는 배열에서 조건에 해당하는 요소만 남기는 함수다. 이렇게 식을 깔끔하게 정리할 수 있다.

사실 여기에서 더 개선하려면, 약수는 쌍으로 나온다는 것을 이용해 제곱근까지만 돌리는 게 더 좋긴 하다.

나머지가 1이 되는 수 찾기

자연수를 입력받으면 나머지가 1이 되는 가장 작은 자연수를 반환하는 문제다.
역시 for문을 돌려 제일 처음 나머지가 1이 되는 수를 찾으면 된다.

fun solution(n: Int): Int {
    for (i in 2..n / 2) if (n % i == 1) return i
    return n - 1 }

역시 약간의 성능을 위해 n/2 까지 for문을 돌려주었다.

그런데 다른 사람의 풀이를 보니 first라는 것을 사용해 풀이한 것이 있었다.

fun solution(n: Int) =
    (1..n).first { n % it == 1 }

처음으로 조건에 맞는 요소를 찾아 반환하는 함수인 것이다. 구현하기 쉬운 로직이다보니 꼭 외울 만큼 중요하진 않아보이지만 코드를 깔끔하게 만들 수 있겠다.

x만큼 간격이 있는 n개의 숫자

정수 x와 자연수 n을 입력받으면 x부터 x씩 증가하는 n개의 배열을 반환하는 문제다. -2, 3을 입력받으면 [-2, -4, -6] 을 반환하는 것이다.

n개 배열을 만들고 각 요소 값을 넣으면 된다. 하지만 뭔가 초기화를 잘 할 수 있는 방법이 있지 않을까 찾아보았다. 역시 코틀린은 멋있는 방법을 준비해뒀다. 배열을 만들 때 사이즈와 함께 람다식을 받는데, 여기에서 인덱스를 인자로 사용할 수 있는 것이다.

fun solution(x: Int, n: Int): LongArray {
    val a = x.toLong()
    return LongArray(n) { i -> a * (i + 1) } }

이렇게 배열을 생성할 때 배열의 사이즈를 입력받고, 초기화 람다식을 입력받는다. 그리고 람다식에서는 인덱스 값을 인자로 받아서 위처럼 초기화를 할 수 있는 것이다.

나중에 scope 함수 공부하며 깨달은 건데, (함수에 따라서) 매개변수를 기본적으로 it 으로 사용할 수 있고, 이것의 이름을 i로 변경하여 사용한 것이었다. 아래처럼 사용할 수도 있다.

LongArray(n) { a * (it + 1) }

참고로

LongArray(n, { a * (it + 1) })

이렇게 람다식을 생성자 안에 쉼표로 넣을 수도 있는데, 오류는 아니지만 안드로이드 스튜디오에서 밖으로 빼라고 경고한다.

scope 함수 얘기가 나와서 한 문제 더 보겠다.

정수 내림차순으로 배치하기

자연수를 입력받으면 내림차순으로 정렬된 수를 반환하는 문제다.
String으로 바꿔 내림차순 정렬해 다시 숫자로 반환하면 된다.

fun solution(n: Long): Long {
    val s = n.toString().toCharArray()
    s.sortDescending()
    return String(s).toLong() }

처음엔 sort 하고 다시 reverse 를 해주었다가 sortDescending 의 존재를 알고 이를 사용해줬다.

다른 사람의 풀이를 보니 sortedArrayDescending() 을 사용해 한 줄로 풀이하기도 했던데, n이 80억까지라서 반환될 인스턴스를 만드는 것도 부담이 클 것 같아서 적용하지 않았다.

그랬는데, scope 함수를 알게 되었다. 따로 반환값을 생성하지 않고 this가 반환되는 apply, also를 적용하면 되는 것이다.

fun solution(n: Long): Long =
    String(n.toString().toCharArray().apply { sortDescending() }).toLong()

여기에서는 it을 적지 않아도 되는 apply를 사용했다.
scope 함수는 잘 사용하면 성능을 유지하면서도 코드를 매우 간결하게 만들 수 있다.

글을 작성하다가 문득 떠올랐는데, 카운팅 소트를 이용하면 가장 빠르겠다. CharArray도 거치지 않아도 되고.