[프로그래머스 - JAVA]탐욕법(Greedy) - Level 1 체육복

문제

 

풀이

풀이1

• add, remove가 간편하게 List 형태로 변환 (이 과정에서 코드가 길어진다. 변환 안하고 하는 방법은 없을까)
• 체육복 여분이 있으면서 도난 당한 사람 List에서 제거 (분실한 사람, 여분 갖은 사람 List 양쪽 다)
• 분실한 사람들의 양쪽 번호 검사하면서 체육 못하는 사람 수만큼 answer--

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        
        List<Integer> loList = new ArrayList<>();
        List<Integer> reList = new ArrayList<>();
        for(int i : lost){
            loList.add(i);
        }
        for(int i : reserve){    
            reList.add(i);
        }
        
        for(int i = 0 ; i < lost.length; i++){
            for(int j = 0 ; j < reserve.length; j++){
                if(lost[i] == reserve[j]){
                    loList.remove((Integer)lost[i]);
                    reList.remove((Integer)reserve[j]);
                }
            }
        }
        
        for(int i = 0 ; i < loList.size(); i++){
            if(reList.contains(loList.get(i) + 1)){
                reList.remove((Integer)(loList.get(i) + 1));
                continue;
            }
            
            if(reList.contains(loList.get(i) - 1)){
                reList.remove((Integer)(loList.get(i) - 1));
                continue;
            } 
            answer--;
        }
        
        return answer;
    }
}

 

 

풀이2

• 학생들 각각 체육복 개수에 대한 배열을 생성하고 없으면 -1, 여분이 있으면 1로 저장
• 학생들 배열을 돌며 -1일때 앞 뒤 학생을 탐색하며 최대한 0으로 맞추기 
• index 관련 exception을 막기 위해 조건문에 범위 지정 

 

 

---

한동안 List를 많이 써서 그런지 모든 문제에 먼저 List 형태의 뭔가를 만들어 놓고 하려고 한다. 이 문제도 List를 안쓰고 푼 코드가 조금 더 속도가 빨랐다. 여러가지 자료구조를 사용해보면 이런 습관은 없어지리라 생각하지만... 

문제를 풀기 전에 먼저 생각을 좀 하고 푸는 습관이 있어야겟다.