[Algorithm] 프로그래머스_체육복(JAVA)

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

프로그래머스

---

reverse와 lost를 정렬한다. 

answer의 초기값을 n-lost.length로 설정한다. 

이중 포문을 사용하여 reverse와 lost가 겹치는 학생 번호가 있다면 해당 배열에 -1을 대입한다. 

이후 reverse+1 또는 reverse-1이 lost에 존재한다면 answer++를 해주고 lost와 reserve에 -1을 대입한다.

 

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

 

이제 코드를 최적화 해보자...

이중포문 때문에 불필요한 탐색이 추가되어 위 코드의 실행시간은 0.32ms이다.

 

set을 사용하여 불필요한 이중포문을 없애보자.

배열을 사용하면 요소를 찾기 위해 순차 검색을 해야하므로 시간복잡도가 O(n)이지만 

Set은 해시 테이블을 사용하여 직접적으로 해시 값을 찾아가기 때문에 검색 시간이 O(1)에 가깝다.

 

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> lostSet = new HashSet<>();
        Set<Integer> reserveSet = new HashSet<>();
        
        for(int r : reserve){
            reserveSet.add(r);
        }
        for(int l : lost){
            if(reserveSet.contains(l)){
                reserveSet.remove(l);
            }else{
                lostSet.add(l);
            }
        }
        
        for(int r : reserveSet){
            if(lostSet.contains(r-1)){
                lostSet.remove(r-1);
            }else if(lostSet.contains(r+1)){
                lostSet.remove(r+1);
            }
        }
        
        return n - lostSet.size();
    }
}

최적화된 코드 실행 시간은 0.06ms로 확인되었다!

 

훨씬 간결해진 코드를 볼 수 있다.