프로그래머스 - 체육복(그리디)

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

프로그래머스

 

프로그래머스 체육복 문제입니다.

금방 풀 줄 알았는데 테스트 케이스 하나 떄문에 생각보다 오래 걸렸네요..

첫번 째 풀이(테스트 케이스 12 번 제외 모두 통과)

테스트 케이스 12번만 계속해서 실패해서 대체 뭐가 문제야 생각했는데 예외 케이스를 하나 찾았습니다.

n = 3, lost = {1,2}, reserve = {2,3} 이런식으로 하게 되면 정답은 2가 나와야 하는데 lost 1을 먼저 처리한 후 2번으로 가기때문에 3이 되어 버리더라구요..

그래서 이 문제의 경우에는 체육복의 여벌도 보유하고 있지만 도난을 당한 케이스를 먼저 제거해주어야 합니다

그 후에 검사를 해야 올바른 정답을 도출할 수 있습니다.

class Solution {
        public int solution(int n, int[] lost, int[] reserve) {
            int answer = n-lost.length;
            int count = 0;

            for(int i=0; i<lost.length; i++){
                for(int j=0; j<reserve.length; j++){
                    if(reserve[j] == lost[i]){
                        reserve[j] = -1;
                        lost[i] = -1;
                        count++;
                        break;
                    } else if(reserve[j] == lost[i]-1) {
                        reserve[j] = -1;
                        count++;
                        break;
                    } else if (reserve[j] == lost[i]+1) {
                        reserve[j] = -1;
                        count++;
                        break;
                    }
                }

            }
            answer += count;

            return answer;
        }
    }

 

정답 코드

정답 코드에서는 먼저 체육복의 여벌을 가지고 있는 동시에 도난을 당하는 번호들을 모두 제거해줍니다.

그 후에 검사를 진행하게 되면 정답이 도출됩니다.

package com.company;

import java.util.ArrayList;
import java.util.Arrays;

public class gymclothes {
    static class Solution {
        public int solution(int n, int[] lost, int[] reserve) {
            int answer = n-lost.length;
            int count = 0;

            for(int i=0; i<lost.length; i++){
                for(int j=0; j<reserve.length; j++){
                    if(reserve[j] == lost[i]){
                            reserve[j] = -1;
                            lost[i] = -1;
                            count++;
                            break;
                    }
                }
            }

            for(int i=0; i<lost.length; i++){
                for(int j=0; j<reserve.length; j++){
                    if(reserve[j] == lost[i]-1 || reserve[j] == lost[i]+1) {
                        reserve[j] = -1;
                        count++;
                        break;
                    }
                }

            }
            answer += count;

            return answer;
        }
    }
}