[프로그래머스] Lv1. 체육복 - Java

syeony·2025년 6월 18일
0

Java

목록 보기
18/19

문제 바로가기

접근방식

그냥 이중for문 돌려서 lost랑 reserve-1, reserve+1인거 겹친거 빼가면서 answer++해주면 될거라 생각했다. 그런데 반례를 생각하지 못했다. lost사람이랑 reserve사람이랑 겹칠경우가 있을 수 있었다.

반례생각못한 틀린코드

import java.io.*;
import java.util.*;

class 체육복 {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n-lost.length;
        Arrays.sort(lost);
        Arrays.sort(reserve);

        for(int i=0;i<reserve.length;i++){
            for(int j=0;j<lost.length;j++){
                if(reserve[i]-1==lost[j] || reserve[i]+1==lost[j]){
                    answer++;
                    lost[j]=-100;
                    reserve[i]=-200;
                }
            }
        }
        return answer;
    }
}

정답코드

반례 ...

그래서 lost와 reserve에서 겹치는 수 먼저 빼줘야한다.

import java.io.*;
import java.util.*;

class 체육복 {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n-lost.length;
        Arrays.sort(lost);
        Arrays.sort(reserve);

        //반례(도난당한사람이랑 여분있는사람이 같을때)
        //예 n=5, lost[2,3], reserve[1,2]
        for(int i=0;i<reserve.length;i++){
            for(int j=0;j<lost.length;j++){
                if(reserve[i]==lost[j]){
                    answer++;
                    reserve[i]=-200;
                    lost[j]=-100;
                }
            }
        }

        for(int i=0;i<reserve.length;i++){
            for(int j=0;j<lost.length;j++){
                if(reserve[i]-1==lost[j] || reserve[i]+1==lost[j]){
                    answer++;
                    lost[j]=-100;
                    reserve[i]=-200;
                }
            }
        }
        return answer;
    }
}

후기

그리디는 항상 까다롭다...
맨날 탐색 문제만 풀다가 이런 문제 만나면 당혹..
연습해야겠다

profile
모바일 어플리케이션, cross platform과 iOS에 관심이 많은 개발자 오승연입니다

0개의 댓글