본문 바로가기
프로그래머스/코딩연습1

[프로그래머스] 체육복(42862)(java)

by 유줘니 2019. 4. 30.

원본 문제 : https://programmers.co.kr/learn/courses/30/lessons/42862

 

문제 설명

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

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

제한사항

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

입출력 예

입출력 예

 

풀이 #1

import java.util.ArrayList;
import java.util.LinkedList;

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

//학생들의 체육복 유무 상태를 보관하는 student 객
class Student{
	boolean stolen;
	boolean reserve;
	
	public Student() {
		super();
		this.stolen = false;
		this.reserve = false;
	}
}

public class LESSON42862 {
	public static void main(String[] args) {
		int n = 3;
		int[] lost = {3};
		int[] reserve = {1};
		System.out.println(solution(n,lost,reserve));

	}
    public static int solution(int n, int[] lost, int[] reserve) {
        
    	//student 인스턴스를 순서대로 저장할 LinkedList 생성
        LinkedList<Student> list = new LinkedList<Student>();
        
        //Student를 차례대로 LinkedList에 삽입,
        //이때 student 인스턴스의 default는 모두 도난 당하지 않았고 여분이 없음
        for(int i = 0; i < n; i++) {
        	list.add(new Student());
        }
        
        //도난 당한 학생의 상태를 변경함
        //도난을 당하면서 여분이 있을 수 없음.
        for(int i = 0; i < lost.length ; i++) {
        	Student student = list.get(lost[i]-1);
        	student.stolen = true;
        	student.reserve = false;
        }
        
        //여분이 있는 학생의 상태를 변경함
        //여분이 있으면서 도난을 당한 상태는 없음
        for(int i = 0; i < reserve.length ; i++) {
        	Student student = list.get(reserve[i]-1);
        	student.stolen = false;
        	student.reserve = true;
        }

        //학생끼리 빌려주고 난 뒤 결과를 저장할 ArrayList를 새로이 생성
        ArrayList<Student> sort = new ArrayList<Student>();
        
        //첫 학생을 LinkedList에서 poll
        Student student = list.poll();
        while(!list.isEmpty()) {
        	//student 다음 학생을 poll
        	Student student_next = list.poll();
        	
        	//앞의 학생이 도난 상태이고, 뒤의 학생이 여분이 있을 경우
        	if(student.stolen==true && student_next.reserve==true) {
        		student.stolen=false;
        		student_next.reserve=false;
        		sort.add(student);
        		sort.add(student_next);
        		student = list.poll();
        	}
        	
        	//앞의 학생이 여분이 있고 뒤의 학생이 도난 상태일 경우
        	else if(student.reserve==true && student_next.stolen==true) {
        		student_next.stolen = false;
        		student.reserve = false;
        		sort.add(student);
        		sort.add(student_next);
        		student = list.poll();
        	}
        	//앞 뒤 학생이 서로 빌려줄 수 없는 관계인 경우
        	else {
        		sort.add(student);
        		student = student_next;
        	}
        }
        //마지막 학생을 ArrayList에 담음
        sort.add(student);
        
        //도난 당하지 않는 상태를 갖는 학생 수는 체육복을 가지고 있는 상태이므로 이를 카운트
        int count = 0;
        for(int i = 0; i < sort.size();i++) {
        	if(sort.get(i).stolen==false) {
        		count++;
        	}
        }
        return count;
    }
}

이렇게 코딩을 했지만, "입출력 예"에서는 모두 통과했지만 테스트 케이스에서 런타임 에러를 내뿜는다...

 

 

 

풀이 #2

import java.util.ArrayList;
import java.util.LinkedList;

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

//학생들의 체육복 유무 상태를 보관하는 student 객
class Student{
	int clothes;
	
	public Student() {
		super();
		this.clothes = 1;
	}
}

public class LESSON42862 {
	public static void main(String[] args) {
		int n = 3;
		int[] lost = {3};
		int[] reserve = {1};
		System.out.println(solution(n,lost,reserve));
	}
	
    public static int solution(int n, int[] lost, int[] reserve) {
        
    	//student 인스턴스를 순서대로 저장할 LinkedList 생성
        LinkedList<Student> list = new LinkedList<Student>();
        
        //Student를 차례대로 LinkedList에 삽입,
        //이때 student 인스턴스의 default는 모두 도난 당하지 않았고 여분이 없음
        for(int i = 0; i < n; i++) {
        	list.add(new Student());
        }
        
        //도난 당한 학생의 상태를 변경함
        for(int i = 0; i < lost.length ; i++) {
        	Student student = list.get(lost[i]-1);
        	student.clothes -= 1;
        }
        
        //여분이 있는 학생의 상태를 변경함
        for(int i = 0; i < reserve.length ; i++) {
        	Student student = list.get(reserve[i]-1);
        	student.clothes += 1;
        }

        //학생끼리 빌려주고 난 뒤 결과를 저장할 ArrayList를 새로이 생성
        ArrayList<Student> sort = new ArrayList<Student>();
        
        //첫 학생을 LinkedList에서 poll
        Student student = list.poll();
        while(!list.isEmpty()) {
        	//student 다음 학생을 poll
        	Student student_next = list.poll();
        	
        	//앞의 학생이 도난 상태이고, 뒤의 학생이 여분이 있을 경우
        	if(student.clothes == 0 && student_next.clothes > 1) {
        		student.clothes += 1;
        		student_next.clothes -= 1;
        		sort.add(student);
        		sort.add(student_next);
        		student = list.poll();
        	}
        	
        	//앞의 학생이 여분이 있고 뒤의 학생이 도난 상태일 경우
        	else if(student.clothes > 1 && student_next.clothes == 0) {
        		student.clothes -= 1;
        		student_next.clothes += 1;
        		sort.add(student);
        		sort.add(student_next);
        		student = list.poll();
        	}
        	
        	//앞 뒤 학생이 서로 빌려줄 수 없는 관계인 경우
        	//앞사람을 ArrayList로 넘김
        	else {
        		sort.add(student);
        		student = student_next;
        	}
        }
        //마지막 학생을 ArrayList에 담음
        sort.add(student);
        
        int count = 0;
        for(int i = 0; i < sort.size();i++) {
        	if(sort.get(i).clothes >= 1) count++;
        }
        return count;
    }
}

