Java kit

해시

1. 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

5점

public class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> set = new HashSet<>(List.of(phone_book));

        for (String p_num : phone_book) {
            for (int i = 1; i < p_num.length(); i++) {
                if (set.contains(p_num.substring(0, i)))
                    return false;
            }
        }
        return true;
    }
}

2. 위장

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothes	return
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]	3

입출력 예 설명

예제 #1
headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

예제 #2
face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

4점

public class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> map = new HashMap<>();

        for (String[] c : clothes) {
            map.put(c[1], map.getOrDefault(c[1], 0) + 1);
        }
        Iterator<Integer> ir = map.values().iterator();

        while (ir.hasNext())
            answer *= ir.next() + 1;

        return answer - 1;
    }
}

스택/큐

1. 기능개발

푼 날짜: 2021.11.25

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progresses	speeds	return
[93, 30, 55]	[1, 30, 5]	[2, 1]
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

입출력 예 설명

입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

5점

public class Solution {
    public ArrayList<Integer> solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> answer = new ArrayList<>();
        int[] periods = new int[speeds.length];
        int max = -1;
        int count = 1;

        for (int i = 0; i < periods.length; i++) 
            periods[i] = (int) Math.ceil((double) (100 - progresses[i]) / speeds[i]);

        for (int i : periods) {
            if (max == -1) {
                max = i;
            } else if (max >= i) {
                count++;
            } else {
                answer.add(count);
                count = 1;
                max = i;
            }
        }
        answer.add(count);
        return answer;
    }
}

2. 프린터

푼 날짜: 2021.11.25

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

입출력 예

priorities	location	return
[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.

4점

public class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<Integer> q = new LinkedList<>();

        for (Integer i : priorities) q.offer(i);
        int max =  Collections.max(q);

        while (!q.isEmpty()) {
            if (max > q.peek()) {
                q.offer(q.poll());
            } else {
                answer++;
                q.poll();

                if (location == 0) {
                    break;
                }
                max = Collections.max(q);
            }
            location--;
            if (location == -1) location = q.size() - 1;
        }
        return answer;
    }
}

뒤로 미룸: [1, 9, 1, 1, 1, 1]
뒤로 미룸: [9, 1, 1, 1, 1, 1]
꺼낸 후: [1, 1, 1, 1, 1]
꺼낸 후: [1, 1, 1, 1]
꺼낸 후: [1, 1, 1]
꺼낸 후: [1, 1]
꺼낸 후: [1]
5

public class 프린터 {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<Integer> q = new LinkedList<>();

        for (Integer i : priorities) q.offer(i);
        int max =  Collections.max(q);

        while (!q.isEmpty()) {
            if (max > q.peek()) {
                q.offer(q.poll());
                System.out.println("뒤로 미룸: " + q);
            } else {
                answer++;
                q.poll();
                System.out.println("꺼낸 후: " + q);

                if (location == 0) {
                    break;
                }
                max = Collections.max(q);
            }
            location--;
            if (location == -1) location = q.size() - 1;
        }
        return answer;
    }
}

3. 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예bridge_lengthweighttruck_weightsreturn

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

3점

public class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> q = new LinkedList<Integer>();
        int idx = 0;
        int time = 0;
        int sum = 0;

        while (idx < truck_weights.length) {
            time++;

            if (q.size() == bridge_length) 
                sum -= q.poll();

            if (sum + truck_weights[idx] <= weight) {
                q.offer(truck_weights[idx]);
                sum += truck_weights[idx];
                idx++;
            } else {
                q.offer(0);
            }
        }
        return time + bridge_length;
    }
}

설명코드

[7] - time: 1 - sum: 7
[7, 0] - time: 2 - sum: 7
[0, 4] - time: 3 - sum: 4
[4, 5] - time: 4 - sum: 9
[5, 0] - time: 5 - sum: 5
[0, 6] - time: 6 - sum: 6

