[99클럽 코테 스터디] 20일차 TIL - 체육복

Hoxy?·2024년 8월 10일
99클럽TIL개발자취업코딩테스트준비항해99
0

99클럽 코테 스터디

목록 보기
20/42
post-thumbnail

오늘의 학습 키워드

</> 탐욕법(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;
    }
    
}

오늘의 회고

오늘도 주제가 탐욕법이어서 어제와 비슷한 방법으로 풀이를 하면 되겠다고 생각하고 과정부터 작성을 시작하였다.
하지만 배열로 하지 않고 부여되는 배열의 값에서 풀이를 한다면 간단하게 풀 수 있지 않을까? 하고 다르게 시도를 해보았다.

  1. 여벌의 체육복을 가져온 사람은 바로 앞사람 또는 바로 뒷사람에게만 빌려줄 수 있다.
  2. 총 학생 수는 n이다
  3. 최종 반환해줄 값은 체육복을 가져온 사람 + 체육복을 빌린 사람이다.
  4. 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 코드리뷰

현재 코드의 장점

  1. 직관적인 접근 방식:

    • 학생들의 체육복 상태를 배열로 관리하면서, 체육복을 잃어버리거나 여분을 가진 학생들의 상태를 바로 반영하는 점은 매우 직관적입니다.
    • 학생들이 체육복을 빌려줄 수 있는 조건을 쉽게 확인할 수 있습니다.

  2. 단순한 구현:

    • 이중 for문을 통해 간단하게 체육복의 분배 상황을 확인하고 처리하는 방식은 이해하기 쉽습니다.

  3. 상태 관리의 명확성:

    • 학생들의 체육복 상태를 student 배열에 저장하고 이를 수정해 나가는 방식은 상태 관리를 명확하게 합니다.

현재 코드의 단점

  1. 불필요한 중복 검사:

    • 잃어버린 학생의 상태를 설정한 후, 여분이 있는 학생의 상태를 설정하는 부분에서 일부 중복이 발생할 수 있습니다. 예를 들어, 이미 여분이 있는 학생이 체육복을 잃어버린 경우 그 학생의 상태가 1이 되어야 하지만, 먼저 잃어버린 상태를 반영하고 이후에 여분을 추가하는 과정에서 불필요한 작업이 발생할 수 있습니다.

  2. 비효율적인 체육복 대여:

    • 체육복을 빌려주는 과정에서 앞 번호의 학생이 빌려줄 수 있는지, 그리고 뒷 번호의 학생이 빌려줄 수 있는지 모두 검사하는데, 이때 최적의 방법이 아닌 경우가 발생할 수 있습니다. 예를 들어, 뒷번호 학생이 더 적합하게 빌려줄 수 있는 상황이 있음에도 불구하고 앞번호 학생이 먼저 빌려줄 경우가 있습니다.

  3. 에지 케이스 처리 미흡:

    • 만약 lost와 reserve 배열에 동일한 학생 번호가 존재하는 경우(즉, 여분의 체육복을 가진 학생이 체육복을 잃어버린 경우), 이 학생에 대한 처리가 정확하지 않을 수 있습니다. 현재의 코드에서는 이 상황이 명확하게 처리되지 않습니다.

시간 복잡도

  • 시간 복잡도: O(n)
    • 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); // 뒷번호 학생을 재귀적으로 확인
            }
        }
    }
}

