[99클럽 코테 스터디] 39일차 TIL - Assign Cookies

Hoxy?·2024년 8월 29일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

39/42

오늘의 학습 키워드

</> 탐욕법

공부한 내용 본인의 언어로 정리하기

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int iIndex = 0;
        int jIndex = 0;

        while(iIndex < g.length && jIndex < s.length){
            if(g[iIndex] <= s[jIndex]){
                iIndex++;
            }
            jIndex++;
        }
        return iIndex;
    }
}

오늘의 회고

오늘은 아이들이 가지고 있는 욕심의 크기만큼의 쿠기를 제공하여 만족시키고 만족할 수 있는 아이가 총 몇명인지 구하는 문제였다.

처음에는 ArrayList를 사용해서 아이들을 비교하고 해당 값이 만족된다면 그 값을 제거하고 난 후에 이어서 비교를 하는 방식으로 반복문을 사용하면서 풀었다.

하지만 23번 테스트케이스에서 g값과 s값이 대량으로 입력되었고 그 과정에서 시간초과가 나버려서 실패를 했다.

그 이유를 알아보니 매번 제거되는 과정에서 엄청난 시간이 걸리게 되어 실패하게 되었다고 했다.

그래서 아예 방식을 바꿔서 제공된 조건이 만족이 된다면 만족되는 만큼의 아이의 순서만 반환을 해주면 되겠다고 생각하여 방식을 바꿔서 진행하였다.

우선 배열 g와 배열 s의 값을 오름차순으로 정렬을 해주었고 내가 구해야하는 순서도 객체를 만들어 초기화를 해주었다.

Arrays.sort(g);
Arrays.sort(s);

int iIndex = 0;
int jIndex = 0;

그리고 이번에는 for문 대신에 전체값을 반복해주기 위해 while을 사용하며 최대 범위의 조건을 걸어주었다.

while(iIndex < g.length && jIndex < s.length)

그리고 문제에서 주어진 조건인 s[j] >= g[i] 에서 i와 j는 내가 초기화한 iIndex, jIndex와 같으므로 똑같이 입력해준다.

if(g[iIndex] <= s[jIndex])

내부의 과정에서 조건이 만족한다면 다음 아이를 아니라면 다음 쿠키를 증가시켜서 조건을 비교시켜 주었다.

if(g[iIndex] <= s[jIndex]){
                iIndex++;
            }
            jIndex++;
        }

그리고 최종적으로 증가된 iIndex를 반환해준다면 만족시킨 아이의 순서가 되므로 만족한 아이의 수와 같아진다.

AI 코드리뷰

현재 코드의 장점

정확성: 코드가 의도한 대로 동작하여, 각 어린이의 요구를 충족시키는 최대 수를 정확하게 반환합니다.
간결성: 로직이 간단하고 이해하기 쉬우며, 변수명도 적절하여 코드의 가독성이 좋습니다.

현재 코드의 단점

정렬 성능: 정렬에 대한 시간 복잡도가
𝑂(𝑛log𝑛)와 𝑂(𝑚log⁡𝑚)입니다. 여기서 𝑛은 어린이의 수, 𝑚은 쿠키의 수입니다.
코드 효율성: 정렬된 두 배열을 한 번씩만 순회하여 결과를 얻는 것은 효율적이지만, 정렬 자체에 필요한 시간이 상당할 수 있습니다.

시간 복잡도

정렬: Arrays.sort()의 시간 복잡도는 𝑂(𝑛log𝑛)및 𝑂(𝑚log⁡𝑚)입니다.
탐색: while 루프의 시간 복잡도는 𝑂(𝑛+𝑚)입니다.

개선된 코드 제안

import java.util.Arrays;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        
        int childIndex = 0;
        int cookieIndex = 0;

        // 두 배열을 한 번씩만 순회하며 최적의 쿠키 분배를 찾는다.
        while (childIndex < g.length && cookieIndex < s.length) {
            if (g[childIndex] <= s[cookieIndex]) {
                childIndex++;
            }
            cookieIndex++;
        }
        return childIndex;
    }
}

개선된 코드의 장점

변수명 개선: iIndex와 jIndex 대신 childIndex와 cookieIndex를 사용하여 변수의 의미를 명확히 하여 코드의 가독성을 향상시킵니다.
코드 이해도 향상: 코드의 의도를 명확히 하여 이해하기 쉬운 구조로 변경하였습니다.

개선된 코드의 단점

정렬의 비용: 정렬 자체는 𝑂(𝑛log𝑛 + 𝑚log⁡𝑚)의 시간 복잡도를 가지며, 이는 문제의 크기가 커질수록 성능에 영향을 미칠 수 있습니다.
정렬이 불필요한 경우: 입력 배열이 이미 정렬되어 있는 경우에도 정렬 알고리즘을 호출하는 것은 불필요한 오버헤드입니다. 그러나 이 경우는 대부분의 일반적인 시나리오에서 문제가 되지 않습니다.

시간 복잡도