BOJ2309

문제

https://www.acmicpc.net/problem/2309

풀이

문제 해결 방법

첫번째로 9명의 난쟁이 중 가짜는 2명임을 알 수 있으므로 9C2 = 36가지 이므로 2중 for문을 사용해서 해결할 수 있는 문제다.
(난쟁이의 수가 터문이 없이 커진다면 다른 방법을 선택해야하는데, 그 경우는 아직 모르겠다. 댓글로 남겨주면 행복할 거 같습니다.)
순서도를 그려보게 되면

이와같은 방법으로 문제를 해결할 수 있다.

자료구조

두번째로 입력받은 9명의 난쟁이 키 데이터를 어떻게 보관할 것인가이다.
결국엔 2개의 데이터를 제거해야하기 때문에 LinkedList에 데이터를 담는 것이 효과적이라고 생각한다.
하지만, 내가 처음 문제를 풀었을 때는 리스트 2개를 사용해서 문제를 해결했다;;;

코드

fun solve(){
        val l : ArrayList<Int> = arrayListOf()
        val tempL = arrayListOf<Int>()
        repeat(9){
            val h = readLine()!!.toInt()
            tempL.add(h)
        }
        l.addAll(tempL)

        for(i in 0 until l.size){
            for(j in (i+1) until l.size){
                val v1 = l[i]
                val v2 = l[j]
                l.remove(v1)
                l.remove(v2)
                if(l.sum() == 100){
                    l.sort()
                    l.forEach {
                        println(it)
                    }
                    return
                }else{
                    l.clear()
                    l.addAll(tempL)
                }
            }
        }
    }

문제를 처음 해결 했을 때는 리스트를 2개 사용했다
알고리즘 자체는 생각을 그대로 표현해서
1. 리스트에 data 2개 제외
2. 합이 100이 되는가?
3. 된다면 정답출력
4. 안된다면 원본 리스트를 다시 담는다.
이 알고리즘의 문제는 삭제가 빈번히 일어난다는 것이다. 효과적이지 못하다
그래서 두번째로 구현 했을 때는

fun solve2(){
        val l = LinkedList<Int>()
        var total = 0
        repeat(9){
            val h = readLine()!!.toInt()
            total += h
            l.add(h)
        }

        loop@for(i in 0 until l.size - 1){
            for(j in (i+1) until l.size){
                if(total - (l[i] + l[j]) == 100){
                    val v1 = l[i]
                    val v2 = l[2]
                    l.remove(v1)
                    l.remove(v2)
                    break@loop
                }
            }
        }
        l.sort()
        for(element in l){
            println(element)
        }
    }

LinkedList를 사용하였고, loop@ break@loop를 통해 2중 for문의 중지를 제어하였다.
또한 list의 값을 삭제하고 다시 담는 것이 아니라, total 변수에서 값을 차감해본 후 100이 된다면 list에서 삭제함으로써 삭제가 필요한 경우에만 발생하도록 하였다.