[BOJ][Kotlin]14928번 풀이

상당히 오랜만에 찾아뵙습니다. 몇 번 바쁘다고 글 쓰는 걸 미루니까 임시저장만 계속 늘어가고 게시를 못하고 있네요. 최근에는 여전히 진행 중인 부트캠프와 함께 코틀린 공부를 병행하고 있습니다. 사실 부트캠프의 커리큘럼과는 상관이 없는 부분인데, 로그인 시스템이 무조건 모바일 인증을 해야 하는 시스템이라 너무 귀찮아서 자동 로그인 매크로를 만들어 보려고 혼자서 이것저것 하다가 어차피 코틀린은 자바랑 아귀가 맞는 부분이 있으니까 까짓 거 코틀린 공부도 시작하자 하는 마음에 조금씩 하고 있습니다. 무슨 책이 좋은지, 어떤 강의가 좋은지 본격적으로 할 수 없는 입장이기도 하고 어차피 결국 프로그래밍은 직접 하는 것만이 성장에 영향을 미치기 때문에 코틀린으로 할 수 있는 무언가 들을 찾아서 하고 있습니다. 이번 포스팅에서 진행할 문제 풀이도 그 '무언가'에 해당하고요.

 

문제 풀이에 앞서,

해당 문제를 설명드리기 위해서 자료를 찾다 보니 이게 꽤나 딥한 컴퓨터 공학적인 지식이 필요하다는 걸 느꼈습니다. 왜 나눗셈 연산이 느린지, 나머지 연산의 로직은 어떻게 되는지, 왜 나머지 연산을 이렇게 진행해도 되는지, 그럼 애초에 나머지 연산의 로직을 이렇게 짜 놓지 않는 이유는 뭔지 등등 다 적지 못할 정도로 방대한 양의 컴퓨터 지식이 연산 로직의 근간에 존재하고 있었습니다. 그걸 모조리 정리하고 있다가는 이 문제의 포스팅을 절대 올릴 수 없겠다는 생각이 들어서 노선을 틀었습니다(비전공자의 슬픔...). 따라서 일반적인 나눗셈 연산으로는 해당 문제를 풀 수 없는 이유는 '속도가 느리기 때문에' 라고 받아들인 채 진행해주시면 감사할 것 같습니다. 이유가 궁금하시다면 나눗셈 연산이 느린 이유, 나눗셈 연산의 로직, ALU, 나머지 연산 등의 검색어를 통해 이유를 찾아보실 수 있습니다(해당 내용들은 저도 포스팅을 게시하려고 합니다만... 시간이 얼마나 걸릴지 예상이 안되네요).

 

https://www.acmicpc.net/problem/14928

14928번: 큰 수 (BIG)

 

문제만 읽어봤을 때는 상당히 간단하게 구현이 가능할 것 같습니다. 티어도 브론즈 5니까 말이죠. 간단하게 kotlin으로 짜 보면 이렇게 됩니다.

import java.math.BigInteger
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    var n = sc.nextBigInteger()
    val m = BigInteger("20000303")

    println("${n.mod(m)}")
}

하지만 실제로 제출을 했을 때는 시간 초과로 실패하게 됩니다. Scanner라서 그런가 싶어서 BufferedReader로 바꾸더라도 마찬가지입니다. 왜 그럴까요?(현재 해당 내용 관련해서 컴퓨터 연산에 대한 글을 작성 중에 있습니다. 빠른 시일 내에 해당 내용을 보여드릴 수 있도록 하겠습니다). 

 

