잡다한 배똥월드

728x90
코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가? O
본인의 실력으로 풀었는가? O

 

 

코딩테스트 연습 - 체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번

programmers.co.kr

 

 

 

 

 

import java.util.*;

class Solution {
    
    int[] check;
    int answer = 0;
    
    public int solution(int n, int[] lost, int[] reserve) {
        check = new int[n+1];
        Arrays.fill(check, 1);
        
        for (int i = 0; i < lost.length; i++) {
            check[lost[i]]--;
        }
        
        for (int i = 0; i < reserve.length; i++) {
            check[reserve[i]]++;
        }
        
        for (int i = 1; i <= n; i++) {
            if (check[i] > 0) answer++;
        }
        
        func(0, answer);
        
        return answer;
    }
    
    public void func(int position, int num) {
        answer = Math.max(answer, num);
        
        for (int i = position; i < check.length; i++) {
            if (check[i] != 2) continue;
                        
            if (i-1 > 0 && check[i-1] == 0) {
                check[i-1]++;
                check[i]--;
                func(i+1, num+1);
                check[i-1]--;
                check[i]++;
            }
            
            if (i+1 < check.length && check[i+1] == 0) {
                check[i+1]++;
                check[i]--;
                func(i+1, num+1);
                check[i+1]--;
                check[i]++;
            }
        }
    }
}

 

테스트 1 통과 (0.04ms, 72.6MB)
테스트 2 통과 (0.05ms, 71.4MB)
테스트 3 통과 (0.06ms, 74.8MB)
테스트 4 통과 (0.06ms, 74.1MB)
테스트 5 통과 (0.12ms, 74.9MB)
테스트 6 통과 (0.03ms, 75.7MB)
테스트 7 통과 (0.05ms, 79MB)
테스트 8 통과 (0.04ms, 76MB)
테스트 9 통과 (0.04ms, 75.4MB)
테스트 10 통과 (0.04ms, 69.9MB)
테스트 11 통과 (0.04ms, 73MB)
테스트 12 통과 (0.03ms, 75.7MB)
테스트 13 통과 (0.06ms, 78.4MB)
테스트 14 통과 (0.04ms, 74.2MB)
테스트 15 통과 (0.05ms, 80MB)
테스트 16 통과 (0.03ms, 77.1MB)
테스트 17 통과 (0.06ms, 73.7MB)
테스트 18 통과 (0.03ms, 75.7MB)
테스트 19 통과 (0.03ms, 73.7MB)
테스트 20 통과 (0.03ms, 72MB)

 

 

 

 

 

여벌 옷을 가지고 있는 사람이 도난을 당했는지 안당했는지를 파악하는 것이 중요한 것 같음

 

 

 

 

 

탐욕법이 뭔지는 모르지만 정말 말 그대로 문제를 표현한 느낌.

 

 

 

 

 

728x90

+ Recent posts