반응형
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
입출력 예
| n | lost | reserve | return |
| 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) 풀이 과정(로그 + 주석)
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
// 여벌 체육복 -> 빌려준다
// 빌려주는 것 -> 앞뒤로만 빌려줄 수 있다 (index)
// 앞-뒤 (독립, 전체-부분) -> 이 조건이 없으면
// 완전탐색 문제 1번 -> 끝까지...
// -> 가능한 많은 사람들이 체육복을 빌려야한다
// 전체 학생의 수 n
// 도난 당한 학생들 lost
// 여분 reserve (여분은 1개씩 밖에 없음)
// 도난 당했다면 여분은 의미 없음
System.out.println(String.format("전체 학생의 수 : %d", n));
System.out.print("도난 당한 학생들 : ");
for (int l : lost) {
System.out.print(l + " ");
}
System.out.println();
System.out.print("여분 있는 학생들 : ");
for (int r : reserve) {
System.out.print(r + " ");
}
System.out.println();
// 현재 자리 배치 먼저 생각해야함 (자리별로, 도난-여분을 다 정리하고 나서...)
// int[] seat = new int[n+1]; // 1부터 n까지 인덱스를 사용 -> 0으로 다 대입되어 있는 배열
int[] seat = new int[n+2]; // 맨 뒷자리도 뒤를 탐색할 수 있게
for (int l : lost) {
// l -> 잃어버린 학생들의 자리 번호 -> index로 사용해줄 수 있음
seat[l]--; // 1개씩 잃어버린 걸 반영함
}
System.out.println("체육복 현황");
for (int s : seat) {
System.out.print(s + " ");
} // 0 0 -1 0 -1 0
for (int r : reserve) {
seat[r]++; // 1개의 여분을 반영
}
System.out.println();
System.out.println("체육복 현황");
for (int s : seat) {
System.out.print(s + " ");
} // 0 1 -1 1 -1 1 -> 상쇄를 배열에 반영하고 시작하고 싶은 것.
System.out.println();
// 체육복이 있어서 0 이상의 값을 유지한 학생들을 탐색
int answer = 0; // 참여할 수 있는 학생
for (int i = 1; i <= n; i++) { // 향상된 for문이 아니라 일반 인덱스로 해야할까?
// 실제 자리가 있는 n명 탐색
// 1부터 탐색 -> 0은 자리만 만들어둔 것이므로...
// 내가 -1이라면 앞뒤로 검색을 해서, 0으로 만들어주는 작업
// System.out.println(String.format("%d의 체육복 소지 여부 : %d", i, seat[i]));
if (seat[i] == -1) { // 체육복이 없으면
System.out.println(String.format("%d는 체육복이 없습니다", i));
// 앞에부터 여분이 있는지 검색을 해봐요
if (seat[i - 1] == 1) { // 앞자리 학생이 여분이 있다면
System.out.println(String.format("%d는 앞자리에게 체육복을 빌렸습니다", i));
seat[i - 1]--;
seat[i]++;
answer++; // 빌렸으니까 참석 가능
continue;
} // 이 이후는 앞자리에는 여분 없는 경우만 남음
if (seat[i + 1] == 1) { // 뒷자리 학생이 여분이 있다면
System.out.println(String.format("%d는 뒷자리에게 체육복을 빌렸습니다", i));
seat[i + 1]--;
seat[i]++;
answer++; // 빌렸으니까 참석 가능
}
} else { // 체육복이 있으면
answer++; // 체육복이 이미 있음
}
}
System.out.println("체육복 현황");
for (int s : seat) {
System.out.print(s + " ");
}
System.out.println();
return answer;
}
}
2) 클린 코드
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
// 학생들의 체육복 상태를 나타내는 배열을 생성합니다.
int[] people = new int[n];
// 전체 학생 수만큼 루프를 돌면서 배열 초기화 및 상태 설정을 합니다.
for (int l : lost)
people[l - 1]--; // 체육복을 도난당한 경우, 해당 학생의 상태를 -1로 설정
for (int r : reserve)
people[r - 1]++; // 여분의 체육복이 있는 경우, 해당 학생의 상태를 +1로 설정
int answer = n; // 최종적으로 수업을 들을 수 있는 학생 수를 저장하는 변수입니다.
// 학생들의 체육복 상태를 확인하면서 수업을 들을 수 있는지 판별합니다.
for (int i = 0; i < people.length; i++) {
if (people[i] == -1) { // 체육복이 없는 경우
if (i - 1 >= 0 && people[i - 1] == 1) {
// 앞번호 학생이 여분의 체육복을 가지고 있는 경우 빌림
people[i]++; // 체육복을 빌려서 수업을 들을 수 있는 상태로 변경
people[i - 1]--; // 앞번호 학생의 체육복 수를 감소시킴
} else if (i + 1 < people.length && people[i + 1] == 1) {
// 뒷번호 학생이 여분의 체육복을 가지고 있는 경우 빌림
people[i]++; // 체육복을 빌려서 수업을 들을 수 있는 상태로 변경
people[i + 1]--; // 뒷번호 학생의 체육복 수를 감소시킴
} else {
answer--; // 앞, 뒤 번호 학생 둘 다 여분의 체육복이 없는 경우 수업을 들을 수 없음
}
}
}
return answer; // 최종적으로 수업을 들을 수 있는 학생 수 반환
}
}
3) mermaid Diagram
sequenceDiagram
participant 솔루션
participant 메인
participant 배열
participant 시스템
메인 ->> 솔루션: solution(n, lost, reserve)
솔루션 ->> 솔루션: 학생 배열 생성
솔루션 ->> 배열: 학생 배열 초기화 (1로)
loop 잃어버린 학생 반복
솔루션 ->> 솔루션: 체육복 개수 감소
end
loop 여벌 체육복을 가진 학생 반복
솔루션 ->> 솔루션: 체육복 개수 증가
end
alt 체육복 대여 가능 여부 확인
loop 학생 배열 반복
alt 체육복 없음
솔루션 ->> 솔루션: 왼쪽에서 빌리기 가능하면 빌림
else
alt 빌릴 수 있는 체육복이 있음
솔루션 ->> 솔루션: 오른쪽에서 빌리기 가능하면 빌림
else
솔루션 ->> 솔루션: 체육복 있음, 계속 진행
end
end
end
else
솔루션 ->> 솔루션: 체육복 빌릴 수 없음
end
솔루션 ->> 메인: 결과 반환
반응형