public class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> q = new LinkedList<Integer>();
        int idx = 0;
        int time = 0;
        int sum = 0;

        while (idx < truck_weights.length) {
            time++;

            if (q.size() == bridge_length) 
                sum -= q.poll();

            if (sum + truck_weights[idx] <= weight) {
                q.offer(truck_weights[idx]);
                sum += truck_weights[idx];
                idx++;
            } else {
                q.offer(0);
            }
            System.out.println(q + " - time: " + time + " - sum: " + sum);
        }
        return time + bridge_length;
    }
}

4. 주식가격

public class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

        for (int i = 0; i < prices.length - 1; i++) {
            int price = prices[i];

            for (int j = i + 1; j < prices.length; j++) {
                int nextPrice = prices[j];
                if (price > nextPrice) {
                    answer[i] = j - i;
                    break;
                }

            }
            if (answer[i] == 0)
                answer[i] = prices.length - 1 - i;
        }
        return answer;
    }
}

스택/큐 문제인데 for 문 두개의 배열로 풀리는 것 같다.

힙 (Heap)

1. 더 맵게

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예scovilleKreturn

[1, 2, 3, 9, 10, 12]	7	2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

public class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i : scoville) heap.offer(i);

        while (heap.peek() < K) {
            int first = heap.poll();
            if (heap.peek() == null) return -1;
            int newOne = mix(first, heap.poll());
            heap.offer(newOne);
            answer++;
        }
        return answer;
    }

    private int mix(Integer f1, Integer f2) {
        return f1 + 2 * f2;
    }
}

정렬

1. 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

8점

public class Solution {
    String answer = "";

    public String solution(int[] numbers) {
        String[] arr = Arrays.stream(numbers).mapToObj(String::valueOf).toArray(String[]::new);
        Arrays.sort(arr, (a, b) -> (b + a).compareTo(a + b));
        Stream.of(arr).forEach(s -> answer += s);
        return answer.charAt(0) == '0' ? "0" : answer;
    }
}

2. H-Index

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예citationsreturn

[3, 0, 6, 1, 5]	3

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

※ 공지 - 2019년 2월 28일 테스트 케이스가 추가되었습니다.

public class Solution {
    public int solution(int[] citations) {
        int n = citations.length;
        Arrays.sort(citations);

        for (int i = 0; i < citations.length; i++) {
            if (citations[i] >= n - i) {
                return n - i;
            }
        }
        return 0;
    }
}

완전탐색

1. 소수찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

7점

public class Solution {
    StringBuilder str = new StringBuilder();
    char[] arr;
    HashSet<Integer> check = new HashSet<>();
    HashSet<Integer> answer = new HashSet<>();

    public int solution(String numbers) {
        arr = numbers.toCharArray();

        dfs();
        return answer.size();
    }

    private void dfs() {
        if (arr.length != str.length()) {
            for (int i = 0; i < arr.length; i++) {
                if (!check.contains(i)) {
                    str.append(arr[i]);
                    check.add(i);

                    isPrime(str);
                    dfs();

                    str.deleteCharAt(str.length()-1);
                    check.remove(i);
                }
            }
        } 
    }

    private void isPrime(StringBuilder str) {
        int n = Integer.parseInt(new String(str));

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return;
        }

        if (n >= 2) answer.add(n);
    }
}

전체코드

입력: 113

1
11
113 // 123
13
131 // 132
1
11
113 // 213
13
131 // 231
3
31
311 // 312
31
311 // 321
[113, 131, 3, 311, 11, 13, 31]
7

public class 소수찾기 {
    StringBuilder str = new StringBuilder();
    char[] arr;
    HashSet<Character> check = new HashSet<>();
    HashSet<Integer> answer = new HashSet<>();

    public int solution(String numbers) {
        arr = numbers.toCharArray();

        dfs();

        System.out.println(answer);

        return answer.size();
    }

