TIL 15일차 (피보나치 수 - Kotlin | 계산기 구현 과제 피드백 반영)

코드카타

 

피보나치 수

 

문제

 

n은 2 ~ 100,000 범위에 해당하는 값이라고 언급되어 있으므로

피보나치 수를 구하는 함수에서 n이  0인 경우는 고려하지 않아도 되며.

시간 복잡도를 고려하여 피보나치 함수를 짜야한다.

 

 

재귀함수 이용

class Solution {
    fun solution(n: Int): Int {

        fun fibo(n: Int): Int {
            if (n == 1 || n == 2) return 1
            else return fibo(n - 1) + fibo(n - 2)
        }

        return fibo(n) % 1234567
    }
}

피보나치 수열을 재귀를 사용해서 구하게 되면

각 호출마다 fibo(n-1)과 fibo(n-2)을 호출하기 때문에

시간 복잡도는 O(n^2)로 매우 비효율적이게 된다.

 

 

동적 프로그래밍 이용

class Solution {
    fun solution(n: Int): Int {

        fun fibo(n: Int): Int {
            val fib = mutableListOf(0, 1) // [fibo(0), fibo(1)]
            (2..n).forEach{fib.add((fib[it-1] + fib[it-2]) % 1234567)}
            return fib[n]
        }

        return fibo(n)
    }
}

fibo(0)과 fibo(1)의 값을 요소로 가지는 가변형 리스트를 선언한다.

리스트 값을 참조해 2 ~ n 범위의 fibo(n)의 결과를 가변형 리스트에 저장하는

메모이제이션 방식으로 피보나치 수를 구하여 시간복잡도를 O(n)으로 줄였다.

 

해당 함수는 메모이제이션을 진행한 리스트의 n번지 값을 반환하므로

% 1234567 연산은 리스트에 fibo(n)값을 더할 때마다 진행한다.

 

 

 몰랐던 사실

val fib = mutableListOf(0, 1)

MutableList는 val로 선언해도 리스트 자체의 변경이 가능한 컬렉션이다.

 

---

 

계산기 과제 풀이 확인

 

LV 3

 

구현 기능

사칙연산 클래스들을 만들어 Cacluator와 상속으로 관계 맺기

 

 

잘못된 부분

클래스를 구현할 때 상속을 포함하지 않았다.

 

 

풀이

open class Calculator {
    open fun operate(num1: Int, num2: Int){}
}

class AddOperation: Calculator() {
    override fun operate(num1: Int, num2: Int) {
        val result = num1 + num2
        println("결과값은: ${result}입니다. ")
    }
}

class SubstractOperation: Calculator() {
    override fun operate(num1: Int, num2: Int) {
        val result = num2 - num2
        println("결과값은: ${result}입니다. ")
    }
}

class DivideOperation: Calculator() {
    override fun operate(num1: Int, num2: Int) {
        val result = num2 / num1
        println("결과값은: ${result}입니다. ")
    }
}

class MultiplyOperation: Calculator() {
    override fun operate(num1: Int, num2: Int) {
        val result = num1 * num2
        println("결과값은: ${result}입니다. ")
    }
}

fun main() {
    val addCalc = AddOperation()
    val minusCalc = SubstractOperation()
    val multipleCalc = MultiplyOperation()
    val divideCalc = DivideOperation()

    addCalc.operate(10, 20)
    minusCalc.operate(20, 10)
    multipleCalc.operate(10, 20)
    divideCalc.operate(20, 10)
}

각각의 사칙연산 클래스들은 계산기 클래스를 상속하여

계산기 클래스의 operate 함수를 오버라이딩하여 구현한다.

 

메인에서 각 클래스의 인스턴스를 불러온 뒤 operate함수를 호출한다.

 

 

 

LV 4

 

구현 기능

사칙 연산 클래스들을 추상화하고

Calculator 클래스의 내부 코드를 변경한다.

 

 

잘못된 부분

의존성 주입을 클래스가 아닌 클래스의 메소드에 진행하였다.

 

 

풀이

class Calculator(private val operator: AbstractOperation) {
    fun operate(num1: Int, num2: Int): Double {
        return operator.operate(num1, num2)
    }
}

abstract class AbstractOperation {
    abstract fun operate(num1: Int, num2: Int): Double
}

class AddOperation: AbstractOperation() {
    override fun operate(num1: Int, num2: Int): Double = (num1 + num2).toDouble()
}

class SubstractOperation: AbstractOperation() {
    override fun operate(num1: Int, num2: Int): Double = (num1 - num2).toDouble()
}

class MultiplyOperation: AbstractOperation() {
    override fun operate(num1: Int, num2: Int): Double = (num1 * num2).toDouble()
}

class DivideOperation: AbstractOperation() {
    override fun operate(num1: Int, num2: Int): Double {
        require(num2 != 0) {
            ArithmeticException("Divide by Zero")
        }
        return (num1 / num2).toDouble()
    }
}

fun main() {
    val addCalc = Calculator(AddOperation())
    println("10더하기 20 결과는 : ${addCalc.operate(10, 20)} 입니다")

    val minusCalc = Calculator(SubstractOperation())
    println("20빼기 10 결과는 : ${minusCalc.operate(20, 10)} 입니다")

    val multipleCalc = Calculator(MultiplyOperation())
    println("10곱하기 20 결과는 : ${multipleCalc.operate(10, 20)} 입니다")

    val divideCalc = Calculator(DivideOperation())
    println("20나누기 10 결과는 : ${divideCalc.operate(20, 10)} 입니다")
}

main에서 각 연산클래스의 인스턴스를 생성 후 계산기 클래스에 의존성을 주입해야한다.

 

 

 

LV 5

 

구현 기능

연산자 우선순위를 고려해 연산 진행하기

 

 

잘못된 부분

잘못된 수식이 입력되었을 때의 예외처리를 진행하지 않았다.

 

 

에러 종류 찾기

 

올바르지 않은 수식을 입력했을 때 에러는

"IndexOutOfBoundsException"에 해당한다.

 

 

버튼 이벤트 로직 수정

fun onClick(view: View) {
        val button = view as Button
        val buttonText = button.text.toString()
        val expressionText = expression.text.toString()
		
        // 다른 버튼 텍스트 동작은 생략함
        when (buttonText) {
            "=" -> {
                if (expressionText.isNotEmpty()) {
                    try {
                        val res = calculator.calculate(expressionText)
                        result.text = "= " + res.toString()
                    } catch (e: IndexOutOfBoundsException) {
                        Toast.makeText(this, "올바르지 않은 수식입니다.", Toast.LENGTH_SHORT).show()
                        expression.text = ""
                    }
                }
            }
        }
    }

계산 결과를 출력하는 버튼을 누를 때 실행하는 로직에서 예외처리를 진행했다.

올바르지 않은 수식을 입력하면 토스트메시지를 띄우고 입력한 수식을 지운다.