개선된 버전의 장점:

  1. 코드의 간결성:
  • 재귀적 접근은 문제를 부분 문제로 나눠서 처리하는 방식이므로, 반복적인 로직을 간결하게 작성할 수 있습니다. 특히 체육복을 빌려주는 논리를 직관적으로 표현할 수 있습니다.
  1. 문제의 자연스러운 분할:
  • 재귀적 방법은 문제를 자연스럽게 작은 하위 문제로 나누어 해결할 수 있게 해줍니다. 체육복 문제처럼 연속적인 학생 간의 관계를 처리할 때, 재귀적으로 접근하면 문제를 쉽게 분할하고 처리할 수 있습니다.
  1. 복잡한 논리 처리:
  • 여러 단계의 조건을 처리해야 하는 경우 재귀적 접근은 더 자연스럽고, 코드를 읽고 이해하기 쉽게 만들어줍니다. 예를 들어, 학생이 체육복을 빌릴 수 있는지 확인하고 그 다음 학생으로 넘어가는 과정이 재귀적으로 잘 표현됩니다.

개선된 버전의 단점:

  1. 스택 오버플로우:
  • 재귀적 함수 호출은 함수 호출 스택을 사용하므로, 매우 큰 입력 크기에서는 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다. 즉, 너무 깊은 재귀 호출은 프로그램을 중단시킬 수 있습니다.
  1. 비효율성:
  • 재귀 호출이 불필요하게 중복될 수 있습니다. 특히 이미 처리된 부분을 다시 처리하는 경우 비효율적일 수 있습니다. 이러한 경우 반복문 기반의 탐욕적 알고리즘이 더 효율적입니다.
  1. 메모리 사용량 증가:
  • 재귀적 접근은 각 함수 호출마다 메모리 스택을 사용하기 때문에 메모리 사용량이 증가합니다. 반복문을 사용하는 것보다 메모리 효율성이 떨어질 수 있습니다.

시간 복잡도:

재귀적 풀이에서 각 학생에 대해 재귀 호출이 이루어지므로, 최악의 경우 모든 학생에 대해 여러 번의 재귀 호출이 발생할 수 있습니다. 재귀 함수에서 borrowUniform은 각 학생의 앞번호 또는 뒷번호로 이동하며 체육복을 빌릴 수 있는지를 확인합니다.

시간 복잡도:

  • 최악의 경우: 각 학생에 대해 최대 2번(앞, 뒤)의 재귀 호출이 이루어질 수 있으므로, 시간 복잡도는
    𝑂(2^𝑛)까지 증가할 수 있습니다. 그러나 현실적으로는 체육복이 없는 학생의 수가 많지 않기 때문에 이 정도의 시간 복잡도가 실제로 발생하는 경우는 드뭅니다.
  • 일반적인 경우: 대부분의 경우 재귀 호출은 인접한 몇몇 학생들에 대해서만 일어나므로, 효율적인 상황에서는 시간 복잡도는
    𝑂(𝑛)에 가까울 수 있습니다.

결론:
재귀적 풀이의 장점은 코드의 간결성과 문제를 자연스럽게 분할할 수 있다는 점에 있습니다. 그러나 이 문제에서 재귀적 접근은 비효율적일 수 있으며, 특히 입력 크기가 클 경우 스택 오버플로우와 같은 문제가 발생할 수 있습니다. 반면, 탐욕적 알고리즘은 더 효율적으로 문제를 해결할 수 있으며, 일반적으로 이 문제에 더 적합한 해결 방법입니다.

내일 공부할 것 :

  1. 메모이제이션과 동적 프로그래밍
    메모이제이션: 재귀적 접근에서 중복되는 계산을 피하기 위한 메모이제이션 기법을 학습하세요.
    예를 들어, 피보나치 수열의 재귀적 계산에 메모이제이션을 적용
    동적 프로그래밍(DP): 재귀적 접근에서 메모이제이션을 통해 동적 프로그래밍으로 전환하는 연습
    예를 들어, 배낭 문제(Knapsack Problem)나 최장 공통 부분 수열(LCS) 문제

  2. ForEach문과 Arrays 함수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42862

profile
Hoxy?
모든것에 의문을 가지는 알아가는 취준생
이전 포스트

[99클럽 코테 스터디] 19일차 TIL - 과일 장수

다음 포스트

[99클럽 코테 스터디] 21일차 TIL - Pascal's Triangle

0개의 댓글