TIL 36일차 (롤케이크 자르기 - Kotlin | 챌린지반 2주차 과제)

코드카타

 

롤케이크 자르기

 

문제

 

롤케이크를 반으로 잘랐을 때 토핑 종류수가 같은 경우의 수를 구하는 문제이다.

 

 

입출력 예시

 

토핑개수가 아주 많을 때의 경우도 고려해야 한다.

 

 

시간초과 풀이

class Solution {
 	
    // 토핑 종류 수 반환 함수
    private fun tNum(list: List<Int>): Int {
        return list.groupBy { it }.keys.size
    }

    fun solution(topping: IntArray): Int {
        var res = 0
        
        // 토핑의 길이만큼 반복하여 롤케이크를 자른다
        for (i in topping.indices) {
            // 왼쪽 롤케이크의 초기 길이는 1이며, 1칸씩 증가한다.
            var left = tNum(topping.slice(0..i))
            // 오른쪽 롤케이크의 초기 길이는 토핑 길이이며, 1칸씩 감소한다.
            var right = tNum(topping.slice(i + 1..topping.size - 1))
            // 자른 롤케이크의 토핑 종류 수가 같은지 확인
            if (left == right) res++
        }

        return res
    }
}

해당로직은 각 인덱스마다 slice 함수를 사용하여 부분 배열을 만들고,

이 부분 배열을 그룹화하여 토핑의 개수를 세는 작업을 수행한다.

 

위 로직은 O(n^2)의 시간복잡도를 가지기에 

배열의 크기가 커질수록 성능 저하를 초래할 수 있게 된다.

 

 

해쉬 맵을 사용한 풀이

class Solution {
    fun solution(topping: IntArray): Int {
        var res = 0
		
        // 왼쪽과 오른쪽 롤케이크의 토핑 종류 수를 저장할 해쉬 맵
        val leftMap = mutableMapOf<Int, Int>()
        val rightMap = mutableMapOf<Int, Int>()
		
        // 왼쪽 맵에다 모든 토핑의 종류와 개수를 매핑한다.
        for (t in topping) {
            leftMap[t] = leftMap.getOrDefault(t, 0) + 1
        }
		
        // 모든 토핑을 순회
        for (t in topping) {
            // 오른쪽 해시맵을 업데이트하면서
            rightMap[t] = rightMap.getOrDefault(t, 0) + 1
			
            // 왼쪽 해시맵에서 값을 줄여 나가기
            if (leftMap[t] == 1) leftMap.remove(t)
            else leftMap[t] = leftMap[t]!! - 1
			
            //두 해시맵의 키 개수가 동일한지 체크
            if (rightMap.keys.size == leftMap.keys.size) res++
        }

        return res
    }
}

해시맵을 사용하여 각 롤케이크의 토핑 종류와 개수를 추적하는 방법을 썼다.

해당 로직에서 해쉬 맵을 반대로 바꿔도 문제없다.

 

 

회고

역시 해쉬 맵 쓰는 로직은 이해하기 쉽다.

 

앞으로 테스트케이스만을 보고 로직을 짜는 것이 아닌

코드의 효율성을 생각해서 로직을 짜야겠다.

 

---

 

챌린지반 2주차 과제

 

과제 내용

 

해당 전광판 사진을 보고 Kotlin으로 항공기 클래스 설계하기

 

 

1단계

import java.util.Date

data class Flight(
    val scheduledTime: Date, // 예정 시간
    val changedTime: Date, // 변경 시간
    val destination: String, // 도착지
    val airlineImg: Int, // 항공사 이미지
    val airlineCode: String, // 편명
    val checkinCounters: List<String>, // 체크인
    val gateNumber: Int, // 탑승구
    val flightStatus: String // 현황
)

전광판을 보고 기본적인 Flight객체를 만들어준다.

 

data class Flight(
    val id: String, // 항공편 ID
    val airplaneCode: String, // 비행기 코드
    // 그 외 생성자들
)

공항을 대용량 / 장기간 운영할때 Flight객체에 필요한 것들을 추가한다.

 

지속해서 운행을 하다보면 비행기가 겹치는 경우가 발생할 수 있다.

그 때 각각의 항공편을 식별하기 위해 클래스 내에 id 속성을 선언한다.

 

data class Flight(
    val coopFlightCodes: List<String>, // 협력 항공사 리스트
    val cratedTime: Date, // 항공편 생성시점
    val updatedTime: Date // 항공편 수정시점
    // 그 외 생성자들
)

전광판에 확인할 순 없지만 비행기 클래스에 필요한 속성들을 추가해준다.

 

 

2단계

open class Flight(
    val flightInfo: FlightInfo,
    val flightTimeInfo: FlightTimeInfo,
    val destination: String,
    val coopFlightCodes: List<String>,
    val checkin: List<String>,
    val gateNumber: Int,
    val flightStatus: String,
)

data class FlightInfo(
    val id: String,
    val airplaneCode: String,
    val airlineImg: Int,
    val airlineCode: String,
)

data class FlightTimeInfo(
    val scheduledTime: Date,
    val changedTime: Date,
    val cratedTime: Date,
    val updatedTime: Date
)

Flight 객체 안의 Data들을 비행기 정보와 비행기 시간 정보로 묶는다.

 

class DepartureFlight(
    flightInfo: FlightInfo,
    flightTimeInfo: FlightTimeInfo,
    coopFlightCodes: List<String>,
    flightStatus: String,
    val destination: String, // 도착지 추가
    val gateNumber: Int, // 탑승구 추가
    val checkinCounters: List<String> // 체크인 카운터 추가
) : Flight(
    flightInfo,
    flightTimeInfo,
    coopFlightCodes,
    flightStatus
)

class ArrivalFlight(
    flightInfo: FlightInfo,
    flightTimeInfo: FlightTimeInfo,
    coopFlightCodes: List<String>,
    flightStatus: String,
    val from: String, // 출발지 추가
) : Flight(
    flightInfo,
    flightTimeInfo,
    coopFlightCodes,
    flightStatus
)

비행기 클래스를 상속해 출발지와 도착지 전광판 클래스를 설계한다.