    private void dfs() {
        if (arr.length != str.length()) {
            for (int i = 0; i < arr.length; i++) {
                if (!check.contains(arr[i])) {
                    str.append(arr[i]);
                    check.add(arr[i]);

                    System.out.println(str);
                    isPrime(str);
                    dfs();

                    str.deleteCharAt(str.length()-1);
                    check.remove(check.remove(arr[i]));
                }
            }
        } 
    }

    private void isPrime(StringBuilder str) {
        int n = Integer.parseInt(new String(str));

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return;
        }

        if (n >= 2) answer.add(n);
    }
}

2. 카펫

푼 날짜: 2021.11.25

6점

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

public class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {
                (int) ((-1 * (-brown/2 + 2) + Math.sqrt(Math.pow(-brown/2 + 2, 2) - 4 * yellow)) / 2) + 2
                , (int) ((-1 * (-brown/2 + 2) - Math.sqrt(Math.pow(-brown/2 + 2, 2) - 4 * yellow)) / 2) + 2
        };
        return answer;
    }
}

탐욕법 (Greedy)

1. 조이스틱

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예namereturn

"JEROEN"	56
"JAN"	23

2. 큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예numberkreturn

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

10점

해답

public class Solution {
	static String number;
	
    public String solution(String number, int k) {
    	this.number = number;
        int maxIdx = -1;
        int digit = number.length() - k;
        int i = 0;
        StringBuilder answer = new StringBuilder();
        
        while (answer.length() < digit) {
        	maxIdx = findMax(maxIdx + 1, k + i++);
        	answer.append(number.charAt(maxIdx));
        }
        return new String(answer);
    }

	private int findMax(int start, int end) {
		int max = -1;
		int idx = -1;
		
		for (int i = start; i <= end; i++) {
			if (max < number.charAt(i)) {
				max = number.charAt(i);
				idx = i;
			}
		}
		return idx;
	}
}

동적계획법 (Dynamic Programming)

깊이/너비 우선탐색 (DFS / BFS)

1. 타겟 넘버

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

답안

public class Solution {
    int[] numbers;
    int target;

    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;

        return dfs(0, 0);
    }

    private int dfs(int sum, int idx) {
        if (idx == numbers.length) {
            if (sum == target) return 1;
            else return 0;
        }
        return dfs(sum + numbers[idx], idx + 1) + dfs(sum - numbers[idx], idx + 1);
    }
}

또 다른 코드

public class Solution {
    int[] numbers;
    int target;
    int cnt;
    int sum = 0;

    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;

        dfs(0);
        return cnt;
    }

    private void dfs(int idx) {
        if (idx == numbers.length) {
            if (sum == target) cnt++;
            return;
        }
        sum += numbers[idx];
        dfs(idx + 1);
        sum -= numbers[idx];
        sum -= numbers[idx];
        dfs(idx + 1);
        sum += numbers[idx];
    }
}

출력코드

+4+1+2+1
+4+1+2-1
+4+1-2+1
+4+1-2-1
+4-1+2+1
+4-1+2-1
+4-1-2+1
+4-1-2-1
-4+1+2+1
-4+1+2-1
-4+1-2+1
-4+1-2-1
-4-1+2+1
-4-1+2-1
-4-1-2+1
-4-1-2-1

public class Solution {
    int[] numbers;
    int target;
    int cnt;
    int sum = 0;
    Stack<Integer> stack = new Stack<>();

    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;

        dfs(0);
        System.out.println();
        return cnt;
    }

    private void dfs(int idx) {
        if (idx == numbers.length) return;
        stack.push(numbers[idx]);
        if (stack.size() == 4) {
            stack.forEach(i -> System.out.print(i > 0 ? "+" + i : i));
            System.out.println();
        }
        dfs(idx + 1);
        stack.pop();
        stack.push(-numbers[idx]);
        if (stack.size() == 4) {
            stack.forEach(i -> System.out.print(i > 0 ? "+" + i : i));
            System.out.println();
        }
        dfs(idx + 1);
        stack.pop();
    }
}

풀코스문제는 DFS 를 두 번 써서 풀 수 있다.

그래프