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

https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=java#

프로그래머스

 

파이썬으로 풀었던 문젠데 너무 바빠지기 전에 그리디 쉬운 문제 하나 풀고 싶어서 풀어봤다. 근데... 왜 틀린 건지 모르겠는데 기괴한 코드 하나 작성했다.

 

100점 만점에 90점이 나왔는데 어떤 부분이 틀렸는지 반례를 못 찾겠어서 일단 올려두고.. 

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {      
        
        Arrays.sort(reserve);
        Arrays.sort(lost);
        
        // 체육복 있으면 1, 없으면 0, 여벌 있으면 2 or 1
        for(int i = 1; i < n+1; i++){
            exist[i] = 1;
        }
        for(int i : lost){
            exist[i]--;
        }
        for(int i : reserve){
            exist[i]++;
        }
        
        // exist에서 0인 애들의 앞 뒤 중 하나가 2면 걔네를 1로 만들면서 끝
        for(int i = 1; i <n+1; i++){
            if(exist[i] == 0 && i < n){
                if(exist[i-1] == 2){
                    exist[i-1]--;
                    exist[i]++;
                }
                else if(exist[i+1] == 2){
                    exist[i+1]--;
                    exist[i]++;
                }
            }
        }
                
        for(int i = 1; i < n+1; i++){
            if(exist[i] > 0) answer++;
        }
        
        return answer;
    }
}

 

정답 풀이부터 하자면, 이중 for문 두 번 써주면 되는 아주 간단한 문제였다. 케이스는 두 가지, 여벌 옷을 가져왔는데 가져온 애가 도난 당하 경우와 여벌 옷 가져온 애가 도난 당하지 않고 다른 애에게 옷을 빌려주는 경우. answer의 초기 값은 lost 배열에 포함되지 않은 수로 지정한다.

이중 for문 안에서 만약 도난 당한 애가 여벌 옷을 가지고 온 애라면 그 애는 체육복을 입을 수 있으니까 answer++하고 여벌 옷을 가지고 있는 친구의 인덱스에 해당하는 reserve와 lost 모두 -1로 표시하고 이중 for문에서 탈출하면 된다. 만약 여벌 옷을 가지고 있는 애가 도난 당한 애 앞이나 뒤에 있다면 answer++하고, 여벌 옷이 있던 친구는 다른 친구한테 체육복을 빌려줬으니 -1로 더 빌려줄 수 없다는 표시를 하고 break로 이중 for문을 탈출하면 된다.

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {      
        
        Arrays.sort(reserve);
        Arrays.sort(lost);
        
        int answer = n-lost.length; // 도난 당하지 않은 학생 수
        // 도난 당해서 빌려줄 수 없는 경우
        for(int i = 0; i < lost.length; i++){
            for(int j = 0; j < reserve.length; j++){
                if(lost[i] == reserve[j]){
                    answer++; // 여분 옷을 가지고 있지만 도난 당한 학생 더하기
                    lost[i] = -1; // 이미 이 숫자에 대해서는 탐색 끝났으니 -1로 두 번째 for문 탈출
                    reserve[j] = -1;
                    break;
                }
            }
        }
        
        for(int i = 0; i < lost.length; i++){
            for(int j = 0; j < reserve.length; j++){
                if(lost[i] - 1 == reserve[j] || lost[i] + 1 == reserve[j]){ // 만약 lost의 하나 뒤의 값이나 앞의 값이 reserve 내에 있는 값이라면
                    answer++; // 빌려줄 수 있고
                    reserve[j] = -1; // 해당 reserve의 값은 체육복을 빌려줬으니 더 빌려줄 수 없어서 탐색 종료
                    break; // 두 번째 for문 탈출
                }
            }
        }
        
        return answer;
    }
}

 

맞출 수 있었는데 시간이 없었어서 아숩다 ^^