체육복

Level 1

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
        Arrays.sort(lost);
        List<Integer> rList = Arrays.stream(reserve)                        
                                    .boxed()
                                    .collect(Collectors.toList());
        for(int i = 0; i < lost.length; i++) { 
        	int rInd = rList.indexOf(lost[i]);
        	if(rInd != -1) {	// 잃어버렸지만 여분이 있는 경우
                answer++;
                lost[i] = 0;	// 잃어버리지 않음으로 표시
                rList.set(rInd, -1);	// 여분없음으로 표시
            }
        }
        
        for(int l : lost) {
            if(l == 0) continue;	// 위에서 처리됨
            // 왼쪽에 여분이 있는지 확인
            int rInd = l > 1 ? rList.indexOf(l-1) : -1;
            // 오른쪽에 여분이 있는지 확인
            rInd = (rInd == -1 && l < n) ? rList.indexOf(l+1) : rInd;
            
            if(rInd != -1) {	// 빌릴 수 있는 경우
                answer++;
                rList.set(rInd, -1);
            }
        }
        
        return answer;
    }
}

조이스틱

Level 2

class Solution {
    public int solution(String name) {
        char[] arr = name.toCharArray();
        int change = 0;             // 알파벳 변경 최소 횟수
        int move = arr.length - 1;  // 이동 최댓값으로 초기화
        
        for(int i = 0; i < arr.length; i++) {
        	change += Math.min(arr[i] - 65, 91 - arr[i]);   // 대문자 65~90
        	
        	int index = i + 1;	// A가 연속으로 나오지 않기 시작하는 인덱스 찾기
        	while(index < arr.length && arr[index] == 'A') index++;
        	
        	move = Math.min(move, Math.min(i * 2 + (arr.length - index), 
                                           i + (arr.length - index) * 2));
        }
        return change + move;
    }
}

큰 수 만들기

Level 2

class Solution {
	// 스택
	 public String solution1(String number, int k) {
        Stack<Character> stack = new Stack<>();	// 남길 수 저장

        for (int i = 0; i < number.length(); i++) {
            char c = number.charAt(i);	// 비교 대상(앞자리 수)
            
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
            	// 비교 대상보다 작고, 아직 제거해야 될 경우, 스택에서 삭제
                stack.pop();	
            }
            stack.push(c);
        }
        
        char[] result = new char[number.length() - k];
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }
    
	// 투 포인터
    public String solution2(String number, int k) {
        int numLen = number.length();
    	StringBuilder sb = new StringBuilder(number);
    	int p = 1;	// 포인터
    	boolean flag = false;
        
    	while(sb.length() + k > numLen) {
    		char a = sb.charAt(p - 1);
    		char b = sb.charAt(p);
            
    		if(a >= b) {	// 앞자리 수가 더 큰 경우
    			if(sb.length() == p + 1) {	// 포인터가 맨끝으로 간 경우
    				sb.deleteCharAt(p);	// 작은 수 삭제
    			} else {	// 삭제 보류
    				p++;	// 뒷자리 수들 비교하도록 포인터 이동
    				flag = true;
    				continue;
    			}
    		} else { 	// 뒷자리 수가 더 큰 경우
				sb.deleteCharAt(p-1);	// 앞에 작은 수 삭제
				if(flag) p = 1;		// 초기화 -> 맨앞부터 다시 비교
    		}
            
    		if(sb.length() == p) p = 1;	// 포인터가 더이상 뒤로 이동할 수 없는 경우
    		flag = false;
    	}
    	
    	return sb.toString();
    }
}

구명보트

Level 2

• 투 포인터

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);	// 가벼운 사람부터 정렬
        int p1 = 0;  // 남아있는 가장 가벼운 사람 인덱스, 2명이 타는 경우의 수
        int p2 = people.length - 1;	// 남아있는 가장 무거운 사람 인덱스
        
        while(p1 < p2) {
            if(people[p1] + people[p2] <= limit) p1++;
            p2--;
        }
        return people.length - p1;
    }
}

섬 연결하기

Level 3

• 크루스칼 알고리즘 (최소 신장 트리)

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        List<int[]> sortedCosts = new ArrayList<>();
        Map<Integer, Integer> connected = new HashMap<Integer, Integer>();	// 연결 선 저장 
        
        for(int[] c : costs) {
            sortedCosts.add(c);
            // 아직 연결된 선이 없으므로, 본인을 가리키도록 설정
            connected.putIfAbsent(c[0], c[0]);
            connected.putIfAbsent(c[1], c[1]);
        }
        Collections.sort(sortedCosts, (a,b) -> a[2] - b[2]);	// 적은 비용부터 정렬
        
        for(int i = 0; i < costs.length; i++) {
            int edge1 = findEdge(connected, sortedCosts.get(i)[0]);
            int edge2 = findEdge(connected, sortedCosts.get(i)[1]);
            // 순환되지 않으면, 섬 연결
            if(edge1 != edge2) {
                if(edge1 < edge2) {	// key 큰 수 -> value 작은 수
                    connected.replace(edge2, edge1);
                } else {
                    connected.replace(edge1, edge2);
                }
                answer += sortedCosts.get(i)[2];	// 비용 추가
            }
        }
        
        return answer;
    }
    
    private int findEdge(Map<Integer, Integer> map, int start) {
    	// base case
        if(map.get(start) == start) return start;
        // recursive case
        map.replace(start, findEdge(map, map.get(start)));
        return map.get(start);
    }
}

단속카메라

Level 3

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        List<int[]> sortedRoutes = new ArrayList<>();
        
        for(int[] route : routes) {
            sortedRoutes.add(route);
        }
        Collections.sort(sortedRoutes, (a,b) -> a[1] - b[1]);   // 빨리 나가는 순서대로 정렬
        
        while(!sortedRoutes.isEmpty()) {
        	// 남은 경로 중 먼저 나가는 지점에 카메라 설치
            int camera = sortedRoutes.get(0)[1];
            
            for(int i = 0; i < sortedRoutes.size(); i++) {
            	// 위에서 설치한 카메라를 지나가는 경우
                if(sortedRoutes.get(i)[0] <= camera 
                	&& sortedRoutes.get(i)[1] >= camera) {
                    
                    sortedRoutes.remove(i);
                    i--;
                }
            }
            answer++;
        }
        return answer;
    }
}