TIL (2022.01.29)

➕ 오늘 푼 문제

프로그래머스 - 체육복

➕ Java 코드

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        // 반복문을 이용해 int 배열을 리스트로 바꿈
        List<Integer> retainList = new ArrayList<>();
        List<Integer> lostList = new ArrayList<>();
        List<Integer> reserveList = new ArrayList<>();
        
        for(int i : lost){
            lostList.add(i);
            retainList.add(i);
        }
        for(int i : reserve){
            reserveList.add(i);
        }
        
        // 여분이 있는 학생이 도난 당한 경우 제거
        retainList.retainAll(reserveList);
        lostList.removeAll(retainList);
        reserveList.removeAll(retainList);
        
        // 왼쪽에 있는 학생을 우선해서 제공하기 위해 정렬
        Collections.sort(reserveList);
        
        for(int i : reserveList){
            int leftIndex = lostList.indexOf(i - 1);
            int rightIndex = lostList.indexOf(i + 1);
            
            if(leftIndex > -1){ // 왼쪽 학생을 빌려주는 경우
                lostList.remove(leftIndex);
            }else if(rightIndex > -1){  // 오른쪽 학생을 빌려주는 경우
                lostList.remove(rightIndex);
            }
        }
        
        return n - lostList.size();
    }
}

• Java에서의 집합 연산과 Python에서의 집합 연산이 달라서 애를 먹었다. 이 알고리즘에서 간과하기 쉬운 부분은 리스트가 정렬되어 있어야 한다는 점이다. 정렬된 상태에서 왼쪽, 오른쪽을 비교해 왼쪽 학생을 우선적으로 빌려주는 것이 그 상황에서 최선의 선택이다.
  • Java의 경우 ArrayList를 이용해 차집합 개념을 구현했는데, 이 경우에는 리스트가 정렬되지 않기 때문에 따로 정렬 연산이 필요하다.
  • 이 문제점을 발견하게 한 테스트 케이스는 아래와 같다.
    n=6, lost=[6,2,4], reserve=[1,5,3] -> answer: 6

➕ Python 코드

def solution(n, lost, reserve):
    # 여분 체육복이 있는데 도난 당한 경우 제거
    set_lost = set(lost) - set(reserve)
    set_reserve = set(reserve) - set(lost)
    
    for i in set_reserve:
        if i-1 in set_lost:  # 왼쪽 학생을 빌려주는 경우
            set_lost.remove(i-1)
        elif i+1 in set_lost: # 오른쪽 학생을 빌려주는 경우
            set_lost.remove(i+1)
    
    return n - len(set_lost)

• Python에서 집합 연산을 하면, 숫자의 경우 정렬이 된다. 자동적으로 정렬이 되기 때문에 파이썬 코드에서 따로 정렬 연산을 수행하지 않아도 된다. (이 부분 때문에 자바로 변환하는 데 어려움을 겪었다.)

➕ 궁금한 내용 및 소감

• 아직은 자바 문법에 익숙하지 않아, 자바 코드로 구현 하는데 애를 먹었다. 파이썬으로 우선 알고리즘을 구상해보고 이를 자바로 바꾸는 방식이 더 편한 것 같다.
• Java
  • 프로그래머스에서는 인자를 배열로 넘겨주는 데, 자바의 경우 배열이 기본적으로 제공하는 함수가 많이 없어서 힘들다. 이번에는 리스트로 바꿔서 구현을 해봤는데 더 좋은 방법이 있는 지 알아봐야겠다.
  • 집합 연산에 대해서도 파이썬에 비해 사용 방식이 복잡한 것 같다. 더 나은 방법을 찾아보자!

➕ 참고 문헌

• int 배열을 List로 변환하기
  • 참고 링크: [Java] int 배열을 List로 변환하기
• ArrayList 정렬하기
  • 참고 링크: [Java] ArrayList 정렬하기 (오름차순, 내림차순, 사용자 정의)
• List에 특정 값이 포함되어 있는지 확인하기
  • 참고 링크: [Java] List에 특정 값이 포함되어 있는지 확인하기
• ArrayList, List에서 부분집합, 교집합, 차집합, 합집합 구현하기
  • 참고 링크: [Java] 자바 ArrayList, List의 교집합, 부분집합, 차집합, 합집합 구하는 방법 총정리