프로그래머스 자바 :: 탐욕법

 

체육복

 

 

 

 

 

 

 

내 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
                 
        HashSet<Integer> lostSet = new HashSet<>();
        HashSet<Integer> reserveSet = new HashSet<>();

        for(int reservePerson : reserve){
            reserveSet.add(reservePerson);
        }
        
        for(int lostPerson : lost){
            if(reserveSet.contains(lostPerson)){
                reserveSet.remove(lostPerson);
            } else {
                lostSet.add(lostPerson);
            }
        }
        
        for (int reservePerson : reserveSet){
            if(lostSet.contains(reservePerson-1)){
                lostSet.remove(reservePerson-1);
            } else if(lostSet.contains(reservePerson+1)){
                lostSet.remove(reservePerson+1);
            }
        }  

        return n-lostSet.size();
    }
}

 

 

 

 

---

 

 

조이스틱

 

[프로그래머스 - Java] 조이스틱

 

와.. 조이스틱 문제는 처음에 간단히 생각했는데 단순히 A~Z까지 몇번인지가 중요한 게 아니라

왼쪽으로 갈지, 오른쪽으로 갈지가 어려운 문제!

 

 

 

 

큰 수 만들기

 

 

[프로그래머스] 큰 수 만들기 -Java

 

 

 

내 풀이

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        char[] numberArr = number.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();

        // 문자 비교를 시작하는 인덱스를 나타내는 start 변수
        int start = 0;
        for(int i = 0; i < number.length() - k; i++){
            char max = '0';

            for(int j = start; j <= i + k; j++){
                // 가장 큰수를 골라서 그 다음 인덱스를 시작 인덱스로 설정하기
                
                if(max < numberArr[j]){
                    max = numberArr[j];
                    start = j + 1;
                }
            }
            // 가장 큰 문자를 String에 넣어주기
            stringBuilder.append(max);
        }
        
        return stringBuilder.toString();
    }
}

 

 

 

---

구명보트

 

 

 

 

 

내 풀이

 

투포인터로 풀 수 있다고 해서 참고해서 풀어봤다!!

int를 Integer로 변경해서 내림차순 정렬하는 것도 외워야 한다!!

 

 

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        // 무거운 순 정렬
        Integer[] peopleArr = Arrays.stream(people).boxed().toArray(Integer[]::new);  // 외우자
        Arrays.sort(peopleArr, Collections.reverseOrder());

        //투포인터
        int left = 0;
        int right = peopleArr.length - 1;

        while (left < right){
            // 가장 무거움 + 가장 가벼움
            int sum = peopleArr[left] + peopleArr[right]; 

            if(sum > limit){
                 // 무게 초과시 가장 무거운 사람 태운다
                left++;
                answer++;
            } else {
                // 초과 안하면 가장 무거움 + 가장 가벼움 태움
                left++;
                right--;
                answer++;
            }
        }

        if(left == right){
            // 한명이 남은 경우에는 플러스 해줌
            answer++;
        }
        
        return answer;
    }
}

 

 

 

---

단속카메라

 

 

 

 

내 풀이

 

가장 심플한 도움 받은 코드

프로그래머스 단속카메라(자바) - 그리디

 

 

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        
        // 배열의 두 번째 요소를 기준으로 오름차순으로 정렬
        Arrays.sort(routes, (o1, o2) -> Integer.compare(o1[1], o2[1]));
        int min = Integer.MIN_VALUE;
        
        for (int[] route : routes){
            if(min < route[0]){
                answer++;
                min = route[1];
            }
        }
        return answer;
              
    }
}

 

 

---

섬 연결하기

 

 

 

 

 

 

[프로그래머스] 섬 연결하기 - JAVA

 

 

 

 

 

 

크루스칼 알고리즘이란 것이 있다는 것을 알았다....!

여러번 풀어봐야 할 것 같다!

 

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
         int[] parent = new int[n];

        for (int i = 0; i < parent.length; i++){
            parent[i] = i;
        }

// 2번째 기준으로 정렬
        Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[2], o2[2]));

        for (int i = 0; i < costs.length; i++){
            if(findParent(parent, costs[i][0]) != findParent(parent, costs[i][1])){
                answer += costs[i][2];
                union(parent, costs[i][0], costs[i][1]);
            }
        }
        return answer;
    }
    
    
    public static int findParent(int[] parent, int node){
        if(parent[node] == node){
            return node;
        }
        return findParent(parent, parent[node]);
    }

    public static void union(int[] parent, int node1, int node2){
        int p1 = findParent(parent, node1);
        int p2 = findParent(parent, node2);

        if (p1 < p2){
            parent[p2] = p1;
        } else {
            parent[p1] = p2;
        }
    }
    
}