프로그래머스 - 체육복 [자바]

• 문제 링크 : 체육복

코딩테스트 연습 - 체육복

 

정답

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {

        /*
        체격순 번호의 앞 뒤만 가능
        e.g. 5<-4->3
        하나 차이만 가능

        최대한 많은 학생

        전체 학생 수 : n
        도난당한 학생 번호 : lost
        여벌 학생 번호 : reserve


        */

        int finalLost = lost.length;

        Arrays.sort(lost);
        Arrays.sort(reserve);

        //데이터 전처리를 해야한다.
        //lost와 reserve에 동일한 숫자가 있으면 제거
         for(int i=0; i<lost.length; i++){
            for(int j=0; j<reserve.length; j++){
                if(lost[i] == reserve[j] && reserve[j] != -1){
                    lost[i] = -1;
                    reserve[j] = -1;
                    finalLost--;
                    break;
                }
            }
        }



        //도난 학생들 for 앞뒤자신 번호 비교해서 빌려 받을 수 있으면 lost.length에서 뺀다
        //return은 n - final lost로
        int front = 0;
        int back = 0;

        for(int lostNumber : lost){
            for(int i=0; i<reserve.length; i++){
                if(lostNumber != -1 && reserve[i] != -1 && finalLost >= 0){
                    front = lostNumber - 1;
                    back = lostNumber + 1;

                    if(reserve[i] == front
                        || reserve[i] == back){
                        reserve[i] = -1;
                        finalLost--;
                        break;
                    }
                }

            }
        }
        //경우의 수가 1개 더 있음
        //서로 겹치게 받을 수 있는 경우 한명이 다른 선택지가 있다면 그걸 선택하면 모두 참여 가능


        return n - finalLost;
    }
}

 

분석

• 몇몇 테스트가 통과되지 않았는데 배열이 sort 되지 않은 것이 문제였음
  
  
• 순간 순간 최선의 선택을 하는걸 그리디 알고리즘이라고 한다.
  
  
• 이 문제에서는 전처리로 같은 숫자를 제거하는 것부터 하고 정렬 후 앞뒤 비교를 해야 정답에 도달할 수 있다.

 

최적 정답

• O(N)으로 해결함. 분석

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        int answer = n;

        for (int l : lost) 
            people[l-1]--;
        for (int r : reserve) 
            people[r-1]++;

        for (int i = 0; i < people.length; i++) {
            if(people[i] == -1) {
                if(i-1>=0 && people[i-1] == 1) {
                    people[i]++;
                    people[i-1]--;
                }else if(i+1< people.length && people[i+1] == 1) {
                    people[i]++;
                    people[i+1]--;
                }else 
                    answer--;
            }
        }
        return answer;
    }
}