오늘의 학습 키워드
</> 탐욕법(Greedy)
공부한 내용 본인의 언어로 정리하기
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
int[] student = new int[n];
//전체 학생 체육복 제공
for(int i = 0; i < n; i++){
student[i] = 1;
}
//잃어버린 학생 체육복 제거
for(int i = 0;i < lost.length; i++){
student[lost[i]-1]--;
}
//여별 체육복 있는 학생 추가
for (int i = 0; i < reserve.length; i++) {
student[reserve[i] - 1]++;
}
//체육복 빌려주기
for(int i = 0; i < n; i++){
//체육복이 없는 학생
if(student[i]==0){
//앞번호 학생에게 빌리면 (현재 학생이 첫 번째라면 앞 사람에게 빌릴 수 없다. && 앞 사람이 체육복을 소지하고 있는가?)
if(i > 0 && student[i-1] > 1){
//체육복 빌리기
student[i]++;
//뒷 학생에게 빌려주기
student[i-1]--;
//뒷번호 학생에게 빌리면 (현재 학생이 마지막 번째라면 뒷 사람에게 빌릴 수 없다. && 뒷 학생이 체육복을 소지하고 있는가?)
} else if (i < n-1 && student[i+1] > 1){
//체육복 빌리기
student[i]++;
//앞 학생에게 빌려주기
student[i+1]--;
}
}
}
//최종적으로 체육복의 소지값인 1이상의 값을 가진 학생들의 수만큼 answer에다 추가
for (int i = 0; i < n; i++) {
if (student[i] > 0) {
answer++;
}
}
return answer;
}
}
오늘의 회고
오늘도 주제가 탐욕법이어서 어제와 비슷한 방법으로 풀이를 하면 되겠다고 생각하고 과정부터 작성을 시작하였다.
하지만 배열로 하지 않고 부여되는 배열의 값에서 풀이를 한다면 간단하게 풀 수 있지 않을까? 하고 다르게 시도를 해보았다.
reserve[i+1]
or reserve[i-1]
이 lost[j]
와 같으면 반환값에 추가하기class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
for(int i =0; i < reserve.length; i++){
for(int j = 0; j<lost.length; j++){
if(i < n-1 && (reserve[i]+1)==lost[j]){
answer++;
} else if (i > 0 && reserve[i]-1 == lost[j]){
answer++;
}
}
}
return answer + (n -lost.length);
}
}
그렇게 처음 완성한 코드가 이렇게 되었다. 하지만 문제가 많았다. 테스트 통과는 커녕 중복되는 값을 처리하지 못했다.
위와 같은 코드는 체육복을 빌려주는 과정에서 중복으로 처리되는 값을 고려하지 못할뿐더러 여벌 체육복을 가져온 학생이 체육복을 도난 당한 경우도 처리하지 못하는 문제가 생긴다.
그래서 아예 처음부터 체육복의 소지 갯수로 진행을 하기 위해 전체 학생에게 체육복 개수 1개씩을 부여 해주고 도난 당하면 -1, 여벌 체육복이 있으면 +1을 해주는 식으로 풀이를 다시 시작하였다.
전체 학생에게 체육복을 제공하기 위해 배열의 최대크기가 n인 학생 배열을 우선적으로 만들어 주었다
int[] student = new int[n]
그리고 전체 학생에게 체육복의 수를 제공하였다
for(int i =0; i < n; i++){
student[i]= 1;
}
이제 체육복을 도난당한 학생과 여벌 체육복을 가지고 있는 학생을 처리 해야했다.
우선 도난당한 학생의 체육복부터 처리하도록 하자
for(int i =0; i<lost.length; i++){
student[lost[i]-1]--;
}
그리고 여벌 체육복을 가지고 있는 학생의 개수를 추가하자
for(int i = 0; i < reserve.length;i++){
student[reserve[i]-1]++;
}
제공되는 학생의 값은 1부터 시작하지만 인덱스 값은 0부터 시작하지 때문에 -1을 해주었다.
이제 잃어버린 학생과 여벌의 체육복을 가지고 있는 학생의 처리가 완료 되었다면 이제 체육복을 빌려주어야 한다
for(int i = 0; i < n; i++){
if(student[i] ==0)
}
체육복이 없는 학생은 배열의 값이 0 이다. 그러므로 값이 0인 학생만을 대상으로 한다.
if(i > 0 && student[i-1] > 1){
student[i]++;
student[i-1]--;
}
위의 코드는 학생의 앞에 사람이 있는지 그리고 앞사람이 체육복을 가지고 있는지 체크하여 빌려주는 과정이다.
반대로 뒤에 있는 학생에게 빌리는 경우도 추가해 주겠다. if문의 조건은 앞의 학생에게 빌리는 경우의 반대로 작성한다.
if( i < n-1 && student[i+1] > 1){
student[i]++;
student[i+1]--;
}
이렇게 되면 체육복을 주고 받는 모든 경우가 끝난다. 최종적으로 체육복을 가지고 있는 학생을 반환하면 되겠다.
for(int i = 0; i < n; i++){
if(student[i] > 0){
answer++;
}
}
return answer;
오늘 코드를 완성하고 내가 생각하는 코드들을 효율적으로 바꿀수 함수를 하나씩 알아보다 보니 배열에 반복문을 사용하는 것 대신 Arrays.fill(student, 1)
이라는 코드로 모든 배열에 값을 1로 채워 넣을 수 있었다.
그리고 모든 배열을 반복해서 순회하는 경우에는 forEach
문을 쓰는게 더 간편하고 효율적인 코드로 만들 수 있다는 것을 알지만 이해도가 많이 떨어져서 아직까지 확신을 가지고 사용하지 못하고 있다. 이 부분은 나중을 위해서라도 기본적으로 익혀둬야겠다.
AI 코드리뷰
현재 코드의 장점
직관적인 접근 방식:
단순한 구현:
for
문을 통해 간단하게 체육복의 분배 상황을 확인하고 처리하는 방식은 이해하기 쉽습니다.상태 관리의 명확성:
student
배열에 저장하고 이를 수정해 나가는 방식은 상태 관리를 명확하게 합니다.현재 코드의 단점
불필요한 중복 검사:
비효율적인 체육복 대여:
에지 케이스 처리 미흡:
lost
와 reserve
배열에 동일한 학생 번호가 존재하는 경우(즉, 여분의 체육복을 가진 학생이 체육복을 잃어버린 경우), 이 학생에 대한 처리가 정확하지 않을 수 있습니다. 현재의 코드에서는 이 상황이 명확하게 처리되지 않습니다.시간 복잡도
n
은 학생의 수입니다.for
루프는 모든 학생의 체육복 상태를 초기화합니다. 이는 O(n)입니다.for
루프는 각각 lost
와 reserve
배열을 한 번씩 순회하며, 이 경우 최악의 경우 O(n)에 가깝습니다.for
루프는 학생 배열을 한 번 더 순회하면서 체육복을 빌려주는 작업을 수행합니다. 이 역시 O(n)입니다.따라서, 전반적인 시간 복잡도는 O(n)입니다.
재귀적 함수를 이용해 체육복 문제를 해결하려면, 체육복을 잃어버린 학생이 체육복을 빌릴 수 있는지 확인하고, 체육복을 빌릴 수 있으면 그 다음 학생으로 넘어가는 방식으로 접근할 수 있습니다. 이 방법은 특정 학생이 체육복을 빌리는 과정을 재귀적으로 탐색하는 방식입니다.
아래는 재귀적 함수를 이용해 문제를 재구성한 코드입니다:
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
// 모든 학생이 체육복을 1개씩 가지고 있다고 가정
int[] student = new int[n];
Arrays.fill(student, 1);
// 잃어버린 학생 체육복 제거
for (int l : lost) {
student[l - 1]--;
}
// 여벌 체육복 있는 학생 추가
for (int r : reserve) {
student[r - 1]++;
}
// 재귀적으로 체육복 빌리기 시도
for (int i = 0; i < n; i++) {
if (student[i] == 0) { // 체육복이 없는 학생
borrowUniform(i, student, n);
}
}
// 체육복을 가진 학생의 수를 세기
int answer = 0;
for (int s : student) {
if (s > 0) {
answer++;
}
}
return answer;
}
// 체육복 빌려주는 재귀 함수
private void borrowUniform(int i, int[] student, int n) {
// 기저 조건: 첫 번째 학생이거나 마지막 학생이면 종료
if (i < 0 || i >= n) {
return;
}
// 앞번호 학생이 여벌 체육복을 가지고 있는 경우
if (i > 0 && student[i - 1] == 2) {
student[i]++;
student[i - 1]--;
}
// 뒷번호 학생이 여벌 체육복을 가지고 있는 경우
else if (i < n - 1 && student[i + 1] == 2) {
student[i]++;
student[i + 1]--;
}
// 빌릴 수 없는 경우 다음 학생으로 넘어가며 재귀 호출
else {
if (i > 0) {
borrowUniform(i - 1, student, n); // 앞번호 학생을 재귀적으로 확인
}
if (i < n - 1) {
borrowUniform(i + 1, student, n); // 뒷번호 학생을 재귀적으로 확인
}
}
}
}
개선된 버전의 장점:
개선된 버전의 단점:
시간 복잡도:
재귀적 풀이에서 각 학생에 대해 재귀 호출이 이루어지므로, 최악의 경우 모든 학생에 대해 여러 번의 재귀 호출이 발생할 수 있습니다. 재귀 함수에서 borrowUniform
은 각 학생의 앞번호 또는 뒷번호로 이동하며 체육복을 빌릴 수 있는지를 확인합니다.
시간 복잡도:
결론:
재귀적 풀이의 장점은 코드의 간결성과 문제를 자연스럽게 분할할 수 있다는 점에 있습니다. 그러나 이 문제에서 재귀적 접근은 비효율적일 수 있으며, 특히 입력 크기가 클 경우 스택 오버플로우와 같은 문제가 발생할 수 있습니다. 반면, 탐욕적 알고리즘은 더 효율적으로 문제를 해결할 수 있으며, 일반적으로 이 문제에 더 적합한 해결 방법입니다.
내일 공부할 것 :
메모이제이션과 동적 프로그래밍
메모이제이션: 재귀적 접근에서 중복되는 계산을 피하기 위한 메모이제이션 기법을 학습하세요.
예를 들어, 피보나치 수열의 재귀적 계산에 메모이제이션을 적용
동적 프로그래밍(DP): 재귀적 접근에서 메모이제이션을 통해 동적 프로그래밍으로 전환하는 연습
예를 들어, 배낭 문제(Knapsack Problem)나 최장 공통 부분 수열(LCS) 문제
ForEach문과 Arrays 함수
문제
https://school.programmers.co.kr/learn/courses/30/lessons/42862