프로그래머스 문제) 체육복
반에서 체육복 도난 사건이 있었는데, 여벌 체육복이 있는 학생이 도난 당한 학생들에게 체육복을 빌려주려 한다. 학생들의 번호는 체격 순으로 매겨져 있어서 바로 앞번호의 학생이나 뒷번호의 학생에게만 체육복을 빌려줄 수 있다. ex. 4번은 3번과 5번한테만 빌려줄 수 있다. 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 한다.
전체 학생수 n, 도난당한 학생의 번호가 담긴 배열 lost, 여벌 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어진다. 체육수업을 들을 수 있는 학생의 최대값은?
주의) 여벌 체육복을 가져온 학생이 체육복을 도난 당하면 한 벌만 남아있는거로 생각한다.
문제의 의미는 알겠는데 이것을 코드로 어떻게 구현할까. 잘 떠오르지 않아 알고리즘 분류를 보니 탐욕법이라고 되어 있다.
원래 알고리즘 분류를 보지 않고 냅다 풀었는데 요즘 알고리즘 공부에 대해 알아보고 있기 때문에 한 번 찾아보기로 했다.
탐욕 알고리즘
[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬
❗️탐욕 알고리즘(Greedy Algorithm)이란? Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에
hanamon.kr
링크를 참고하여 탐욕 알고리즘을 공부했다. 선택의 순간마다 최적의 상황만을 쫓아 최종적 해답에 도달하는 방식이라고 한다. 탐욕 알고리즘을 적용하려면 문제가 다음 조건을 성립하여야 한다.
탐욕스런 선택 조건(greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않음.
최적 부분 구조 조건(Optimal Substructure) : 문제에 대한 최적해가 부분문제에 대해서도 최적해.
이 조건을 만족하는 특정한 상황이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다고 한다.
조건은 부합하는가?
1. 문제에서 학생들은 체격순으로 번호가 매겨져 있으므로, 앞 번에서 선택을 한 것이 이후의 선택에 큰 영향을 주지는 않는다.
다만, 4번이 체육복의 여유분이 있는 상태에서 3번 5번이 체육복을 잃어버린 경우 3번이 먼저 4번의 체육복을 빌리게 되면 5번에게는 영향이 간다. 하지만 역시 5번에게 빌려주면 3번도 못 받게 되므로 return값에는 변함이 없을 것 같다.(코드를 짜봐야 확실히 알 거 같다.)
2. 학생수가 많고 적음에 따라서 문제 방식이 달라지는게 아니므로 최적 부분 구조 조건도 만족할 거 같다.
문제 풀기
✅ 이미 한 번 빌려준 사람은 빌려주지 못한다.
✅ greedy 알고리즘 문제라면 하나 하나 다 보는 방식으로 알고리즘을 짜야 하니 일단 for문을 돌린다고 생각한다.
반 학생들을 for문으로 돌릴려면 일단 먼저 1번부터 n번까지의 index를 사용하기 위해 인트배열을 하나 만든 뒤, 1번부터 n번까지 인덱스의 자리에 1을 넣어준다.(각자가 가지고 있는 체육복의 개수)
reserve에 해당하는 인덱스는 2를 넣어준다.
lost에 해당하는 인덱스는 -1을 해준다. 0을 넣으면 안된다. 체육복을 여유로 들고 왔다가 잃어버린 경우는 체육복이 한 개 있는 경우로 치기 때문이다.
for문을 1번부터 n번까지 돌려서 만약에 값이 0인 경우
- i-1 인덱스가 2인지 확인, i-1 인덱스의 값을 2->1, i인덱스의 값을 0 ->1 해준다.
- 아니면 i+1 인덱스가 2인지 확인, 위와 같이 해준다.
for문을 다시 1번부터 n번까지 돌려서 각 인덱스의 값이 1인 경우일때만 count하여 return한다.
오류가 났다!
int 배열을 만들 때 index값=번호값으로 편하게 하고 싶어서 크기를 n+1의 크기로 했더니 마지막 index에서 i+1 인덱스가 없는데여? 하는 오류였다. 그럼 뭐 하나 더 넣어주지 뭐. 해서 n+2의 크기로 만들어서 해결.
int[] allStudents = new int[n + 2];
정답!
코드 리뷰
나는 각자의 체육복 값을 다 계산해 준 다음, 다시 체육복의 수대로 count를 하여 체육 수업을 들을 수 있는 최대 학생의 수를 리턴했는데,
어떤 분이 쓴 걸 보니 어차피 앞의 코드가 뒤 코드에 영향을 끼치지 않으므로 index의 값이 0으로 결정난 순간 그 학생을 반 전체의 학생 수에서 빼면 되는 것이었다. 한 번 더 for문을 돌릴 필요가 없었다.
그래도 문제의 알고리즘이 무엇인지 알아보고, 그 구조에 맞추어 코드를 짜보고, 잘 맞추고 했다는 점에서는 칭찬.
하지만 이번의 경우에는 아 이 문제는 그리디 알고리즘이니까 그 때 그 때 최적해를 구해야겠구나를 알고 풀었지만 다음에도 비슷한 문제를 그리디 알고리즘으로 파악하고 풀 수 있을까? 문제를 풀다 보면 어떤 문제가 그리디 문제인지 감이 잡힌다고 하니 많이! 그리고 성실하게! 풀어볼 것!!
'STUDY > JAVA' 카테고리의 다른 글
[TIL] 다형성 코드로 익혀보기 (0) | 2023.05.27 |
---|---|
[TIL] 프로그래머스 - 완주하지 못한 선수 (0) | 2023.05.26 |
[TIL] 프로그래머스 - 숫자 짝꿍 (0) | 2023.05.22 |
[TIL] 약수의 개수 구하기 빠른 방법 (0) | 2023.05.14 |
230411 공부기록 (0) | 2023.04.12 |