15725번: 다항함수의 미분

문제 출처 : https://www.acmicpc.net/problem/15725

 

언어 : Kotlin

 

문제 설명 :

다항식(polynomial)은 문자의 거듭제곱의 상수 배들의 합을 표현하는 수식이다. 예를 들어 x2 - 2x + 3 같은 식을 의미한다. 그 중 변수가 하나인 것을 일변수 다항식이라고 하고 보통 다음과 같이 표현한다.

f(x) = anxn + an-1xn-1 + ... + a2x2 + a1x + a0

최대 일차 일변수 다항식이 주어졌을 때 그 함수를 미분한 결과를 출력하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 최대 일차 일변수 다항식이 주어진다. 항의 개수는 최대 2개이고, 변수는 항상 x로 주어지며, 각 항은 공백 문자로 구분되지 않는다. 주어지는 계수와 상수의 절댓값은 10,000을 넘지 않는 정수이다. 단, 계수의 절댓값이 1인 경우에는 계수를 생략한다. 차수가 같은 항은 한 번만 주어진다.

다항식은 차수가 큰 것부터 작아지는 순서대로 주어진다.

 

출력 :

주어진 일변수 다항식을 미분한 결과를 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
6x-6	6

 

풀이 : 

주어진 input 값(다항식 문자열)을 순회하며 +와 - 문자를 기준으로 항을 분리하고 부호를 추적한다.

이후 각 항을 순회하며 x를 포함하고 있는 계수를 계산한다.

 

x와 -x는 문제에서 말한대로 계수가 절댓값 1이기 때문에 1이 생략되어있다.

이를 1와 -1로 다시 처리하고, 다른 항의 x는 제거한다. 남은 문자열을 정수로 변환해 계수로 추출한다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val polynomial = readLine()

    bw.write(differentiate(polynomial))
    bw.flush()
    bw.close()
}

fun differentiate(polynomial: String): String {
    val terms = mutableListOf<String>()
    var currentTerm = StringBuilder()
    var sign = 1

    for (char in polynomial) {
        when (char) {
            '+' -> {
                if (currentTerm.isNotEmpty()) terms += if (sign == -1) "-$currentTerm" else currentTerm.toString()
                currentTerm = StringBuilder()
                sign = 1
            }
            '-' -> {
                if (currentTerm.isNotEmpty()) terms += if (sign == -1) "-$currentTerm" else currentTerm.toString()
                currentTerm = StringBuilder()
                sign = -1
            }
            else -> currentTerm.append(char)
        }
    }
    if (currentTerm.isNotEmpty()) terms += if (sign == -1) "-$currentTerm" else currentTerm.toString()

    val result = mutableListOf<String>()
    for (term in terms) {
        if (term.contains("x")) {
            val coefficient = when (term) {
                "x" -> 1
                "-x" -> -1
                else -> term.replace("x", "").toInt()
            }
            val newCoefficient = coefficient * 1
            if (newCoefficient != 0) result.add(newCoefficient.toString())
        }
    }

    return if (result.isEmpty()) "0" else result.joinToString(" + ").replace(" + -", " - ")
}