[Coding Test] (2) 이전 문제 다시 풀어보기

블로그는 비영리로 운영되고 있습니다.

차후 저작권 문제가 발생할 시, 해당 글은 삭제하도록 하겠습니다.

---

 

class ExampleUnitTest {
    fun solution(N: Int, stages: IntArray): IntArray {
        // 결과를 담을 리스트 생성
        val result = ArrayList<Int>()

        // 각 스테이지별 실패율을 저장할 맵 생성
        val failMap = mutableMapOf<Int, Double>()

        // 각 스테이지별로 실패율 계산
        // 1부터 N(마지막 스테이지)까지 반복
        for (i in 1..N) {
            // 스테이지에 도달한 사람 수
            var tryCount = 0

            // 스테이지를 클리어 못한 사람 수
            var failCount = 0

            // stages 배열을 돌면서 도전자 수와 실패자 수 계산
            for (j in stages) {
                if (j >= i) {    // i스테이지에 도달했으면
                    tryCount++
                }
                if (j == i) {    // i스테이지를 클리어하지 못했으면
                    failCount++
                }
            }

            // 실패율 계산해서 맵에 저장
            if (tryCount == 0) {
                failMap[i] = 0.0
            } else {
                failMap[i] = failCount.toDouble() / tryCount
            }
        }

        // 실패율 높은 순으로 스테이지 번호 정렬
        while (failMap.isNotEmpty()) {
            var maxRate = -1.0
            var maxStage = 0

            // 현재 남은 스테이지 중 가장 실패율 높은 스테이지 찾기
            for ((stage, rate) in failMap) {
                if (rate > maxRate) {
                    maxRate = rate
                    maxStage = stage
                } else if (rate == maxRate && stage < maxStage) {
                    // 실패율이 같다면 작은 번호가 우선
                    maxStage = stage
                }
            }

            // 찾은 스테이지를 결과에 추가하고 맵에서 제거
            result.add(maxStage)
            failMap.remove(maxStage)
        }

        return result.toIntArray()
    }

    @Test
    fun main() {
        // 테스트
        val n1 = 5
        val stages1 = intArrayOf(2, 1, 2, 6, 2, 4, 3, 3)

        // 3, 4, 2, 1, 5
        println("결과1: ${solution(n1, stages1).contentToString()}")

        val n2 = 4
        val stages2 = intArrayOf(4, 4, 4, 4, 4)

        // 4, 1, 2, 3
        println("결과2: ${solution(n2, stages2).contentToString()}")
    }
}

결과1: [3, 4, 2, 1, 5]
결과2: [4, 1, 2, 3]

 

위에는 저번 코딩테스트에서 풀었던 문제입니다. 딱 기본적인 조건문, 반복문만 사용해서 풀었습니다.

먼저 문제를 풀기위해서 반드시 필요한 값을 알아보겠습니다.

• 전체 스테이지 갯수
• 사용자들이 현재 도전 중인 스테이지 배열
• 스테이지에 도달한 플에이어 수 (도전자 수)
• 스테이지를 클리어하지 못한 플레이어 수 (실패자 수)
• 실패율: 실패자 수 / 도전자 수

---

 

1. HashMap 사용

class ExampleUnitTest {
    fun newSolution(N: Int, stages: IntArray): IntArray {
        // 스테이지별 실패자 수
        val stageFailCount: IntArray = IntArray(N + 2) { 0 }
        for(failStage in stages) {
            stageFailCount[failStage]++
        }

        // 총 도전자 수
        var challengers = stages.size

        // 스테이지별 도전자 수
        val stageChallengerMap: HashMap<Int, Int> = hashMapOf()
        for(challengerStage in 1..N) {
            challengers -= stageFailCount[challengerStage]
            stageChallengerMap[challengerStage] = challengers
        }

        // 각 스테이지별 실패율 계산
        // 실패자 수 / 도전자 수
        val stageRateMap: HashMap<Int, Double> = hashMapOf()
        for(stageKey in stageChallengerMap.keys) {
            stageRateMap[stageKey] = stageFailCount[stageKey].toDouble() / stageChallengerMap[stageKey]!!.toDouble()
        }

        // 실패율이 높은 순서대로 정렬
        val sortRateMap = stageRateMap.toList().sortedByDescending { (stage, rate) -> rate }.toMap()

        return sortRateMap.keys.toIntArray()
    }

    @Test
    fun main() {
        // 테스트
        val n1 = 5
        val stages1 = intArrayOf(2, 1, 2, 6, 2, 4, 3, 3)

        // 3, 4, 2, 1, 5
        println("결과1: ${newSolution(n1, stages1).contentToString()}")

        val n2 = 4
        val stages2 = intArrayOf(4, 4, 4, 4, 4)

        // 4, 1, 2, 3
        println("결과2: ${newSolution(n2, stages2).contentToString()}")
    }
}

 

HashMap을 사용해서 풀어봤습니다. 막상 풀고보니, 도전자 수와 실패자 수를 따로 변수에 담을 필요가 없을 것 같아서 아래처럼 변경했습니다.

 

2. 실패율 계산 통합

fun newSolution2(N: Int, stages: IntArray): IntArray {
        // 스테이지별 실패자 수
        val stageFailCount: IntArray = IntArray(N + 2) { 0 }
        for(failStage in stages) {
            stageFailCount[failStage]++
        }

        // 총 도전자 수
        var challengers = stages.size

        // 스테이지별 실패율
        val stageRateMap: HashMap<Int, Double> = hashMapOf()
        for(stage in 1..N) {
            challengers -= stageFailCount[stage]
            stageRateMap[stage] = stageFailCount[stage].toDouble() / challengers.toDouble()
        }

        return stageRateMap
            .toList()
            .sortedByDescending { it.second }
            .toMap()
            .keys
            .toIntArray()
    }

 

 

3. ArrayList<Pair> 사용

fun newSolution3(N: Int, stages: IntArray): IntArray {
        // 스테이지별 실패자 수
        val stageFailCount: IntArray = IntArray(N + 2) { 0 }
        for(failStage in stages) {
            stageFailCount[failStage]++
        }

        // 총 도전자 수
        var challengers = stages.size

        // 스테이지별 실패율
        val stageRatePair: ArrayList<Pair<Int, Double>> = ArrayList()
        for(stage in 1..N) {
            challengers -= stageFailCount[stage]
            stageRatePair.add(Pair(stage, stageFailCount[stage].toDouble() / challengers.toDouble()))
        }

        return stageRatePair
            .sortedByDescending { it.second }
            .map { it.first }
            .toIntArray()
    }

 

---

이번 포스트는 여기서 마치겠습니다!

다음 포스트에서 프로그래머스 Lv.1을 다시 도전해보겠습니다~!