프로그래머스_체육복 JAVA

프로그래머스

이번에 풀 문제는 '체육복'이다.

이미 과거에 풀었던 문제라 과거 코드가 남아있다.

 

과거 코드

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length; 
        
        List<Integer> list = new ArrayList<>();
        
        for(int l : reserve) {
            list.add(l);
        }
        
        for(int i = 0; i < lost.length; i++) {
            for(int j = 0; j < list.size(); j++) {
                if(lost[i] == list.get(j)) {
                    list.remove(j);
                    lost[i] = -1;
                    answer++;
                }
            }
        }
        
        for(int i = 0; i < lost.length; i++) {
            for(int j = 0; j < list.size(); j++) {
                if(lost[i] - 1 == list.get(j) || lost[i] + 1  == list.get(j)) {
                    list.remove(j);
                    answer++;
                    break;
                }
            }
        }
        return answer;
    }
}

과거에는 이중for문을 두 번 사용했었다.

왜 이렇게 짰는지는 지금 보면 전혀 모르겠다.

 

현재 코드

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        int[] result = new int[n+1];
        result[0] = -1;

        Arrays.sort(lost);

        for(int num : reserve) {
            if(!isContains(lost, num)) result[num] = 1;
        }
        
        for(int num : lost) {
            if(num < 0) continue;
            int prev = num - 1 <= 0 ? 1 : num - 1;
            int next = Math.min(num + 1, n);

            if(result[prev] == 1) {
                result[prev] = 0;
                result[num] = 0;
            } else if(result[next] == 1) {
                result[next] = 0;
                result[num] = 0;
            } else {
                result[num] = -1;
                answer--;
            }
        }
        
        return answer;
    }
    
    public static boolean isContains(int[] lost, int num) {
        for(int i = 0; i < lost.length; i++) {
            if(lost[i] == num) {
                lost[i] = -1;
                return true;
            }
        }
        return false;
    }
}

 

과거 코드보다.. 코드는 더 길어졌다.

이중for문을 최대한 없애보려고 노력했는데 좋은 코드인지는 모르겠다.

lost, reserve 배열을 삭제하는 등의 연산은 최대한 지양했다.

사실 이중for문만 없애고 list등의 삭제 연산 등등 오래 걸릴 것 같은 로직을 변경만한거지

확실하게 성능이 개선된건지는 잘 모르겠어서.. ChatGPT한테 코드 주고 물어봤다.

첫 번째 코드가 과거 코드이고 두 번째 코드가 현재 코드이다.

두 번째 코드가 길지만.. 성능이 더 좋긴 좋다고 한다.

더 나은 코드가 있냐고 물어보니 'Set' 자료구조를 이용하면 된다고 한다.

 

Set을 사용한 코드

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 num : lost) lostSet.add(num);
        for(int num : reserve) {
            if(lostSet.contains(num)) {
                lostSet.remove(num);
            } else {
                reserveSet.add(num);
            }
        }

        for(int num : new HashSet<>(lostSet)) {
            if(reserveSet.contains(num - 1)) {
                reserveSet.remove(num - 1);
                lostSet.remove(num);
            } else if (reserveSet.contains(num + 1)){
                reserveSet.remove(num + 1);
                lostSet.remove(num);
            }
        }

        return n - lostSet.size();
    }
}

Set을 사용하면 contains(),  remove().. 즉, 탐색과 삭제가 평균 O(1)로 수행되어 빠른 속도로 문제를 풀 수 있다.

Set 자료구조는 단순히 중복 방지인줄만 알았고 그렇게만 써왔었다.

int 배열에는 contains()를 사용할 수 없어 관련 메서드를 따로 만들었었는데.. Set을 사용하면 간단히 끝낼 수 있는 문제여서 놀랐다.

Set은... 탐색과 삭제가 O(1) ! 외우자.

 

 

오늘도 즐거운 코오딩