[프로그래머스 고득점Kit] 0806 - 그리디

🔎 보충

배열 출력하기

System.out.print(Arrays.toString(people));

이차원 배열 정렬하기

// 두번째 요소기준 오름차순 정렬
Arrays.sort(routes,(a,b)->Integer.compare(a[1], b[1]));

---

📚 큰 수 만들기

방법1) Stack 활용

// Stack 활용 ver
public class Greedy0806_1 {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - 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();
                k--;
            }
            stack.push(c);
        }
        
        for (int i=0; i<result.length; i++) 
            result[i] = stack.get(i);
        
        
        return new String(result); // char[]을 String으로 리턴
    }
}

방법2) StringBuilder 활용

    public String solution(String number, int k) {
    	
        StringBuilder sb = new StringBuilder(number);
        
        for (int i = 0; i+1 < sb.length() && k>0; i++) {
            if(sb.charAt(i) < sb.charAt(i+1)) {
                sb.deleteCharAt(i);
                i=-1;
                k--;
            }
        }
        if(k!=0)
            sb.delete(sb.length()-k, sb.length());
        
        return sb.toString();
    }

📚 구명보트

	public int solution(int[] people,int limit) {
		
		int cnt=0;
		Arrays.sort(people);
        //System.out.print(Arrays.toString(people));
		
		int minIdx=0;
		int maxIdx = people.length-1;
		
		while(minIdx<=maxIdx) { // 50,70,80 같은 경우를 위해 '='필요
			if(people[minIdx]+people[maxIdx]<=limit) 
				minIdx++;
			
			maxIdx--;
            cnt++;
		}
		
		return cnt;
	}

📚 섬 연결하기(크루스칼 알고리즘)

public class Greedy0806_3 {
	
	public static int[] parent = new int[101];
	
	public int solution(int n,int[][] costs) {
		
		int answer=0;
		
		// 비용기준(세번째 요소) 오름차순 정렬 
		Arrays.sort(costs,(a,b)->Integer.compare(a[2], b[2]));
		
		// 처음에는 자기 자신을 부모로 초기화
		for(int i=0;i<n;i++)
			parent[i] = i;
		
		for(int[] edge:costs) {
			int from = edge[0];
			int to = edge[1];
			int cost = edge[2];
			
			if(findParent(from)!=findParent(to)) {
				unionParent(from,to);
				answer+=cost;
			}
			
		}
		
		return answer;
	}

	private void unionParent(int from, int to) {
		from = findParent(from);
		to = findParent(to);
		if(from<to) parent[to] = from;
		else parent[from] = to;
		
	}

	private static int findParent(int x) {
		if(x==parent[x]) return x;
		return parent[x] = findParent(parent[x]);
	}
}

📚 단속 카메라

	public int solution(int[][] routes) {
		
		// 진출시간 기준 오름차순 정렬
		Arrays.sort(routes,(a,b)->Integer.compare(a[1], b[1]));
		
		int answer=0;
		int camera = -30000; // 문제 제한사항 중 최소 진입지점이 -30000
		
		for(int[] r:routes) {
			if(camera<r[0]) { // 카메라가 진입점 밖에 있다면
				answer++;	
				camera=r[1];	// 진출점 갱신
								// 진출점으로 지정해야 다음 루트의 진입점과 비교하기 쉬움
			}
		}
		
		return answer;
	}