도난의 유무와 여분의 유부는 중요한 사항이 아니었다. 그냥 옷의 갯수가 제일 중요하다.

테스트 케이스 11번에서만 런타임 에러가 발생한다.

 

 

 

완성 #3

import java.util.ArrayList;
import java.util.LinkedList;

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

//학생들의 체육복 유무 상태를 보관하는 student 객
class Student{
	int clothes;
	
	public Student() {
		super();
		this.clothes = 1;
	}
}

public class LESSON42862 {
	public static void main(String[] args) {
		int n = 5;
		int[] lost = {2,4};
		int[] reserve = {3,5};
		System.out.println(solution(n,lost,reserve));
	}
	
    public static int solution(int n, int[] lost, int[] reserve) {
        
    	//student 인스턴스를 순서대로 저장할 LinkedList 생성
        LinkedList<Student> list = new LinkedList<Student>();
        
        //Student를 차례대로 LinkedList에 삽입,
        //이때 student 인스턴스의 초기값은 모두 옷이 한벌이다.
        for(int i = 0; i < n; i++) {
        	list.add(new Student());
        }
        
        //도난 당한 학생의 옷을 -1함
        for(int i = 0; i < lost.length ; i++) {
        	Student student = list.get(lost[i]-1);
        	student.clothes -= 1;
        }
        
        //여분이 있는 학생의 옷을 +1함
        for(int i = 0; i < reserve.length ; i++) {
        	Student student = list.get(reserve[i]-1);
        	student.clothes += 1;
        }

        //학생끼리 빌려주고 난 뒤 결과를 저장할 ArrayList를 새로이 생성
        ArrayList<Student> sort = new ArrayList<Student>();
        
        //첫 학생을 LinkedList에서 poll
        Student student = list.poll();
        while(!list.isEmpty()) {
        	//비교할 student 다음 학생을 poll
        	Student student_next = list.poll();
        	
        	//앞의 학생이 도난 상태이고, 뒤의 학생이 여분이 있을 경우
        	if(student.clothes == 0 && student_next.clothes > 1) {
        		student.clothes += 1;
        		student_next.clothes -= 1;
        		sort.add(student);
        		sort.add(student_next);
        		student = list.poll();
        	}
        	
        	//앞의 학생이 여분이 있고 뒤의 학생이 도난 상태일 경우
        	else if(student.clothes > 1 && student_next.clothes == 0) {
        		student.clothes -= 1;
        		student_next.clothes += 1;
        		sort.add(student);
        		sort.add(student_next);
        		student = list.poll();
        	}
        	
        	//앞 뒤 학생이 서로 빌려줄 수 없는 관계인 경우
        	//앞사람을 ArrayList로 넘김
        	else {
        		sort.add(student);
        		student = student_next;
        	}
        }
        //마지막 학생을 ArrayList에 담음
        //새로운 ArrayList의 사이즈가 전체 학생수를 초과하지 않도록
        if(sort.size()<n) sort.add(student);
        
        System.out.println(sort.size());
        
        int count = 0;
        for(int i = 0; i < sort.size();i++) {
        	if(sort.get(i).clothes >= 1) count++;
        }
        return count;
    }
}

테스트 케이스 11번의 반례이다.

n = 9 
lost = {2,4,7,8 }
reserve = {3,6,9}
answer = 8 

n = 5
lost = {2,4}
reserve = {3,5}
answer = 5

디버그를 하니 전체 학생수를 초과하여 sort(ArrayList)가 만들어져, 그렇게 되지 못하도록

if문으로 마지막 sort.add(student)로 잡았다.

'프로그래머스 > 코딩연습1' 카테고리의 다른 글

[프로그래머스] 쇠막대기(42585)(java)  (0) 2019.05.01
[프로그래머스] 탑(42588) (java)  (0) 2019.04.30
[프로그래머스] 기능개발(42586)(java)  (0) 2019.04.29
[프로그래머스] 실패율 (42889)(JAVA)  (0) 2019.04.25
[프로그래머스] 프린터(42587) (java)  (0) 2019.04.25

관련글

댓글

티스토리툴바