스위프트 체육복 알고리즘 문제 배열에 대해 알아가기
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
| 5 | [2, 4] | [1, 3, 5] | 5 |
| 5 | [2, 4] | [3] | 4 |
| 3 | [3] | [1] | 2 |
예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.
예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.
일단 문제를 보고 생각한 것은
1. 체육복이 없는 친구 찾기
2. 체육복이 있는 친구 찾기
3. 체육복이 없는 친구가 옆에 있는 경우 있는 친구가 빌려주고 인덱스에서 삭제
var sum = 0
var arr = [Int]()
for i in 0...n {
if lost.contains(i) {
sum += 1
arr.append(i)
}
}
let krr = n - sum
var srr = [Int]()
for i in 0..<reserve.count {
srr.append(reserve[i])
}
var kkk = 0
for i in arr {
for j in srr {
if i + 1 == j {
kkk += 1
srr.remove(at: j)
break
} else if i - 1 == j {
kkk += 1
srr.remove(at: j)
break
} else {
kkk += 0
}
}
} return 0
}solution(5, [2,4], [1,3,5])
하지만 배열이 틀려지면 실패
맞으면 첫번째 인덱스 삭제 했지만 또 실패 - 첫번째 친구가 아닐 수 있기에
일단 배열에 가장 헷갈리는것 2중 배열과 배열이 돌아가는 형태이다. 가장 헷갈리는 중
var students = [Int](repeating: 1, count: n)
for l in lost {
students[l-1] = 0 // 체육복이 없는 친구는 0 변경
}
for r in reserve {
students[r-1] += 1 // 여벌 가지고 온 친구는 플러스 1
}
이렇게 해놓으면 students에 2개의 배열이 진행되는 것 같다. 아직 공부중이라 확신은 없지만
전 문제도 이렇게 풀이 했던거 같다.
즉 하나의 변수에 2개의 배열을 만들어서 인덱스에 저장을 하는거 같다 .
첫 번째 student는 인덱스 때문에 -1 해주는 것 같다 인덱스는 0부터 시작하니
n = 5 일경우 -1 했으니 인덱스 부여는 0 1 2 3 4 부여가 되고
리피팅 반복이니 1 1 1 1 1 된다
lost 2, 4 reverse 1, 3, 5 이면
for 문을 통해서 i - 1 인덱스에 0 주어진다
그래서 lost 인덱스에 0 1 2 3 4 차례대로 lost 2 ,4 이기에 2 -1 = 1 인덱스 부여 4 = 3 부여해서
첫번째 for 문은 student = 10101 값을 가지게 된다 인덱스는 0 1 2 3 4 이기 때문에
reverse 경우 1 3 5 임으로 - 1 해서 0 2 4 인덱스가 부여됨으로
두번째 for 문은 student = 20202 된다
이제 빌려줘도 없는 친구만 찾으면 된다.
var count = 0 // 체육복을 빌리지 못한 학생 수
for i in 0..<n {
if students[i] == 0 { // 0일 경우에만 작동한다
if i>0 && students[i-1] > 1 {
// 앞번호 학생에게 빌린다.
students[i] = 1 // i가 1번 인덱스 인 경우 1번 인덱스는 0에서 1로 채워진다(빌림을 받아서 0에서 1)
students[i-1] = 1 0번 인덱스는 2에서 1로 변경한다 (빌려줘서 2에서 1로)
} else if i<n-1 && students[i+1] > 1 {
// 뒷번호 학생에게 빌린다. 위와 동일한 방식이고 앞번호가 없으면 뒷번호로 넘어가서 수행한다.
students[i] = 1
students[i+1] = 1
} else {
// 빌리지 못했다. 하면 카운터 1을 하게 되고
최종적으로 총 학생 - 체육복이 없는 학생 = 체육시간 참가 가능한 인원 되서 리턴하게 된다
count += 1
}
}
}
return n - count
}
30분 고민하고 3번 실패하고 다른 사람 한 것을 보았다.
생각은 비슷했으나 배열 사용 방법을 잘 몰라서 헤매고 삽질을 오래한거 같다.
아직은 경험이 많이 필요한거 같다.