[Programmers] 체육복

 

1. 문제

 

2. 아이디어

0. 이 문제의 답은(전체 학생수 - 잃어버린 학생수)로 구하자. -> lost 배열의 원소를 제거하는 방식으로 풀어가자.

1. 도난당한애 == 여벌있는애 일 경우부터 삭제하고 시작하자. ∵ 어차피 여벌있으면서 도난당한애는 다른애한테 빌려주지 못한다.

2. 앞번호 먼저 검사 뒷번호 후검사를 하자. // Mistake

 

 

3. 주의사항

        for(index in lostList.indices) {
//            잃어버린 애, 가져온애가 같으면 양쪽 리스트에서 둘다 삭제
            if (reserveList.remove(lostList[index])) lostList.removeAt(index)
        }

 

for loop에서 index를 활용하여 '정순'으로 순환하면서 컬렉션의 원소를 제거하는 경우

원소가 제거된 후 index는 증가하는데 원소는 빈자리를 메꾸며 앞으로 당겨지기 때문에 원하는 값을 얻지 못하고

outOfIndex 혹은 outOfBound Exception이 발생할 수 있다.

 

따라서 이 문제를 풀때 나는 '역순'으로 loop을 돌린다.

-> 역순으로 돌린다면 '앞번호 선검사 뒷번호 후검사'가 아닌 '뒷번호 선검사, 앞번호 후검사'를 해야한다.

그림을 그려보면 왜 그런지 바로 알 수 있다.

 

 

4. 문제 풀이

class Solution{
fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
//        1. 도난당한애 == 여벌있는애 상쇄
//        reserve 가져온애가 lost 랑 같은경우는 어차피 못빌려줌
        val lostList = lost.toMutableList()
        val reserveList = reserve.toMutableList()
//        잃어버린애 만큼 일단 상쇄 시도
        for(index in lostList.indices.reversed()) {
//            잃어버린 애, 가져온애가 같으면 양쪽 리스트에서 둘다 삭제
            if (reserveList.remove(lostList[index])) lostList.removeAt(index)
        }
//        2. lost 기준 앞/뒤 여벌 있는지 확인.
//        있으면 지우고 reserve에서 해당 원소 삭제
        for (index in lostList.indices.reversed()) {
            //                뒷번호 검사, 존재하면 lost 및 바로 뒷번호 삭제
        // 역순일 경우 뒷번호부터 검사하지 않으면 최대 숫자가 안나올 수 있다. (그림으로 이해하면 바로됨)
            if (reserveList.contains(lostList[index]+1)) {
                reserveList.remove(lostList[index]+1)
                lostList.removeAt(index)
        //            앞번호 후 검사, 존재하면 lost 및 바로 앞번호 삭제
            } else if (reserveList.contains(lostList[index]-1)) {
                reserveList.remove(lostList[index]-1)
                lostList.removeAt(index)
            }  else {
            }
        }
        return n - lostList.size
        
    }
}

 

Reference

www.techiedelight.com/remove-elements-from-list-while-iterating-kotlin/

Remove elements from a List while iterating in Kotlin - Techie Delight

collection에서 원소 제거시 iterator를 어떻게 활용해야 하는가를 소개해준다.