Kotlin 카카오 주차 요금 계산 - ConcurrentModificationException, HashMap, hashing
DoDoBest
·2024. 9. 4. 23:17
ConcurrentModificationException
https://school.programmers.co.kr/learn/courses/30/lessons/92341
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
자동차의 주차장 출입 누적 시간을 기록한 후, 비용을 계산해서 반환하면 되는 문제이다.
아래는 처음에 작성한 답안이다. 어떤 문제가 있을까?
/**
누적 주차 시간이 기본 시간 이하라면 기본 요금
누적 주차 시간이 기본 시간을 초과하면 초과한 시간에 대해 단위 시간 마다 단위 요금
초과한 시간이 단위 시간으로 나누어 떨어지지 않으면 올림
fees[0] : 기본 시간
fees[1] : 기본 요금
fees[2] : 단위 시간
fees[3] : 단위 요금
records : "시각 차량번호 내역" 공백으로 구분. 시각을 기준으로 오름차순
시각 : HH:MM -> 분 단위로 변환하기
차량번호 : 네 자리 문자열
내역 : IN, OUT
23:59까지 출차되지 않으면 23:59에 출차한 것으로 간주
차량 번호가 작은 자동차부터 청구할 주차 요금을 리턴
*/
class Solution {
private lateinit var fees: IntArray
fun solution(fees: IntArray, records: Array<String>): IntArray {
this.fees = fees
// 주차장에 주차된 차량의 정보를 기록한다.
val parking = hashMapOf<String, Int>()
// 주차장에 출입한 차량의 누적 시간 정보를 기록한다.
val accumulatedParkingTime = hashMapOf<String, Int>()
for (record in records) {
val (t, carNum, enterType) = record.split(" ")
val (h, m) = t.split(":").map { it.toInt() }
val time = h * 60 + m
if (enterType == "IN") {
parking[carNum] = time
} else {
accumulatedParkingTime[carNum] =
accumulatedParkingTime.getOrDefault(carNum, 0) + time - parking.remove(carNum)!!
}
}
// 입/출차 기록에 입차만 하고 출차한 기록이 없는 차량은 23:59에 출차한 것으로 처리한다.
for (carNum in parking.keys) {
accumulatedParkingTime[carNum] =
accumulatedParkingTime.getOrDefault(carNum, 0) + LAST_TIME - parking.remove(carNum)!!
}
val answer = IntArray(accumulatedParkingTime.keys.size)
// 차량의 당일 누적 주차 시간을 확인한 후 비용을 계산한다.
for ((idx, carNum) in accumulatedParkingTime.keys.sorted().withIndex()) {
answer[idx] = calc(accumulatedParkingTime[carNum]!!)
}
return answer
}
private fun calc(time: Int): Int {
if (time <= fees[0]) {
return fees[1]
}
val overTime = time - fees[0]
var sum = fees[1] + overTime / fees[2] * fees[3]
if (overTime % fees[2] != 0) {
sum += fees[3]
}
return sum
}
companion object {
private const val LAST_TIME = 23 * 60 + 59
}
}
fun main() {
val fees = intArrayOf(100, 1000, 10, 50)
val records = arrayOf("16:00 3961 IN", "16:00 0202 IN", "18:00 3961 OUT", "23:58 3961 IN")
val answer = Solution().solution(fees, records)
println(answer)
}
문제가 되는 부분은 출차 기록이 없는 차량을 처리할 때 발생한다. 위 코드를 실행하면 for 문에서 ConcurrentModificationException이 발생한다.
// 입/출차 기록에 입차만 하고 출차한 기록이 없는 차량은 23:59에 출차한 것으로 처리한다.
for (carNum in parking.keys) {
accumulatedParkingTime[carNum] =
accumulatedParkingTime.getOrDefault(carNum, 0) + LAST_TIME - parking.remove(carNum)!!
}
Exception in thread "main" java.util.ConcurrentModificationException at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1605) at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1628) at Solution.solution(code.kt:44) at CodeKt.main(code.kt:79) at CodeKt.main(code.kt)
문제가 발생한 부분을 따라가 보자. 처음에는 Iterator의 next 함수가 호출된다.
이것은 for .. in 이 Iterator를 이용해서 내부 원소를 탐색하기 때문이다.
https://dodobest.tistory.com/66
for .. in 은 무엇일까
학습하게 된 계기 코틀린 코루틴 책을 학습하다가 for문에 Channel class를 사용하는 코드를 보고, list도 아닌 class가 어떻게 원소를 반환하는지 궁금해졌다. suspend fun main(): Unit = coroutineScope { val channe
dodobest.tistory.com
nextNode에서 modCount와 expectedModCount가 일치하지 않으면 ConcurrentModificationException을 던지고 있다.
modCount는 HashMap에 추가, 삭제가 발생한 횟수를 나타내는 값이다.
expectedModCount는 Iterator가 생성되는 시점에 저장된 modCount 값이다.
즉, HashMap의 원소를 탐색하는 중, 새로운 원소가 추가되거나 삭제되면 exception이 발생한다.
fun main() {
val hashMap = hashMapOf(
1 to 1,
2 to 2,
3 to 3,
)
for ((idx, key) in hashMap.keys.withIndex()) {
if (idx == 1) {
// 0. 기존 원소를 변경하는 경우 - 아무 문제 없다
// hashMap[3] = 10
// 1. 새로운 원소를 추가하는 경우 - exception
// hashMap[4] = 4
// 2. 기존 원소를 삭제하는 경우 - exception
// hashMap.remove(3)
// 3. 기존 원소를 삭제하고, 새로운 원소를 추가하는 경우 - exception
hashMap.remove(3)
hashMap[4] = 4
}
println("$key : ${hashMap[key]}")
}
}
/**
* 1 : 1
* 2 : 2
* Exception in thread "main" java.util.ConcurrentModificationException
* at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1605)
* at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1628)
* at CodeKt.main(code.kt:86)
* at CodeKt.main(code.kt)
*/
기존 코드에서 hashMap을 iterate 하는 중 원소를 삭제했기 때문에 Exception이 발생한 것을 알 수 있다.
로직 상으로 정답을 구하는 과정에서 굳이 원소를 삭제하는 행위가 필요 없기 때문에 삭제 하지 않고 그냥 값을 꺼내 쓰도록 수정하면 exception이 발생하지 않는다.
// 입/출차 기록에 입차만 하고 출차한 기록이 없는 차량은 23:59에 출차한 것으로 처리한다.
for (carNum in parking.keys) {
accumulatedParkingTime[carNum] =
accumulatedParkingTime.getOrDefault(carNum, 0) + LAST_TIME - parking.remove(carNum)!!
}
수정된 코드는 다음과 같다.
class Solution {
private lateinit var fees: IntArray
fun solution(fees: IntArray, records: Array<String>): IntArray {
this.fees = fees
// 주차장에 주차된 차량의 정보를 기록한다.
val parking = hashMapOf<String, Int>()
// 주차장에 출입한 차량의 누적 시간 정보를 기록한다.
val accumulatedParkingTime = hashMapOf<String, Int>()
for (record in records) {
val (t, carNum, enterType) = record.split(" ")
val (h, m) = t.split(":").map { it.toInt() }
val time = h * 60 + m
if (enterType == "IN") {
parking[carNum] = time
} else {
accumulatedParkingTime[carNum] =
accumulatedParkingTime.getOrDefault(carNum, 0) + time - parking.remove(carNum)!!
}
}
// 입/출차 기록에 입차만 하고 출차한 기록이 없는 차량은 23:59에 출차한 것으로 처리한다.
for (carNum in parking.keys) {
accumulatedParkingTime[carNum] =
accumulatedParkingTime.getOrDefault(carNum, 0) + LAST_TIME - parking[carNum]!!
}
val answer = IntArray(accumulatedParkingTime.keys.size)
// 차량의 당일 누적 주차 시간을 확인한 후 비용을 계산한다.
for ((idx, carNum) in accumulatedParkingTime.keys.sorted().withIndex()) {
answer[idx] = calc(accumulatedParkingTime[carNum]!!)
}
return answer
}
private fun calc(time: Int): Int {
if (time <= fees[0]) {
return fees[1]
}
val overTime = time - fees[0]
var sum = fees[1] + overTime / fees[2] * fees[3]
if (overTime % fees[2] != 0) {
sum += fees[3]
}
return sum
}
companion object {
private const val LAST_TIME = 23 * 60 + 59
}
}
HashMap, Hashing
HashMap은 키와 값을 묶어서 하나의 데이터로 저장하는 Map의 특징과 많은 양의 데이터를 빠르게 검색하는 해싱(Hashing)의 특징을 가진다.
HashTable과 달리 HashMap은 Key와 Value로 null을 허용한다. HashTable은 컬렉션 프레임웍이 도입되면서 HashMap으로 대체되었으나 이전 소스와의 호환성을 위해 존재한다.
HashMap은 Key, value 쌍을 Entry class 1개로 관리한다.
해싱이란 해시함수를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다. 해시함수는 저장되어 있는 곳을 알려 주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.
해싱은 배열과 링크드 리스트의 조합으로 되어 있다.
저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그곳에 연결되어 있는 링크드 리스트에 저장하게 된다. 데이터를 검색하는 과정은 다음과 같다.
1. 검색하고자 하는 값의 키로 해시함수를 호출한다.
2. 해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 링크드 리스트를 찾는다.
3. 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.
링크드 리스트는 검색에 불리한 자료구조이기 때문에, 링크드 리스트의 크기는 작은 상태로 유지되어야 한다.
반면에 배열은 배열의 크기가 커져도, 원하는 요소가 몇 번째에 있는 지만 알면 아래의 공식에 의해서 빠르게 원하는 값을 찾을 수 있다.
배열의 인덱스가 n인 요소의 주소 = 배열의 시작주소 + type의 size * n
하나의 링크드 리스트에 최소한의 데이터만 저장되려면, 저장될 데이터의 크기를 고려해서 HashMap의 크기를 적절하게 지정해주어야 하고, 해시함수가 서로 다른 키에 대해서 중복된 해시코드를 최소한으로 반환해야 한다.
HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 Object 클래스에 정의된 hashCode()를 해시함수로 사용한다. hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일한 방법이다.
String 클래스의 경우 문자열의 내용으로 해시코드를 만들어내기 때문에, 서로 다른 String 인스턴스일지라도 같은 내용의 문자열을 가졌다면 hashCode()를 호출했을 때 같은 해시코드를 반환한다.
객체가 동일한지 비교할 때, equals()로 비교한 결과가 true인지와 hashCode()의 반환 값이 동일한지를 확인한다. 그래서 새로운 클래스를 정의할 때 equals를 오버라이딩한다면, hashCode도 같이 오버라이딩해서 equals()의 결과가 true이면 hashCode의 결과도 같도록 설정해야 한다.
그렇지 않으면 해싱을 구현한 컬렉션 클래스에서는 equals()의 호출 결과가 true지만 해시코드가 다른 두 객체를 서로 다른 것으로 인식하고 따로 저장한다.
equals()의 호출 결과가 false이고 해시코드가 같은 경우는 같은 링크드 리스트에 저장된 서로 다른 두 데이터가 된다.
'코딩테스트' 카테고리의 다른 글
| 리트코드 994 Rotting Oranges - Kotlin 타입에 따른 시간 단축 팁 (0) | 2024.11.28 |
|---|---|
| 프로그래머스 모음사전 Kotlin (0) | 2024.04.25 |
| 프로그래머스 2개 이하로 다른 비트 Kotlin (0) | 2024.04.25 |
| Leetcode 42. Trapping Rain Water (0) | 2024.04.12 |
| 프로그래머스 시간 측정 오류와 H-Index 문제 (0) | 2024.04.09 |
