프로그래머스 Lv. 1 Swift 알고리즘 - 체육복_그리디

확실히 Lv2 풀다가 Lv1로만 내려와도 난이도가 다르다는게 느껴진다 이젠...

그 전에 풀었던 조이스틱과 같은 그리디 문제이지만 난이도가 훨씬 낮았다!

 

운동복을 빌려줄 수 있는 사람을 찾고 그 사람의 옆에 있는 사람 중에 운동복이 필요한 사람에게 운동복을 빌려주면 된다.

 

근데 사실 내가 푼 코드는 뭔가... 좀 많이 더럽다... 😇

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 일단 체육복을 빌려줄 수 있는 사람과 빌려야하는 사람을 나눴다.
2. 필요한 사람은 0으로 빌려줄 수 있는 사람은 99로 대체하였다.
3. 이때 놓치지 말아야할 것은 여유가 있다가 도난당한 사람이다.
4. 이 사람들은 빌려줄 수 있는 사람인 99에 들어가면 안되기 때문에
5. 0과 99로 값을 변환시켜주기전에 미리 100으로 변환시켜놓는다.
6. 그래야 for 문이 돌면서 0과 99를 대입할 때 오류값이 생기지 않는다.
7. 이렇게 for 문을 위에서부터 3개 돌리고나면 [0, 99, 3, 4, 5, 99, 0...] 이런 식으로 배열이 만들어진다.
8. 이때 이 배열을 기준으로 99인 원소의 인덱스에서 -1, +1 하여 앞 뒤 원소 중 0인 원소를 찾는다.
9. 0인 원소는 체육복이 필요한 원소이므로 99로부터 체육복을 건네받으면 자신의 위치값을 다시 생성받는다.
10. 이때 오른쪽 기준으로 주지 말고 왼쪽부터 채우는게 더 많은 사람들이 체육복을 받을 수 있도록 만드는 일이다.
11. 이를 반복하면 끝

 

 

* 처음 틀린 코드

import Foundation

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    // 0: 체육복이 필요한 사람, 99: 체육복을 빌려줄 수 있는 사람, 100: 여유가 있었는데 도난당해 빌려줄 수 없는 사람
    var arr: [Int] = Array(stride(from: 1, to: n+1, by: 1))
    var arrLost = lost
    var arrReserve = reserve
    
    for i in 0..<arrLost.count {
        for j in 0..<arrReserve.count {
            if arrReserve[j] == arrLost[i] {
                arrReserve[j] = 100
                arrLost[i] = 100
            }
        }
    }
    
    for i in 0..<arrLost.count {
        for j in 0..<arr.count {
            if arr[j] == arrLost[i] && arrLost[i] != 100 {
                arr[j] = 0
            }
        }
    }
    
    for i in 0..<arrReserve.count {
        for j in 0..<arr.count {
            if arr[j] == arrReserve[i] && arrReserve[i] != 100 {
                arr[j] = 99
            }
        }
    }
    
    for i in 0..<arr.count {
        if i == 0 {
            if arr[i] == 99 && arr[i+1] == 0 {
                arr[i+1] = i + 1
            }
        } else if i == arr.count-1 {
            if arr[i] == 99 && arr[i-1] == 0 {
                arr[i-1] = i - 1
            }
        } else {
            if arr[i] == 99 {
                if arr[i-1] == 0 && arr[i+1] != 0 {
                    if i - 1 == 0 {
                        // 0번째 위치한 값만 101로 예외 처리
                        arr[i-1] = 101
                    } else {
                        arr[i-1] = i - 1
                    }
                } else if arr[i-1] != 0 && arr[i+1] == 0 {
                    if i - 1 == 0 {
                        arr[i+1] = 101
                    } else {
                        arr[i+1] = i + 1
                    }
                } else if arr[i-1] == 0 && arr[i+1] == 0 {
                    if i - 1 == 0 {
                        arr[i-1] = 101
                    } else {
                        arr[i-1] = i - 1
                    }
                }
            }
        }
    }
    return arr.count - arr.filter{$0 == 0}.count
}

 

 

정리(Today I Learned)

1. 그리디는 결국 예외와의 싸움이다. 예외를 잘 찾자!