[Java : 프로그래머스] 체육복

문제

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

풀이

자바가 갖고 있는 자료구조나 클래스들에 익숙해지기 위해 도전했다가
int와 Integer의 차이, ArrayList 등 많이 배운 문제.
우선 틀린 풀이부터…

1차 풀이

key값을 이용한 요소제거를 위해서 Hashtable 자료구조로 접근했다.

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Hashtable<Integer, Integer> ht = new Hashtable<Integer, Integer>();
        // lost만큼 해시 테이블에 key 추가.
        for(int l : lost){ ht.put(l, 0); }
        // reserve만큼 테이블에서 key 제거.
        for(int r : reserve){
            // 자기 자신부터 챙기고,
            if(ht.containsKey(r)) ht.remove(r);
            // 나보다 작은 애 챙겨주고,
            else if(ht.containsKey(r-1)) ht.remove(r-1);
            // 나보다 큰 애 챙겨준다.
            else if(ht.containsKey(r+1)) ht.remove(r+1);
        }
        // 수업 참여 못하는 학생만큼 빼서 반환.
        return n-ht.size();
    }
}

5, 7번 테스트 케이스에 걸렸다. 왜 걸리는 것인지 조사해본 결과,
여유분을 가지고 있는 학생은 다른 친구를 챙기기 전에 우선 자기부터 입어야한다는
Greedy 특성에 걸맞는 전처리를 먼저 행해줘야 한다는 걸 알게 됐다.

2차 풀이

Key와 Value를 모두 사용하지 않았기에 Hashtable이 부적합해보였다.
파이썬의 List와 비슷한 자료구조가 있을까 알아보니, ArrayList라는 자료구조가 있었다.
오호, ArrayList를 사용하면 될 것 같다!

ArrayList의 메소드 중 해당하는 원소가 들어있는지 파악하는 contains가 있었는데,
contains에 primitive(int, double…)가 들어가면 인덱스 검사,
Wrapper(Integer, Long…)가 들어가면 객체 검사가 진행됐다.

‘학생 번호 배열이 int형 자료형인데… 어떻게 객체 검사를 진행시켜야하지?’

고민하면서 int와 Integer의 차이 대해 공부하게 됐다.
공부한 내용을 총집합해서 코드를 재작성해보자!

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        // Integer 자료형 ArrayList 생성.
        List<Integer> Lost = new ArrayList<Integer>(lost.length);
        List<Integer> Reserve = new ArrayList<Integer>(reserve.length);
        // ArrayList에 int형 배열 원소들을 삽입.
        for(int l : lost) { Lost.add(l); }
        for(int r : reserve) { Reserve.add(r); }
        // Greedy하게, Reserve를 가지고 Lost 당했으면 제외.
        for(Integer i = 1; i < n+1; i++){
            if(Lost.contains(i) && Reserve.contains(i)){
                Lost.remove(i);
                Reserve.remove(i);
            }
        }
        // Reserve가 없을 때 까지.
        while(!Reserve.isEmpty()){
            // Reserve 추출.
            Integer r = Reserve.remove(0);
            // 나보다 작은 애가 Lost 당했으면 챙겨주기.
            if(Lost.contains(r-1)) Lost.remove((Integer)((int)r-1));
            // 나보다 큰 애가 Lost 당했으면 챙겨주기.
            else if(Lost.contains(r+1)) Lost.remove((Integer)((int)r+1));
            
        }
        // 수업 참여 못하는 학생만큼 빼서 반환.
        return n-Lost.size();
    }
}

성공!

더 나은 풀이

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;
    }
}

• 전체 학생 수 크기의 배열 생성.
• 잃어버린 학생은 -1, 여유분이 있는 학생은 1로 초기화.
• 루프를 돌면서 나보다 작은 애한테 먼저 빌려보고, 큰 애한테 다시 빌린다.

깔끔하다.