[프로그래머스/42862] 체육복

07 Feb 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 첫 번째 풀이 (실패)
  • 두 번째 풀이 (성공)

☑️ 문제

프로그래머스 42862

☑️ 풀이

첫 번째 풀이 (실패)

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int cnt = 0; 
        for (int i = 0; i < reserve.length; i++) {
            if (lost.length <= cnt) {
                break;        
            } else {
                for (int j = 0; j < lost.length - 1; j++) {
                    if (Math.abs(reserve[i] - lost[j]) == 1) {
                        cnt++;
                        break;
                    } 
                }
            }
        }
        
        int left = n - lost.length - reserve.length;
        return cnt + reserve.length + left;
    }
}

• 테케는 통과했지만, 제출했을 때 절반을 통과하지 못했다.
• 문제 조건 중 ”여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.” 이 부분을 간과했다.
  • lost 와 reserve 배열에는 중복된 학생이 있을 수 있다는 것!

두 번째 풀이 (성공)

//시간: 0.04ms
//메모리: 90.9MB

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int cnt = 0;
        int[] clothes = new int[n];
        Arrays.fill(clothes, 1);
        for (int l : lost) {
            clothes[l - 1]--;
        }

        for (int r : reserve) {
            clothes[r - 1]++;
        }

        for (int i = 0; i < clothes.length; i++) {
            if (clothes[i] == 0) {
                // 앞사람에게 빌릴 수 있는 지 확인
                if (i > 0 && clothes[i - 1] > 1) {
                    clothes[i - 1]--;
                    clothes[i]++;
                }
                // 뒷사람에게 빌릴 수 있는 지 확인
                else if (i < clothes.length - 1 && clothes[i + 1] > 1) {
                    clothes[i + 1]--;
                    clothes[i]++;
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < clothes.length; i++) {
            if (clothes[i] != 0) {
                answer++;
            }
        }
        return answer;
    }
}

• 이번에는 학생이 가진 체육복의 개수를 clothes 배열의 형태로 만들었다.
• 그리고 앞사람과 뒷사람에게 빌릴 수 있는 두 가지 경우로 나누어 반복문을 돌았다.
• 전체적으로 O(n) 의 시간복잡도를 가져 효율적이었다.