Notice
Recent Posts
Recent Comments
Link
슈프림 블로그
[프로그래머스] 탐욕법(Greedy) - 체육복 (Swift 풀이) 본문
728x90
programmers.co.kr/learn/courses/30/lessons/42862
코딩테스트 연습 - 체육복
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번
programmers.co.kr
학생들이 가지고 있는 체육복의 개수를 저장하는 배열 students
일단 모든 학생이 기본적으로 1벌의 체육복을 가지고 있으므로 1을 n번 반복하여 저장한다.
var students = [Int](repeating: 1, count: n)
잃어버린 사람은 체육복을 1벌 빼고, 여벌을 가져온 사람은 체육복을 1벌 증가시킨다.
여기서, lost 배열과 reserve의 값은 몇번째 학생인지를 나타내는 것이므로, 배열의 인덱스값으로 넣기 위해서는 -1을 해주어야 한다.
// 잃어버린 사람은 체육복 0벌
for l in lost {
students[l-1] = 0
}
// 여벌 가져 온 사람은 +1 벌
for r in reserve {
students[r-1] += 1
}
이제 students 배열을 탐색하면서, 체육복이 0벌인 학생을 발견하면 앞, 또는 뒤의 학생이 체육복을 2벌 이상 가지고 있으면 빌리도록 한다.
앞 뒤 학생 모두에게 빌리지 못하면, 빌리지 못한 학생 count를 1 증가시킨다.
var count = 0 // 체육복을 빌리지 못한 학생 수
for i in 0..<n {
if students[i] == 0 {
if i>0 && students[i-1] > 1 {
// 앞번호 학생에게 빌린다.
students[i] = 1
students[i-1] = 1
} else if i<n-1 && students[i+1] > 1 {
// 뒷번호 학생에게 빌린다.
students[i] = 1
students[i+1] = 1
} else {
// 빌리지 못했다.
count += 1
}
}
}
최종적으로, 전체 학생 수 n에서 count 를 뺀 값을 반환한다.
최종 코드
import Foundation
func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
// 가지고 있는 체육복 개수 저장 (기본적으로 1벌)
var students = [Int](repeating: 1, count: n)
// 잃어버린 사람은 체육복 0벌
for l in lost {
students[l-1] = 0
}
// 여벌 가져 온 사람은 +1 벌
for r in reserve {
students[r-1] += 1
}
var count = 0 // 체육복을 빌리지 못한 학생 수
for i in 0..<n {
if students[i] == 0 {
if i>0 && students[i-1] > 1 {
// 앞번호 학생에게 빌린다.
students[i] = 1
students[i-1] = 1
} else if i<n-1 && students[i+1] > 1 {
// 뒷번호 학생에게 빌린다.
students[i] = 1
students[i+1] = 1
} else {
// 빌리지 못했다.
count += 1
}
}
}
return n - count
}
반응형
'코딩테스트' 카테고리의 다른 글
[프로그래머스] 탐욕법(Greedy) - 큰 수 만들기 (Swift 풀이) (1) | 2021.01.10 |
---|---|
[프로그래머스] 월간코드챌린지1 - 삼각 달팽이 (Swift 풀이) (0) | 2021.01.04 |
[프로그래머스] 2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임(Swift / Python 풀이) (0) | 2020.10.23 |
[프로그래머스] 월간 코드 챌린지 시즌1 - 두 개 뽑아서 더하기 (Swift 풀이) (0) | 2020.10.23 |
[프로그래머스] 이분탐색 - 징검다리 (Swift 풀이) (0) | 2020.10.21 |
Comments