(Java) 프로그래머스 체육복

프로그래머스 1단계 체육복 문제이다.

다른 1단계들 보다 확실히 어렵다는 생각이 들었다.

 

그리디 알고리즘을 이용해서 해결하는 문제로 분류되어 있는데

그리디 알고리즘이란 어떤 것을 결정할 때 그 순간에서 가장 좋아 보이는 것을 선택하는 것이다.

일반적인 문제 상황에서는 그리디 알고리즘을 이용하는것이 최적의 해결방안은 아니나

코딩 테스트에서는 출제자가 그리디 알고리즘을 이용하면 그것이 최적의 해가 보장되게 출제한다고 한다.

 

---

처음 작성한 코드

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
    // 체육복을 상태를 나타내기 위한 배열 만들기
	int[] temp = new int[n];
	
	// 체육복 도난 상태 등록
	for(int i : lost) {
		temp[i - 1]--;
	}
	
	System.out.println("도난상태 : " + Arrays.toString(temp));
	
	// 여분의 체육복 상태 등록
	for (int i : reserve) {
		temp[i - 1]++;
	}
	
	System.out.println("여분상태 : " + Arrays.toString(temp));
	
	//
	for(int i=0; i<temp.length; i++) {
		// 체육복을 도난 당했으면
		if(temp[i] < 0) {
			// 뒷번호 사람의 체육복을 빌림
			if(i != temp.length - 1 && temp[i + 1] > 0) {
				temp[i]++;
				temp[i + 1]--;
			}
			// 뒷번호에 여분의 체육복이 없으면 앞번호에서 빌림
			else if(i != 0 && temp[i -1] > 0){
				temp[i]++;
				temp[i - 1]--;
			}
		}
	}
	int answer = 0;
	
	for(int i=0; i<temp.length; i++) {
		if(temp[i] >= 0) {
			answer++;
			}
		}
        return answer;
    }
}

1. 체육복의 상태를 나타내기 위한 배열을 만든다.

2. 도난, 여분의 상태를 등록한다.

3. 채육복 교환

4. 최대의 값 구해서 answer로 반환

 

이렇게 작성해서 풀었다.

그런데 테스트 17부터 20이 통과가 안된다...

아무리 생각해봐도 왜 통과가 안되는지 모르겠어서 다른분들 풀이를 참고해보았다.

---

두 번째 작성한 코드

import java.util.Arrays;
import java.util.HashSet;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
    
    // 반환값을 n으로 초기화
    int answer = n;
	
    // reserve와 lost 배열 초기화
	HashSet<Integer> rList = new HashSet<>();
	HashSet<Integer> lList = new HashSet<>();
	
    // reserve 배열 등록
	for (int i : reserve) {
		rList.add(i);
	}
	
    // lost 배열 등록하면서 체육복 교환
	for (int i : lost) { 
		if(rList.contains(i)) {
			rList.remove(i);
		}
		else lList.add(i);{
			}
		} 
	
    // 최대값 반환
	for (int i : lost) { 
			if(lList.contains(i)) { 
				if(rList.contains(i-1)) 
					rList.remove(i-1); 
				else if(rList.contains(i+1)) 
					rList.remove(i+1); 
				else answer--; 
				} 
			} 
        return answer;
    }
}

Hashset을 이용해서 풀이할 수 있었다.

그런데 이번에는 테스트 13, 14번에서 통과를 못했는데 찾아보니 lost나 reserve 입력값이 정렬이 되어 있지 않은

케이스가 있다고 한다.

---

마지막 정답 코드

import java.util.Arrays;
import java.util.HashSet;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
    
    // 반환값을 n으로 초기화
    int answer = n;
	
    // 정렬
    Arrays.sort(lost);
    Arrays.sort(reserve);	
    
    // reserve와 lost 배열 초기화
	HashSet<Integer> rList = new HashSet<>();
	HashSet<Integer> lList = new HashSet<>();
	
    // reserve 배열 등록
	for (int i : reserve) {
		rList.add(i);
	}
	
    // lost 배열 등록하면서 체육복 교환
	for (int i : lost) { 
		if(rList.contains(i)) {
			rList.remove(i);
		}
		else lList.add(i);{
			}
		} 
	
    // 최대값 반환
	for (int i : lost) { 
			if(lList.contains(i)) { 
				if(rList.contains(i-1)) 
					rList.remove(i-1); 
				else if(rList.contains(i+1)) 
					rList.remove(i+1); 
				else answer--; 
				} 
			} 
        return answer;
    }
}

 

세 번의 시도 끝에 모든 케이스를 통과할 수 있었다.

 

아직 갈 길이 멀구나...