[자바] 프로그래머스 - 체육복 [코딩테스트 연습 Lv1]

문제 : programmers-체육복

 

1. '여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.' 부분부터 처리해야 한다. lost와 reserve에 동시에 포함되는 항목이 있다면 양쪽에서 제거해서, '2' 이후의 로직에 영향을 끼치면 안된다.

 

2. +-1인 학생한테 체육복을 빌릴 수 있으므로 무지성으로 lost 기준으로 +-1 학생한테 빌릴 수 있으면 바로 빌리고, reserve에서 제거하면 된다. 뭐 오름차순으로 -1인 학생부터 빌리고 이런 과정이 필요 없다. 

  만약 +-2 이상으로 빌릴 수 있었다면 누가 누구한테 빌리는지에 따라 빌릴 수 있는 학생의 수가 변경될 것이므로 Level 1이 아니고, 최소 4 이상이 됬을 것이다. 이 경우엔 네트워크 플로우로 최대유량 구해서 푸는게 정해로 생각된다. 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    private int[] order = {-1, 1};
    public int solution(int n, int[] lost, int[] reserve) {
        n-=lost.length;
        int[] lostNum = new int[31];
        for (int i = 0; i < lost.length; i++) lostNum[lost[i]] = 1;
        int[] chk = new int[32];
        for (int i = 0; i < reserve.length; i++) chk[reserve[i]] = 1;
        for (int i = 0; i < 31; i++) if (lostNum[i]*chk[i]==1) {n++; lostNum[i]=chk[i]=0;}
        for (int i = 0; i < 31; i++) {
            if (lostNum[i]!=1) continue;
            for (int j = 0; j < 2; j++) {
                if (chk[i+order[j]]==1) {
                    chk[i+order[j]]--;
                    n++;
                    break;
                }
            }
        }
        return n;
    }
}