그리디알고리즘 체육복(프로그래머스)

1차 시도

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int cnt = 0;
        
        if(lost.length <= reserve.length){
            for(int i = 0; i < lost.length; i++){
                if(reserve[i] != lost[i] - 1 && reserve[i] != lost[i] + 1 && reserve[i] != lost[i]){
                    cnt++;
                }
            }
           answer = n-cnt; 
        }else if(reserve.length < lost.length){
            for(int i = 0; i < reserve.length; i++){
                if(reserve[i] != lost[i] - 1 && reserve[i] != lost[i] + 1 && reserve[i] != lost[i]){
                    cnt++;
                }
            }
            answer = n-cnt-(lost.length-reserve.length); 
        }
        
        return answer;
    }
}

예제는 맞았지만 채점해보니 16점...ㅎ

2차 시도

3개씩 비교를 하는 것은 아무래도 다른 케이스들을 생각하지 못하게 만들어서 새로운 방식을 사용하기로 함

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        
        //최소 lost에 없는 애들은 수업 들을 수 있음
        int answer = n-lost.length;
        
        for(int i = 0; i < reserve.length; i++){
            for(int j = 0; j < lost.length; j++){
                
                if(reserve[i] == lost[j]){
                    answer++;
                }else if(reserve[i] == lost[j]-1){
                    answer++;
                    i++;
                    j++;
                }else if(reserve[i] == lost[j]+1){
                    answer++;
                    i++;
                    j++;
                }
            }
        }
            
        return answer;
    }
}

이번에는 50점...

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        
        //최소 lost에 없는 애들은 수업 들을 수 있음
        int answer = n-lost.length;
        
        for(int i = 0; i < reserve.length; i++){
            for(int j = 0; j < lost.length; j++){
                
                if(reserve[i] == lost[j]){
                    answer++;
                }else if(reserve[i] == lost[j] + 1 && lost[j] != n){
                    answer++;
                }else if(reserve[i] > lost[j] + 1 && lost[j] != n){
                    i--;
                }else if(reserve[i] == lost[j] - 1 && lost[j] != 1){
                    answer++;
                }else if(reserve[i] < lost[j] - 1 && lost[j] != 1){
                    j--;
                }
                break;
            }
        }
        return answer;
    }
}

n차 시도...ㅎ

import java.util.ArrayList;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
        
        //하나씩 지워주는 것이 정신 건강에 이로우므로 ArrayList를 사용하기로 함
        ArrayList<Integer> res = new ArrayList<>();
        ArrayList<Integer> los = new ArrayList<>();
        
        //하나씩 담아준다
        for(int r : reserve){
            res.add(r);
        }
        
        for(int l : lost){
            los.add(l);
        }
        
        //여분의 체육복을 가져왔으나, 도둑 맞았을 때
        for(int i = 0; i < res.size(); i++){
            for(int j = 0; j < los.size(); j++){
                if(res.get(i) == los.get(j)){
                    res.remove(i); //더이상 빌려줄 수 없으므로 reserve에서 하나씩 지워준다.
                    los.remove(j); //수업에 참여할 수 있게 되었으므로 지워준다
                    j--;//lost, reserve에서 모두 지워지니까 처음부터 들을 수 있는 사람처럼 되버림, 그 자리부터 다시 시작
                    answer++;
                    
                    break;//멈춰서 다시 시작하니까
                }
            }
        }//여기서 reserve부터 지워줘야, 여분이 도둑맞지 않은 상황에서의 여분량을 재조정 가능
        
        for(int i = 0; i < res.size(); i++){
            for(int j = 0; j < los.size(); j++){
                if(res.get(i) == los.get(j) + 1 || res.get(i) == los.get(j) - 1){
                    res.remove(i); //더이상 빌려줄 수 없으니까
                    //los.remove(j); 수업에 참여할 수 있게 됐지만 answer에서 하나씩 제하니까 바뀌면 안됨
                    answer++;
                    
                    break; //다시 반복하도록
                }
            }
        }
        return answer;
    }
}

58점... 이쯤 되니 진짜 모르겠다.

n+1차 시도

import java.util.ArrayList;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
        
        //하나씩 지워주는 것이 정신 건강에 이로우므로 ArrayList를 사용하기로 함
        ArrayList<Integer> res = new ArrayList<>();
        ArrayList<Integer> los = new ArrayList<>();
        
        //하나씩 담아준다
        for(int r : reserve){
            res.add(r);
        }
        
        for(int l : lost){
            los.add(l);
        }
        
        //여분의 체육복을 가져왔으나, 도둑 맞았을 때
        for(int i = 0; i < los.size(); i++){
            for(int j = 0; j < res.size(); j++){
                if(res.get(j) == los.get(i)){
                    res.remove(j); 
                    los.remove(i); 
                    i--;
                    answer++;
                    
                    break;
                }
            }
        }
        
        for(int i = 0; i < los.size(); i++){
            for(int j = 0; j < res.size(); j++){
                if(res.get(j) == los.get(i) + 1 || res.get(j) == los.get(i) - 1){
                    res.remove(j);
                    answer++;
                    
                    break;
                }
            }
        }
        return answer;
    }
}

for문에서 los와 res의 순서를 바꾸니 또 맞는다...
왜 이러는 걸까...

일단 los(0) 일때 res(1)~res(reserve)
los(1) 일때 res(1)~res(reserve)
...

이므로 여분의 옷이 도둑 맞을 경우에는 res, los 다 사라져야 하니까 i--해서 새 루프(?)를 다시 돌려줬던 것임

옷을 빌려주는 경우에는 lost가 1번 학생이거나 n번 학생일때, 바로 옆 번호 (2번이나 n-1번) 만이 빌려줄 수 있으므로 los를 기준으로 이중 for문을 돌려야했다.
res를 기준으로 돌리게 되면 los의 경우도 사라지게되어 answer 값에 변동이 생겨버린다.

하... 다른 분 글 참고해서 한건데로 어려우니.... level2는 또 얼마나 걸릴지...ㅠㅠㅠㅠ

좋은 웹페이지 즐겨찾기