[Programmers] Lv1_체육복 (JAVA)

💻JAVA 코드 바로보기

 

 

□문제 설명

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

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

 

---

 

□제한사항

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

---

□입출력 예

n	lost	reserve	return
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명이 체육수업을 들을 수 있습니다.

 

 

---

🌼JAVA 알고리즘

 

□초기화면

 

 

[참고]
탐욕법(Greedy)이란?
velog.io/@mkitigy
매 선택에서 최적의 결과를 만들어내는 것.

 

 

 

 

 

 

□풀이과정

reserve를 그대로 복사한 ArrayList를 만들고, 체육복은 우선 모두가 입을 수 있다고 가정한다. 1) 여벌옷이 없는 학생이 도난당했을 때, 앞뒤번호가 여벌옷이 없을 때(List에 존재하지 않을 때) 체육복을 입을 수 없기에 answer--를 진행한다. 만약 앞뒤번호 둘 중 하나라도 있다면, 해당 번호를 List에서 제외하여 여벌옷을 가진 명단에서 뺀다. 2) 여벌옷이 있는 학생이 도난당했을 때, 학생의 번호를 List에서 제외하여 여벌옷을 가진 명단에서 뺀다.

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<reserve.length;i++){
            list.add(reserve[i]);
        }
        
        for(int i=0;i<lost.length;i++){
            //여벌옷이 있는 학생이 도난당했을 경우
            if(Arrays.asList(lost[i]).contains(reserve)){
                list.remove(Integer.valueOf(lost[i]));
            }
            //여벌옷이 없는 학생이 도난당했을 경우
            else{
                boolean check = Arrays.asList(lost[i]-1).contains(reserve);
                int reserve_number = lost[i]-1;
                if(!check){
                    System.out.println("-1에게 없어서 +1번한테 확인");
                    check = Arrays.asList(lost[i]+1).contains(reserve);
                    reserve_number = lost[i]+1;
                }
                
                System.out.println("배열존재여부 : "+check);
                //빌릴 수 있으면
                if(!check) list.remove(reserve_number);
                //빌릴 수 없으면
                else answer--;
            }
        }
        
        return answer;
    }
}

코드가 조금 복잡해보이지만, 위의 설명대로 ArrayList에 값이 있는지 확인하고, 제거하는 과정을 코드로 만들었다. 잃어버린 명단에 i번 학생이 있는지 검사할 때,  체육복을 빌려줄 학생(i+1,i-1)이 여벌옷 명단에 있는지 검사할 때 List에 번호가 있는지 검사하는 메소드 Arrays.asList(00).contains(00)를 사용했는데, 뜻대로 실행되지 않았다.

Arrays.asList(00).contains(00)를 좀 더 알아보니 괄호 안의 값은 찾고싶은 '값' 이 아닌 원하는 '인덱스'가 존재하는지 검사하는 메소드였다. (에러발생이유) 따라서 괄호 안의 값을 Integer.valueOf(00)로 바꾸어 원하는 '값'을 찾도록 바꾸어보았다.

        for(int i=0;i<lost.length;i++){
            //여벌옷이 있는 학생이 도난당했을 경우
            if(Arrays.asList(Integer.valueOf(lost[i])).contains(reserve)){
                list.remove(Integer.valueOf(lost[i]));
            }
            //여벌옷이 없는 학생이 도난당했을 경우
            else{
                boolean check = Arrays.asList(Integer.valueOf(lost[i]-1)).contains(reserve);
                System.out.println(check);
                int reserve_number = lost[i]-1;
                if(!check){
                    System.out.println("-1에게 없어서 +1번한테 확인");
                    check = Arrays.asList(Integer.valueOf(lost[i]+1)).contains(reserve);
                    reserve_number = lost[i]+1;
                }
                
                System.out.println("배열존재여부 : "+check);
                //빌릴 수 있으면
                if(!check) list.remove(Integer.valueOf(reserve_number));
                //빌릴 수 없으면
                else answer--;
            }
        }
        
        return answer;
    }
}

여러 방법을 사용해봤지만 특정 값이 들어있는 list요소만 삭제하고, 있는지 판별하는 것이 잘 되지 않아서 아예 ArrayList를 사용하지 않고, 배열 그 자체를 사용하는 방법으로 바꾸어보았다.

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
                
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                //여벌옷이 있는 학생이 도난당했을 경우
                if(lost[i]==reserve[j]){
                    reserve[i]=-1;
                    lost[i]=-1;  //빌릴 필요가 없음
                    break;
                }
                answer--;
            }
        }
            
            
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                //여벌옷이 없는 학생이 도난당했을 경우
                System.out.println(lost[i]+"번 검사중");
                if(lost[i]-1==reserve[j]){
                    reserve[j]=-1;
                    System.out.println("-1번에게 빌릴 수 있음");
                    break;
                }
                else if(lost[i]+1==reserve[j]){
                    System.out.println("+1번에게 빌릴 수 있음");
                    reserve[j]=-1;
                    break;
                }
                System.out.println("빌릴 수 없음");
                answer--;
            }
        }
               
        
        return answer;
    }
}

 

이상해.....

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        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]){
                    reserve[i]=-1;
                    lost[i]=-1;  //빌릴 필요가 없음
                    answer++;
                    break;
                }
            }
        }
            
            
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                //여벌옷이 없는 학생이 도난당했을 경우
                if(lost[i]-1==reserve[j]){
                    reserve[j]=-1;
                    answer++;
                    break;
                }
                else if(lost[i]+1==reserve[j]){
                    reserve[j]=-1;
                    answer++;
                    break;
                }
            }
        }
               
        
        return answer;
    }
}

실행 결과는 맞았지만, 채점을 돌려보니 대부분의 경우가 런타임 에러가 발생해서 비슷한 알고리즘으로 짜신 분에게 쪼오금.. 도움을 받아보았다 🔗콩이의 개발블로그 코드 차이점이 answer = n-lost.length를 먼저 하고 변수 2개를 따로 주는게 아닌 answer++를 한것밖에 없는데.. 런타입 에러가 생긴 이유는 멀까..

 

 

 

 

 

□완성 코드

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int count1 = 0;
        int count2 = 0;
        
        for(int i=0; i<lost.length; i++) {
            for(int j=0; j<reserve.length; j++) {
                //여벌옷이 있는 학생이 도난당했을 경우
                if(lost[i]==reserve[j]) {
                    reserve[j] = -1;
                    lost[i] = -1; //빌릴 필요 없음
                    count1++;
                    break;
                }
            }
        }
        
        for(int i=0; i<lost.length; i++) {
            for(int j=0; j<reserve.length; j++) {
                //여벌옷이 없는 학생이 도난당했을 경우
                if(lost[i]==reserve[j]+1 || lost[i]==reserve[j]-1) {
                    reserve[j] = -1;
                    count2++;
                    break;
                }
            }
        }
        answer = n - lost.length + count1 + count2;
        
        return answer;
    }
}

 

 

 

 

 

 

 

---

□링크

코딩테스트 연습 - 체육복

 

About Me