일단 기본으로 제공되는 나머지 연산이 너무 느려서 못쓴다라는 사실은 알겠는데 그럼 어떻게 해야 이 문제를 풀 수 있을까요? 간단하게 말하자면 연산 자체가 딱히 달라지는 것은 없습니다. 다만 이런 컴퓨터 산술 연산의 경우 입력되는 숫자가 클수록 연산 시간이 엄청나게 늘어나는 특징이 있습니다(이 문제의 최대 입력값은 $ 10 ^ {10 ^ 6} $ 으로 길이가 백만정도 되니 상당히 시간이 오래걸리겠죠). 따라서 우리는 큰 숫자를 작은 수로 바꿔서 연산을 반복하는 방법을 사용해볼 겁니다.

 

 

오랜만에 보는 나눗셈 방법이죠? 사실 중학교만 들어가도 거의 다 분수로 처리를 하기 시작하니까 이런 식으로 나눗셈을 하는 일이 거의 없는데요. 그래도 이 문제에 한해서 이해가 좀 잘 될 것 같아 작성을 해봤습니다. 사실 뭐 이런 식으로 길게 적지만 않을 뿐이지 나눗셈이란 게 바뀐 건 아니니까요.

 

먼저 나눗셈이란 피제수(나누어지는 수, 여기서는 12345)를 제수(나누는 수, 여기서는 7)로 나누어 몫과 나머지로 나타내는 연산을 의미합니다. 나눗셈이 어떻게 되는지 잘 보고 있으면 맨 앞에서부터 하나씩 피제수의 자릿수에 제수로 나눗셈을 진행하고 몫은 위에, 나머지는 가로 실선을 긋고 아래에 작성한 다음 그다음 자리의 수를 가져와서 나머지에 붙인 다음 다시 제수로 나눗셈을 진행하는 것을 쭉 반복하는 작업입니다. 그렇게 작업을 쭉 반복해서 나아가서 마지막에 남는 나머지가 사실 맨 처음의 피제수를 제수로 나눈 나머지와 같은 것이죠. 해당 내용을 코드로 적어보면 다음과 같습니다.

 

import java.util.*

fun main() {
    val sc = Scanner(System.`in`)
    var n = sc.next()
    val m:Int = 20000303
    var remain = "0"
    var tmp:Int
    
    //참고로 kotlin for loop는 맨 마지막수도 포함(인덱스는 0부터 시작인데), 그래서 -1

    for (i in 0..n.length-1) { 
        remain += n[i]
        tmp = remain.toInt() % m
        remain = tmp.toString()
    }
    println(remain)
}

 

아무래도 아직 제가 코틀린을 자유자재로 쓰는 정도가 아니다 보니 코드가 약간 비효율적일 수도 있습니다만 최대한 자세히 짜려고 노력해봤습니다. for 반복문을 보시면 입력 n(피제수)에 인덱스로 접근해서 한 자리씩 가져온 다음 나머지에 붙이고 나눗셈을 진행하는 과정이 들어있습니다. 이런 식으로 컴퓨터에 나머지 연산을 아예 맡기는 게 아니라 우리가 손으로 나눗셈을 하듯이 구현을 해주는 코드입니다.

 

이렇게 아주 큰 수의 나눗셈을 그냥 산술 연산자로 연산을 맡기는 것보다 작은 수의 나눗셈 여러 번으로 바꾸는 게 for loop를 쓰더라도 훨씬 빠른 것을 알 수 있었습니다. 사실 이 풀이를 작성하면서 그럼 왜 기본적인 로직을 이 형태로 짜 놓지 않았을까 하는 의구심이 들었습니다만, 이 내용은 다음에 다른 포스팅에서 한 번 알아보기로 하고 이번 포스팅은 여기서 마칠까 합니다. 개인적으로 python만 내내 쓰다가 kotlin으로 이런 코드를 짜 보면 상당히 즐겁습니다. python이 정말 사용자의 편의를 많이 봐주는구나 싶기도 하고요. 얼마 전에 3.11 버전이 업데이트되면서 상당히 코드 실행 속도가 빨라졌다고 들었는데 4 버전이 나올 때쯤이면 python이 느린 언어라는 꼬리표를 뗄 수 있을지도 모르겠습니다.