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

1. 문제

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

코딩테스트 연습 - 체육복

2. 접근방법

프로그래머스 그리디 1번문제

 

우선 문제 자체에 설명이 부실하다 생각했는데

n명이라면 번호도 1~n번 이라는 조건을 넣어주면 좋지 않았나 생각한다.

 

 

* 풀이 방법

이 문제에서 고민해야 하는 부분은

 체육복을 빌릴 때 오른쪽 친구한테 빌릴 것인지 왼쪽 친구한테 빌릴 것인지이다.

 

위 경우에 3번 친구가 2번 친구에게 빌리는 경우

1번 친구는 체육복을 빌리지 못하게 되고

3번 친구가 4번 친구에게 빌리는 경우

1번 친구도 체육복을 빌릴 수 있게 된다.

 

떠오르는 풀이로 dps를 이용해 왼쪽 친구한테 먼저 빌려보고 그 다음 오른쪽 친구에게 빌려보는

완탐을 생각해 볼 수 있지만 n이 31로 2^31이 되니 불가능 하다.

 

사실 해결방법은 단순한데

1번부터 시작하면 왼쪽친구한테 먼저 빌려보고

끝번부터 시작하면 오른쪽친구한테 먼저 빌려보는식으로 풀이하면

가능한 많은 인원이 옷을 빌릴 수 있게 된다.

이미 지나온 번호의 친구들은 할 수 있는 한으로 해결이 다 된 상태이기 때문에 지나온 번호한테 먼저 빌리게 되면

겹쳐서 빌리는 경우를 최소화 할 수 있기 때문이다.

 

 

코드는

인덱스 처리를 위해 n+2 번까지 옷 유무를 저장하는 배열을 만들고

lost배열에 있는 번호는 -1

reserve 배열에 있는 번호는 +1을 해둔다.

 

그러면 0은 본인의 체육복을 가지고 있는 사람

-1은 빌려야하는 사람 1은 여유분을 가진 사람을 의미하게 된다.

 

answer는 사람의 수 n으로 초기화 해두고 -1인 친구가 옷을 빌리지 못하는 경우 - 해주는 식으로 구한다.

옷을 빌리는 로직으로

1번 친구부터 시작하여 30번친구까지 돌며

 

-1인 친구를 만나면

왼쪽친구가 1인지 확인하고

맞다면 왼쪽친구 -1 현재친구 +1

아니라면 오른쪽친구를 확인

1이라면 오른쪽 -1 현재 +1

두 친구 다 여유분이 없다면 옷을 못 빌렸으므로 answer --

모든 번호를 다 확인한 뒤 answer를 리턴 해주면 된다.

3. 자바 코드

public class Solution {

	public int solution(int n, int[] lost, int[] reserve) {
		int answer = n;
		int clothes[] = new int[n+2];
		for (int i : lost)
			clothes[i]--;
		for (int i : reserve)
			clothes[i]++;
		for (int i = 1; i < n+1; i++) {
			if (clothes[i] == -1)
				if (clothes[i - 1] == 1)
					clothes[i - 1] = clothes[i] = 0;
				else if (clothes[i + 1] == 1)
					clothes[i + 1] = clothes[i] = 0;
				else
					answer--;
		}
		return answer;
	}

}

4. 마치며

그리디 문제는 푸는 것보다 설명하는게 훨씬 어려운 것 같다.