[ 프로그래머스 ] 체육복

NaHyun_kkiimm·2024년 3월 28일

알고리즘

목록 보기

15/18

문제 요약

n명이 있는 교실에는 체육복을 도난당한 그룹 lost와 여분의 체육복을 가진 그룹 reserve이 주어진다. 체육복의 등 뒤에는 숫자가 써져있으며, 여분을 가진 학생은 자신의 번호 앞 혹은 뒤 학생에게만 체육복을 빌려줄 수 있다.
이 때 수업을 들을 수 있는 최대한 많은 학생의 수는 몇인가?

[ 예시 ]

n	lost	reserve	return
5	[2,4]	[1,3,5]	5
5	[2,4]	[3]	4
6	[1,5,6]	[1,2,3,5]	5

[ 제약 조건 ]

여분을 가진 학생이 도난 그룹에 속해있을 수도 있다. 이럴 경우 남은 체육복의 수는 1개임으로 다른 학생에게 빌려줄 수 없다.
여벌을 가진 학생만이 대여해 줄 수 있다.
도난당한 그룹의 학생에서 번호가 중복되진 않는다.
여분을 가진 학생에서 번호가 중복되지 않는다.

[ 프로그래머스 ]

Level 1 / Java
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42862

풀이

1) 도난 그룹과 여분을 가진 그룹을 오름차순으로 정렬한다.
2) 도난을 당한 학생 중 여분을 가진 학생의 수를 먼저 계산한다.
3) 도난을 당한 학생 중 여분을 갖지 못한 학생의 수를 계산한다.

Code

시간 복잡도 : O(nlogn)

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;        
        Arrays.sort(lost);
        Arrays.sort(reserve);
        // 선택 절차 : 각 배열을 오름차순으로 정렬한다     
        for(int i=0;i<lost.length;i++) {
            for(int j=0;j<reserve.length;j++) {
                if (lost[i] == reserve[j]) {
                    answer++;
                    reserve[j] = -1;
                    lost[i] = -1;
                    break;
                }   
            }
        }
        // 도난당한 학생 중 여벌이 있는 학생 수 계산
        for(int i=0;i<lost.length;i++) {
            for(int j=0;j<reserve.length;j++) {
                if (lost[i] == reserve[j]-1 || lost[i] == reserve[j]+1) {
                    answer++;
                    reserve[j] = -1;
                    break;
                }
            }
        }
        // 도난당한 학생 중 여벌이 없는 학생 수 계산
        return answer;
    }
}

다른 풀이

위의 알고리즘 설계와 같은 코드이지만, 전체 학생의 체육복 현황을 관리함으로서 반복문의 중첩을 줄일 수 있다.

시간복잡도 $O(N)$ 이 되게 된다.

state배열에 저장되는 각각의 값은 다음을 의미한다.

-1 : 도난당한 학생 = 참가 불가

0 : 여벌은 없지만, 자신의 체육복을 지닌 학생 = 참가 가능

1 : 여벌이 있는 학생 = 참가 가능

여벌을 받을 수 없는 학생이 있는 경우, 전체 학생 수에서 -1을 진행하여 최종 결과값을 반환한다.

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        int[] state = new int[n];
        
        for(int l : lost)
            state[l-1]--;
        for(int r : reserve)
            state[r-1]++;
        // 도난당한 학생 중 여벌이 있는 학생 계산
        
        for(int i=0;i<n;i++) {
            if (state[i]==-1) {
                if (i-1>=0 && state[i-1]==1) {
                    state[i]++;
                    state[i-1]--;
                } else if (i+1<n && state[i+1] == 1) {
                    state[i]++;
                    state[i+1]--;
                } else {
                    answer--;
                }
            }
        }
        // 도난당한 학생 중 여벌이 없는 학생 계산
        return answer;
    }
}