[알고리즘] 프로그래머스 : 체육복

알고리즘 문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

 

---

내가 작성한 코드

자바에서 배열이 고지식하고 융통성이 없어서 좋아하지 않았는데 성능 측면에서는 ArrayList보다 배열이 더 빠르다고 하여 배열에 정을 붙이려고 노력하고 있다. 라이브러리도 곧잘 활용했지만 라이브러리 또한 무분별하게 사용하면 속도가 느려진다고 이야기가 들었다. 라이브러리는 편하지만 뭐든 적절하게 활용해야 하고 알고리즘에 있어서는 원시적인 방법이 속도가 빠르다.

각설하고 이 문제는 먼저 인자값으로 들어온 체육복을 잃어버린 학생과 여유분의 체육복을 가져온 학생들의 배열을 오름차순으로 정렬하고 시작한다. 그 뒤 반복문을 돌리는데 먼저 여유분의 체육복을 가져왔지만 체육복을 잃어버린 학생(reserve 배열과 lost 배열에 동시에 번호가 있는 학생)에 0을 저장한다. 그리고 체육복을 잃어버린 학생의 앞번호 학생이 여유분의 체육복을 가져왔으면 두 값에 모두 0을 저장하고, 그 뒤 체육복을 잃어버린 학생의 뒷번호 학생이 여유분의 체육복을 가져왔으면 두 값에 모두 0을 저장한다. 마지막으로 체육복을 잃어버린 학생의 배열에서 0이 아닌 개수(체육복을 받지 못해서 체육수업을 들을 수 없는 학생의 수)를 세고 전체 학생수 n에서 빼주면 체육 수업을 들을 수 있는 학생수가 나온다. 

import java.util.Arrays;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int count = 0;
        Arrays.sort(lost);
        Arrays.sort(reserve);
        for(int i=0; i<lost.length; i++){
            for(int j=0; j<reserve.length; j++){
                if(lost[i]==reserve[j]){
                    lost[i]=0;
                    reserve[j]=0;
                    break;
                }
            }
        }
        for(int i=0; i<lost.length; i++){
            for(int j=0; j<reserve.length; j++){
                if(lost[i]==0) break;
                else if(reserve[j]!=0 && lost[i]-1==reserve[j]){
                    lost[i]=0;
                    reserve[j]=0;
                    break;
                }
                else if(reserve[j]!=0 && lost[i]+1==reserve[j]){
                    lost[i]=0;
                    reserve[j]=0;
                    break;
                }
            }
        }
        for(int i=0; i<lost.length; i++){
            if(lost[i]!=0) count++;
        }
        answer = n-count;
        return answer;
    }
}

 

이렇게 코드를 짰더니 속도는 꽤 빠르게 잡혔다. 변수 저장과 관련하여 공간 복잡도는 좀 더 고민해봐야겠다.