[Swift/프로그래머스] 요격 시스템 (그리디)

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

문제가 백준의 전깃줄과 흡사해서 이 또한 LIS 로 풀어야하는 문제인줄 알았다.

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

 

원리는 비슷하지만 LIS와 DP 를 사용하지 않고 간단하게 해결 가능한 문제였다.

 

처음 내가 시도한 코드

import Foundation

func solution(_ targets:[[Int]]) -> Int {

    var connect = [(Int,Int)]()
    var dp = [Int](repeating : 1, count : targets.count)

    for target in targets {
        connect.append((target[0] ?? 0,target[1] ?? 0))
    }

    connect = connect.sorted {$0.0 < $1.0}

    print(connect)

    let array = connect.map {$0.1}

    for i in 0..<targets.count {
        for j in 0...i {
            if array[i] >= array[j]{
                dp[i] += max(dp[i],dp[j] + 1)
            }
        }
    }

    return 0
}

 

이런 느낌으로 LIS로 해결하려했는데 연속으로 증가할 필요가 없었고

 

튜플에 담아 미사일 끝부분을 기준으로 정렬해주고 순회하면 해결되는 문제였다.

 

풀이

import Foundation

func solution(_ targets:[[Int]]) -> Int {
    
    var connect = [(Int,Int)]()
    
    for target in targets {
        connect.append((target[0] ?? 0,target[1] ?? 0))
    }
    
    connect.sort { $0.1 < $1.1 }
    
    var count = 0
    var lastEnd = -1
    
     for target in connect {
        if target.0 >= lastEnd {
            count += 1
            lastEnd = target.1
        }
    }
    
    return count
}

 

미사일 끝부분의 위치를 기준으로 튜플을 담은 배열을 정렬해주었다.

 

그리고 미사일 끝부분을 요격하더라도 추락하지 않으므로 조건문으로서 taget.0 >= lastEnd로 조건을 설정해주었다.