티스토리 뷰

728x90

https://programmers.co.kr/learn/courses/30/lessons/42862?language=swift 

 

코딩테스트 연습 - 체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번

programmers.co.kr

탐욕법(Greedy)

체육복을 도난 당한 친구들에게 여분이 있는 학생들이 양옆의 친구에게 빌려줘서
체육복이 없는 학생 인원을 최소로 줄여서 체육복이 있는 학생수를 출력하는 문제

 

접근방법

우선 본인이 여벌의 옷을 갖고 있는데 한개를 분실한 친구 번호는 양배열에서 모두 제거한다. (filter사용)

체육복이 있는 학생 번호를 담은 reserve 배열을 순회하면서 본인의 앞,뒤 친구가 lost 배열에 있으면

체육복을 빌려준다 ( lost 배열에서 지움 )

최종적으로 lost 배열에 남은 학생수(여분을 빌리지 못한 학생수)를 전체 인원(n)에서 빼서 반환한다.

 

오답노트

- 본인의 앞사람 번호를 참조할때 범위를 넘어갈 것을 대비해서 ( v-1 < 0 ? 0 : v-1 ) 로 했었는데 번호가 1번부터라 0을 1로 바꿔줘야 했음 => 그리고 사실 어차피 index 메서드로 있나 없나 체크하는거라 오버플로 대비를 내가 안해줘도 될 것 같음 (그럼 이게 원인은 아니었던거네..)

- 원래는 lost 배열을 순회하면서 본인의 앞,뒤 친구들에게 체육복을 빌리는 로직으로 구현했으나 실패했음. 근데 다른 요인일 수 있어서 다시 시도해볼 예정 (현재는 reserve 배열을 순회하는 것으로 구현한 상태)

- 순회하는 배열은 오름차순으로 정렬되어 있어야함 (가장 마지막 트러블이 이거였음)

- 그리고 본인에게 본인이 빌려주는 상황을 왜 꼭 filter해서 걸러야 하는지 모르겠음. if문에서 앞,뒤 전에 본인에게 빌려주는 경우를 처리할 수도 있을 것 같은데 안됨.

 

소스코드

import Foundation

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    var lostt = lost.filter{ !reserve.contains($0) }
    var reservee = reserve.sorted().filter{ !lost.contains($0) }
    
    for r in reservee {
        if let i = lostt.index(of:r-1){
            lostt.remove(at:i)
        }else if let i = lostt.index(of:r+1){
            lostt.remove(at:i)
        }
    }
    
    return n - lostt.count
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/02   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29
글 보관함