[프로그래머스] 탐욕법(Greedy) 체육복 (Java)

 

🔥DAY +3

 

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

 

코딩테스트 연습 - 체육복

 

 

> 문제 설명 보기

 

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예nlostreservereturn

5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

 

---

 

🔥 [로직]

1. 배열들 순차정렬

2. 여벌을 가져온 사람이 체육복을 도난당한 경우를 먼저 고려

(체육복을 빌려 줄 수 없는 상황이기 때문에 고려대상이 아니므로 배열에서 제거해줘야하기 때문)

 

(1) 체육복을 빌려 줄 수 없기 때문에 reserve값을 0으로 만들어준다. (2) 본인의 여벌 체육복을 입으면 되기 때문에 lost값도 0으로 만들어준다. (3) 잃어버렸지만 해결책을 찾았기 때문에 answer값 또한 증가

3. 그 외의 경우(여벌을 가져오지 않았는데 도난당한 경우 체크)

여벌을 가져온 사람이 도난당했는지 체크(reserve값이 0인 사람), 여벌이 있는 학생의 번호가 1이 차이나는지 체크

if((reserve[i] != 0) && ((num == reserve[i]-1) || (num == reserve[i]+1)))

 이 조건을 충족한 경우 더이상 빌려준 학생이 빌려줄 수 없기 때문에 값을 0으로 만들어준다. answer값 또한 1 증가!

 

🔥 [최종 코드]

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        int answer = n - lost.length;
        
        for(int j = 0; j < lost.length; j++) {
            for(int i = 0; i < reserve.length; i++) {
                if(lost[j] == reserve[i]) { //여벌을 가져온 사람이 체육복을 도난당한 경우
                    reserve[i] = 0;
                    lost[j] = 0;
                    answer++;
                    break;
                }
            }
        }
        
        for(int num : lost) {
            if(num == 0) continue;
            for(int i = 0; i < reserve.length; i++) {
                if((reserve[i] != 0) && ((num == reserve[i]-1) || (num == reserve[i]+1))){
                    reserve[i] = 0;
                    answer++;
                    break;
                }   
            }
            
        }
        return answer;
    }
}

 

🔥 [소감]

정말정말.. 오래걸렸다. 처음엔 테스트케이스 12,13,18에서 에러가 났는데 이건 여벌 체육복을 가진 학생이 도둑맞은 케이스를 고려하지 못해서 문제가 된거라 고치는데 오래 걸리진 않았는데 그 다음에 5,12 테스트케이스가 에러가 발생했다.

분명히 여벌 체육복도 고려하고.. 내가 로직을 따라갔을땐 분명 흠이 없어보이는데 예외 케이스가 뭔지 몰라서 한참을 헤맸다.ㅠㅠ

다른 사람들이 올려놓은 질문하기를 한참 보던 중 4, [3,1,2] [2,4,3] -> 3 테스트 케이스를 추가해보라는 조언을 봤다. 체크포인트를 찍어보면서 확인하다가 그제서야 원인을 찾게 되었당

 

> 문제가 되었던 기존 코드

 

//문제가 되었던 코드입니다. 정답 아님!

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        int answer = n - lost.length;
        
        for(int num : lost) {
            for(int i = 0; i < reserve.length; i++) {
                if(num == reserve[i]) { //여벌을 가져온 사람이 체육복을 도난당한 경우
                    reserve[i] = 0;
                    answer++;
                    System.out.println(i+"가 도난당해서 answer 증가");
                    break;
                }
                if((reserve[i] != 0) && ((num == reserve[i]-1) || (num == reserve[i]+1))){
                    System.out.println(reserve[i]+"가 "+num+"한테 빌려줌");
                    reserve[i] = 0;
                    answer++;
                    break;
                }   
            }
            
        }
        return answer;
    }
}

 

이 값들을 각각 정렬하면 lost = [1,2,3] , reserve = [2,3,4]가 되는데 기존의 코드에서는 정렬된 lost배열, reserve 배열을 순서대로 돌면서 1. 여벌을 가진 학생이 도둑 맞은 경우  2. 아닌 경우 빌릴 수 있는지의 여부를 한번에 체크해버리기 때문에 해당 케이스에서 2번 학생이 본인이 도둑맞았음에도 1에게 체육복을 빌려주는 참사가 발생한다. (결국 여벌을 고려하지 안한 코드가 되어버림 ㅠㅠ)

(이렇게 되면 안됨.)

 

문제를 꼼꼼히 읽고 우선순위를 파악하는 게 시간단축의 핵심인 것 같다! 

 

---

 

코테 준비를 본격적으로 시작한지 얼마 되지 않아 코드에 미흡한 점이 많을 수 있습니다. 
부족한 점 피드백 주시면 앞으로의 포스팅에 반영하겠습니다! 봐주셔서 정말 감사합니다 :)
-zelkova