[내일배움캠프][TIL] 23.12.01 (금) - 명예의 전당, 계산기 만들기 Lv3 완성본
1. 코드카타
오늘 푼 알고리즘 문제는 '명예의 전당' 이다.
| 명예의 전당 |
 |
 |
이 문제의 매커니즘은 다음과 같다.
- k일 까지는 명예의 전당에 score가 높은 점수 순으로 차곡차곡 쌓인다.
- 그 다음날부터는 그 날의 score가 명예의 전당 최하점보다 높으면 명예의 전당에 있던 최하점은 밀려나고, 그 score가 명예의 전당에 새롭게 등재된다.
- 이 때, 1일부터 마지막날까지의 최하점을 모두 return하기
그렇다면 어떻게 코드를 짜야 할까?
1일부터 k일 까지는 어차피 차곡차곡 쌓이므로 별다른 처리가 필요하지 않다.
고로 다음과 같이 적을 수 있다.
for (i in 0 until k) {
hallOfFame += score[i]
hallOfFame.sortDescending()
answer += hallOfFame[i]
}참고로 hallOfFame은 미리 intArray형으로 변수선언했다.
그 날의 score를 hallOfFame에 저장해두고, 그걸 내림차순으로 정렬한 뒤에 맨 끝 번호를 answer에 저장.
문제는 이제 그 다음날부터 마지막날까지.
여기서부터는 hallOfFame에 있는 최하점이 score보다 낮으면 더 이상 필요가 없기 때문에 제거해야 한다.
이걸 실현시키기 위해서 여러가지 방법을 생각해보고 적용시켜봤지만 알 수 없는 오류들이 떴고(나중에야 안 사실이지만, 맨 처음 코드를 잘못 작성해서 생긴 오류더라) 이게 안 되면 뭐 어떻게 하지 하다가 문득 이런 생각이 들었다.
굳이 제거할 필요가 있나?
모든 숫자를 다 받아서 정렬한 다음에 k번째 점수를 저장하면 필터링해서 최하점을 저장하는 것과 똑같은 것이 아닌가?
여기서 아이디어를 얻어서 다음과 같은 코드를 짰다.
for (j in k until score.size) {
hallOfFame += score[j]
hallOfFame.sortDescending()
answer += hallOfFame[k-1]
}
그리고 이를 종합해 만든 코드는 다음과 같다.
class Solution {
fun solution(k: Int, score: IntArray): IntArray {
var answer: IntArray = intArrayOf()
var hallOfFame: IntArray = intArrayOf()
for (i in 0 until k) {
hallOfFame += score[i]
hallOfFame.sortDescending()
answer += hallOfFame[i]
}
for (j in k until score.size) {
hallOfFame += score[j]
hallOfFame.sortDescending()
answer += hallOfFame[k-1]
}
return answer
}
}
이렇게 코드를 짜고 제출을 하니 이럴수가.
시간 초과가 떴다.
틀렸다는 이야기는 안 했으니 코드 자체는 맞는데 위의 과정들이 시간을 너무 오래 잡아먹었다는 이야기였다.
이걸 어떻게 간소화시키지?
혹시나 hallOfFame에 쓸데없이 너무 많은 요소들을 집어넣었나?
그래서 아까 필터링했던 방법 중에 하나를 써먹기로 했다.
for (j in k until score.size) {
if (score[j] > hallOfFame[k-1]) hallOfFame[k-1] = score[j]
hallOfFame.sortDescending()
answer += hallOfFame[k-1]
}값을 비교하여 score가 최하점보다 높으면 score를 hallOfFame[k-1]에 대입시키는 것.
이렇게 하면 이전에 hallOfFame에 쓸데없는 수들이 들어갔던 것에 비하면 수를 줄일 수 있으니 간소화되었다.
하지만, 이것 역시 시간초과가 떴다.
흠… 설마 for문이 너무 많나?
이전에 강사님께서 말하시기로 for문을 남용해도 작업 시간이 오래 걸린다고 하셨다.
지금 for문은 2개.
이걸 하나로 합쳐봤다.
for (i in 0 until score.size) {
hallOfFame += score[i]
hallOfFame.sortDescending()
if (k > i) answer += hallOfFame[i]
else answer += hallOfFame[k-1]
}
정렬은 기존과 똑같지만, k번째 이전에는 맨 마지막 숫자를 return하고 그 다음부터는 k번째 숫자를 return하는 식으로 간소화하였다.
그리고 마침내 통과.
혹시나 했지만, 시간 초과의 원인은 바로 for문 때문이었다.
그리하여 최종 완성된 코드는 다음과 같다.
class Solution {
fun solution(k: Int, score: IntArray): IntArray {
var answer: IntArray = intArrayOf()
var hallOfFame: IntArray = intArrayOf()
for (i in 0 until score.size) {
hallOfFame += score[i]
hallOfFame.sortDescending()
if (k > i) answer += hallOfFame[i]
else answer += hallOfFame[k-1]
}
return answer
}
}
오늘의 교훈 : for문을 줄일 수 있으면 최대한 간결하게 만들 것.
2. Kotlin 문법 기초 과제 - 계산기 만들기 Lv3 최종
오늘 계산기 해설 강의가 올라왔었고, 뭐가 잘못됐는지 알아보기 위해 차근차근 시청했다.
그런데 그 해설 강의는 그 위의 단계인 Lv4 기준으로 해설해서 Lv3는 그걸 바탕으로 내가 알아서 수정해야 했다.
그렇게 완성된 Lv3 계산기 코드 전문이다.
class AddOperation {
fun operate (num1: Int, num2: Int) : Double = (num1 + num2).toDouble()
}
class SubstractOpeation {
fun operate (num1: Int, num2: Int) : Double = (num1 - num2).toDouble()
}
class MultiplyOperation {
fun operate (num1: Int, num2: Int) : Double = (num1 * num2).toDouble()
}
class DivideOperation {
fun operate (num1: Int, num2: Int) : Double = (num1 / num2).toDouble()
}
먼저 각 연산을 담당하는 연산 클래스.
대략적인 구성은 어제 처음 만든 것과 크게 차이가 없는데 두 가지 차이점이 있다.
하나는 Double형으로 변환시켰다는 것. (이건 어차피 num 받는 게 Int형인데 왜 Double형으로 변환했냐 하겠지만 추후에 num을 Double형으로 바꿀 수도 있으니까….)
그리고 제일 큰 차이점은 모든 연산 클래스의 함수명이 통일되었다는 것.
이러면 나중에 어떻게 구분하냐 할 텐데 그 다음 Calculator 클래스를 보면 알 수 있다.
class Calculator {
fun addOperation (oper: AddOperation, num1: Int, num2: Int): Double {
return oper.operate(num1, num2)
}
fun subOperation (oper: SubstractOpeation, num1: Int, num2: Int): Double {
return oper.operate(num1, num2)
}
fun mulOperation (oper: MultiplyOperation, num1: Int, num2: Int): Double {
return oper.operate(num1, num2)
}
fun divOperation (oper: DivideOperation, num1: Int, num2: Int): Double {
return oper.operate(num1, num2)
}
}
각 연산 함수를 정의할 때 들어가는 매개변수에 각 클래스 객체를 포함시켰다.
그리고는 객체 뒤에 operate 함수를 붙여서 return시켰다.
당연히 이걸 완벽히 이해해서 적지는 않았고 강의 영상에 이거 비스무리하게 적은 것이 있길래 혹시? 싶어서 넣어봤다.
그리고 대망의 main 함수.
fun main() {
var num1 = readLine()!!.toInt()
var num2 = readLine()!!.toInt()
val calc = Calculator()
println("어떤 연산자를 사용하시겠습니까?")
println("[1] 덧셈 [2] 뺄셈 [3] 곱셈 [4] 나눗셈")
var operator = readLine()!!.toInt()
if (operator == 1) {
println("덧셈 결과 ${calc.addOperation(AddOperation(), num1, num2)} 입니다.")
}
else if (operator == 2) {
println("뺄셈 결과 ${calc.subOperation(SubstractOpeation(), num1, num2)} 입니다.")
}
else if (operator == 3) {
println("곱셈 결과 ${calc.mulOperation(MultiplyOperation(), num1, num2)} 입니다.")
}
else if (operator == 4) {
println("나눗셈 결과 ${calc.divOperation(DivideOperation(), num1, num2)} 입니다.")
}
else {
println("계산기를 실행할 수 없습니다.")
}
}
역시나 달라진 것은 크게 없고 calc를 정의할 때 Calculator 클래스 () 안의 내용을 비운 것이 전부이다.
이렇게 해서 Lv3 계산기까지 완성되었다.
P.S) Lv4 계산기는 강의를 봐도 경이로움의 연속이라서 따로 만들지는 않고 어떤 원리로 이렇게 적어도 돌아가는지 강의를 여러번 보면서 이해하기로 했다.
참고로 Lv4의 내용은 다음과 같다.
- Lv4 (선택) : AddOperation(더하기), SubtractOperation(빼기), MultiplyOperation(곱하기), DivideOperation(나누기) 연산 클래스들을 AbstractOperation라는 클래스명으로 만들어 사용하여 추상화하고 Calculator 클래스의 내부 코드를 변경하기
추상 클래스를 보면서 느낀 Lv3 계산기와의 차이점 중 하나는 Calculator에 저런 식으로 길게 작성하지 않고 간단하게 적어도 연산 클래스와 추상 클래스가 상속 관계여서 알아서 계산이 된다는 점.
역시 알다가도 모르는 것이 코딩이다.