골드에그

1. 문제요약

1715번: 카드 정렬하기 (acmicpc.net)

각 묶음의 카드의 개수가 A, B 라고 주어질 때, 한 번 두 묶음을 합칠 때 A+B 번의 비교를 해야한다. 만약 A, B, C, D 의 카드 개수를 순서대로 하나로 합치려고 할 때, (A+B) + ((A+B)+C) + ((A+B+C)+D) 번 총 비교해야 한다.

카드의 개수가 연속으로 주어질 때, 최소한 몇 번 비교해야 하는지 알아내시오.

2. 문제예제

3. 문제풀이(수동)

주어진 문제예제를 살펴보면, (10+20) 번 비교하고, 다시 그 묶음을 40 번과 비교해서 (10+20) + (30+40) 번 비교해야 한다. 정렬이 되어 있지 않는 경우도 살펴볼 수 있다. 10, 20, 28, 25 라면, (10+20) 번 비교하고, (28+25) 번 비교한 다음 두 카드비교를 더해 (10+20) + (28+25) + (10+20) + (28+25) 로 최소 166 번 비교할 수도 있다. 

4. 팩트추출

Fact 1 : 한 번 합쳐진 값도 다시 하나의 값으로 인식해서 나머지 다른 값들과 비교해 최소끼리 계속 더해야 한다.

문제풀이(수동) 두 번째 예제를 보면 10+20 번 비교해서 한 번 합쳐진 값이 다른 값들과 비교하는데 나머지 25, 28 숫자보다 커서 25와 28끼리 합쳐야 한 것을 볼 수 있다.

Fact 2 :  Fact 1 번을 통해 연산한 결과 값들도 나머지 다른 값들과 함께 정렬되어 다시 연산에 쓰여야 된다는 것을 알 수 있다. 다시 말해보면, 삽입하면서 정렬이 되고 그 중 항상 최소값을 가져와야 한다.

5. 문제전략

Fact 2 번을 통해 연산한 결과 값이 삽입하면서 정렬이 되어야 하고, 항상 최소값을 가져와야 한다는 점 때문에 우선순위 큐를 사용하면 된다.

5. 소스코드

import java.io.*;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        long total = 0;
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            long cardValue = Long.parseLong(br.readLine());
            pq.add(cardValue);
        }
        while (pq.size() > 1) {
            long first = pq.poll();
            long second = pq.poll();
            total += first + second;
            pq.add(first + second);
        }
        System.out.println(total);
    }
}

1. 문제요약

13334번: 철로 (acmicpc.net)

집과 사무실의 시작점, 끝점과 주어진 길이 d 가 주어질 때, 길이 d 에 포함되는 집과 사무실 구간의 개수가 최대인 경우를 구하시오.

2. 문제예제

3. 문제풀이(수동)

예제들을 문제풀이하면서 아이디어를 얻을 수는 없다. 아래 팩트추출을 통해 모든 경우의 수를 점검해야 한다.

4. 팩트추출

Fact 1 : 범위가 포함이 되어있는지 확인할 때, 나머지 좌표들을 정렬하면 다른 한 쪽만 대소비교할 수 있어 복잡도를 줄일 수 있다. 아래는 구간들의 오른쪽 끝점을 기준으로 오름차순으로 정렬한 모습이다. 가장 아래쪽부터 1번, 2번, 3번이라고 지칭할 때 다양한 특징들이 발견된다.

먼저 1번을 기준으로 2번이 포함되지 않는다면 3번, 4번에서도 2번은 포함되지 않는다. (오른쪽 끝점이 계속 순차적으로 증가하는 형태이기 때문에) 한 번 제외된 구간은 다른 구간에서 계산할 때도 제외된다는 뜻이다.

Fact 2 :  거리 N 에 포함되지 않는 구간은 계산할 필요가 없다.

Fact 3 : 이전 결과에서는 거리 N 에 포함이 되었더라도 다음에 계산할 때는 오른쪽 끝점이 이동하므로 포함되지 않을 수 있다. 이전 결과를 활용하기 위해 시작점도 정렬이 필요하다. 거리 N 에 포함되면 시작점을 포함했다가 오른쪽 끝점이 이동할 때 정렬되어 있는 시작점들에서 하나씩 꺼내 비교하면 모두 다 비교하지 않아도 된다.

5. 문제전략

한 쪽을 정렬해서 이전 결과 값을 재활용해야 한다는 점, 다른 한 쪽도 삽입을 하면서 정렬을 해야한다는 점을 파악해야 한다. 삽입하면서 정렬하는 자료구조는 우선순위큐가 적절하다.

5. 소스코드

private static class Interval implements Comparable<Interval> {
        int start, end;
        Interval(int startVariable, int endVariable) {
            start = startVariable;
            end = endVariable;
        }
        @Override
        public int compareTo(Interval o) {
            return Integer.compare(this.end, o.end);
        }
    }
    public static void main(String[] args) {
        // 거리 N, Interval 은 집과 구간, 오른쪽 끝점으로 정렬
        // ... (생략) ...
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (Interval interval : intervals) {
            if (interval.start >= interval.end - N) {
                count++;
                pq.add(interval.start);
            }
            while (!pq.isEmpty() && pq.peek() < interval.end - N) {
                pq.poll();
                count--;
            }
            maximum = Math.max(maximum, count);
        }
    }

1. 문제요약

코딩테스트 연습 - 미로 탈출 명령어 | 프로그래머스 스쿨 (programmers.co.kr)

(x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

l: 왼쪽으로 한 칸 이동
r: 오른쪽으로 한 칸 이동
u: 위쪽으로 한 칸 이동
d: 아래쪽으로 한 칸 이동

출발 위치, 도착 위치, 총 거리 K 가 주어질 때, 미로를 탈출하기 위한 경로를 구하시오.

2. 문제예제

문제 지문에 잘 나와있으므로 생략한다.

3. 팩트추출

Fact 1 : 사전 순으로 출력되려면 항상 d => l => r => u 순으로 탐색해야 한다. 지금 탐색 순서가 실패하면 아래 단계 순번으로 탐색하다가 다시 윗 단계 순번으로 탐색해야 한다.

Fact 2 : 2차원 배열로 구성되어 있는 그래프를 탐색하는데 위와 같이 특정한 조건이 존재하면 DFS 로 탐색하는 것이 좋다.

특정한 조건이란, 모두 비교하지 않고 도착이 가능한 형태인지 체크하는 문제이거나, 체인 형태로 탐색하는 순서(조건 존재)가 있는 경우이다. 해당 문제와 같이 실패했을 때도 탐색하는 순서가 정해져있다면 금상첨화다.

Fact 3 : 가지치기를 할 수 있다. 현재 위치에서 도착 위치까지 남은 거리와 남은 k 가 같은 짝수이거나 홀수이어야 한다. 짝 /홀이 다르다면, 어차피 도착을 못 하기 때문에 더 이상 탐색할 필요가 없다.

4. 문제전략

d => l => r => u 순서로 dfs 탐색하고 현재 위치에서 도착 위치까지 남은 거리와 남은 k 거리를 비교한다.

5. 소스코드

import java.util.*;

class Solution {
        // d, l, r, u 순으로 탐색
    private static final int[] dx = { 1, 0, 0, -1};
    private static final int[] dy = { 0, -1, 1, 0};
    private static final String[] term = {"d", "l", "r", "u"};
    private static int mapX, mapY;
    private static int endX, endY;
    private String tempAnswer = "";

    public boolean dfs(int x, int y, int k, String str, int diff) {
        if(k==0 && diff==0){
            tempAnswer = str;
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(nextX >=0 && nextY >= 0 && nextX < mapX && nextY < mapY && diff<=k) {
                if ((diff % 2 == 0 && k % 2 ==0) || (diff % 2 == 1 && k % 2 ==1)) {
                    if (dfs(nextX, nextY, k - 1, str + term[i], Math.abs(nextX - endX) + Math.abs(nextY - endY))) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer;
        mapX = n;
        mapY = m;
        endX = r-1;
        endY = c-1;
        int diff = Math.abs((r-1)-(x-1)) + Math.abs((c-1)-(y-1));
        dfs(x-1, y-1, k, "", diff);
        if(tempAnswer.equals("")){
            answer = "impossible";
        } else {
            answer = tempAnswer;
        }
        return answer;
    }
}

1. 문제요약

코딩테스트 연습 - 풍선 터트리기 | 프로그래머스 스쿨 (programmers.co.kr)

일렬로 나열된 n 개의 풍선이 있다. 풍선들을 아래 규칙에 따라 단 1개만 남을 때까지 하나씩 터트린다고 할 때 최후까지 남기는 것이 가능한 풍선들의 갯수를 구하시오.

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트린다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킨다.
3. 번호가 더 작은 풍선을 터트리는 행위는 한 번만 수행할 수 있다.

2. 문제예제

[9,-1,-5] 풍선이 주어질 때 다음과 같다.

• 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
• 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

3. 팩트추출

Fact 1 : 숫자가 낮은 풍선을 터트리는 행위는 한 번만 할 수 있으므로 모든 조합을 탐색할 필요는 없다. 탐색 방향에 맞춰 조합을 쪼개 규칙성을 찾는다. 일부 조합의 결과를 찾는 알고리즘과 전체 조합의 결과를 찾는 알고리즘이 같다면 DP 이다.

일단, 풍선의 갯수를 n 이라고 가정하고 n 이 점차 증가했을 때 규칙성을 찾아본다.

1) n 이 1 일 때,

무조건 풍선이 남아 있으므로 1 반환

2) n 이 2 일 때,

1번 풍선이 작고 2 번 풍선이 큰 경우와 1번 풍선이 크고 2번 풍선이 작은 경우로 나눌 수 있다.

낮은 풍선을 터트리는 찬스 없이도 큰 걸 제거할 수 있으므로 2 반환

3) n 이 3 일 때, 가운데 풍선을 기준으로 4 가지 경우의 수로 나눌 수 있다.

3-1) 왼쪽이 작고 오른쪽이 큰 경우

1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존

2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존

2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존

3-2) 왼쪽이 크고 오른쪽이 작은 경우

1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존

2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존

2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존

= 3-1 경우의 수와 같다.

3-3) 왼쪽도 작고 오른쪽도 작은 경우

1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존

3번을 제거하고 2번을 제거하면 (큰 것 => 큰 것 순) 1 생존

3번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 2 생존

2번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 1 생존

= 모든 경우의 수를 살펴봐도 중간값은 생존이 되지 않는다.

3-4) 왼쪽도 크고 오른쪽도 큰 경우

2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존

2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존

3번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 2 생존

현재 값보다 양 옆에 있는 숫자가 모두 작은 경우에만 생존하지 못 한다.

Fact 2 : 이전 결과 값이 그 다음에 영향을 미치지 않고 작은 문제들의 정답이 전체 문제의 정답이 되는 규칙성은 발견되지 않았다. (거의 모든 경우의 숫자가 살아 남으므로) 따라서 DP 나 분할 정복 문제는 아니다. 그러나 생존하지 못 하는 경우의 수로 보면 두 구역 모두 현재 숫자보다 작을 때 한 가지 경우의 수 밖에 없다. 따라서 경우의 수가 적은 여집합을 구한다.

Fact 3 : n 이 4일 때, 5일 때도 같은 규칙성이 존재하는지 확인한다. 작은 풍선을 제거하는 규칙을 사용하지 않고 큰 값만 골라 왼쪽, 오른쪽에서 제거한다면 항상 작은 값들만 배치하게 된다. 그렇게 n 이 3일 때로 만들고 위 규칙을 적용하면 결과값이 동일하다. 구역을 확장해도 해당 규칙에는 문제가 없다.

4. 문제전략

부분 문제로 보이지 않고 규칙성이 보이지 않으므로 완전 조합 문제로 풀어야 한다. 하지만 생존을 못 하는 여집합 경우의 수는 한 가지이므로 이 점을 고려하여 두 구역의 최솟 값보다 큰 경우의 숫자만 찾아 제외시켜 문제를 풀면 된다.

5. 소스코드

class Solution {
    public int solution(int[] a) {
        int count = 0;
        if (a.length == 1) return 1;
        if (a.length == 2) return 2;

        int leftMin = a[0];
        int rightMin[] = new int[a.length];
        rightMin[a.length-1] = a[a.length-1];

        for (int i = a.length - 2; i > 0; i--)
            rightMin[i] = Math.min(rightMin[i + 1], a[i]);

        for (int i = 0; i < a.length; i++) {
            if (!(leftMin < a[i] && rightMin[i] < a[i]))
                count++;
            leftMin = Math.min(leftMin, a[i]);
        }
        return count;
    }
}

1. 문제요약

코딩테스트 연습 - 다단계 칫솔 판매 | 프로그래머스 스쿨 (programmers.co.kr)

이 회사는 다단계 판매 업무를 하고 있다. 초대 받은 사람의 이익 10 퍼센트를 초대한 사람이 가지는 시스템인데 중앙에 있는 Center 까지 거슬러 올라가 모두 이익금을 나누어 가져야 한다.

판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어질 때, 각 판매원이 득한 이익금을 나열한 배열을 구하시오.

2. 문제예제

emily 가 450 원을 벌었다면, mary 는 10 퍼센트인 45 원을 가지게 되고, center 는 45원의 10 퍼센트인 40원을 가지게 된다.

3. 팩트추출

Fact 1 : 어렴풋이 보면 트리 자료구조 문제로 보일 수 있으나 enroll 입장에서 보면 부모가 하나이기 때문에 항상 일차원적인 구조이다. 따라서 부모노드까지 계속 재귀호출하면서 이익금을 계산해주면 된다. enroll 의 갯수만큼 반복문을 수행하고 이익금을 나누어 가지면 된다.

4. 문제전략

트리 문제라고 속지만 않으면 된다. enroll 을 순회하면서 이익금을 계산하면 된다.

5. 소스코드

import java.util.*;

class Solution {
   static class Person {
        String name;
        Person parent;
        int sellAmount;

        public Person(String name, Person parent, int sellAmount) {
            this.name = name;
            this.parent = parent;
            this.sellAmount = sellAmount;
        }

        public void calculateMultiLevel(int amount) {
            int parentAmount = amount / 10;
            this.sellAmount += amount - parentAmount;
            if (this.parent != null && parentAmount >= 1) {
                this.parent.calculateMultiLevel(parentAmount);
            }
        }
    }
    private static HashMap<String, Person> childParent;

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        childParent = new HashMap<>();
        for (String enrollP: enroll) {
            childParent.put(enrollP, new Person(enrollP, null, 0));
        }
        for (int i = 0; i < enroll.length; i++) {
            if (!referral[i].equals("-")) {
                childParent.get(enroll[i]).parent = childParent.get(referral[i]);
            }
        }
        for (int i = 0; i < seller.length ; i++) {
            childParent.get(seller[i]).calculateMultiLevel(amount[i] * 100);
        }
        int[] result = new int[enroll.length];

        for (int i = 0; i < result.length; i++) {
            result[i] = childParent.get(enroll[i]).sellAmount;
        }
        return result;
    }
}

1. 문제요약

코딩테스트 연습 - 등산코스 정하기 | 프로그래머스 스쿨 (programmers.co.kr)

출입구에서 산봉우리까지 갔다가 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다.

등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity 라고 할 때 이 intensity 가 가장 짧은 코스를 찾아라. (등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다.)

2. 문제예제

등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같다.

각 경로의 가중치가 가장 큰 값이 3 이며, 이 보다 intensity가 낮은 등산코스는 없다.

3. 팩트추출

Fact 1 : Dijkstra 다이젝스트라 알고리즘처럼 항상 최단 거리를 선택한다면, 경로의 intensity 배열은 항상 단조 증가 형태이다. 이 점을 활용하면 출발점에서 산봉우리까지 갔다가 다시 출발점으로 돌아오지 않아도 된다. 출발점에서 산봉우리까지 가는 반쪽짜리 최단 경로만 찾으면 된다. 출발 경로와 회귀 경로가 틀릴 수 있을지 언정 intensity 는 같을 것이기 때문이다. 이 문제에서는 경로를 구하라고 하지 않았으므로 가능하다. => 따라서 큐에 꺼낸 위치가 산봉우리라면 탐색을 종료한다.

Fact 2 : Fact 1 과 마찬가지로 경로를 구하라고 하지는 않았으므로, 출발점에서 동시에 출발하여 intensity 배열을 수정하여도 상관이 없다. 문제에서 요구하는 정답은 산봉우리와 그 산봉우리의 intensity 이다. 그러니까 어느 출발점에서 출발하여도 도착지점의 intensity 가 최소가 되는 경로만 찾으면 된다. 따라서 우선순위 큐에 출발지점을 모두 넣어놓고 시작한다.

Fact 3 : 일반적인 Dijkstra 다이젝스트라 알고리즘과 다른 점은 각 지점의 비용을 합한 거리가 최소가 되는 경로를 찾는 것이 아니라 각 구간의 최대 비용이 최소가 되는 경로를 찾는 것이다. 따라서 아래와 같이 로직을 수정한다.

if(dist[adjNode.to] > curNode.weight + adjNode.weight){
	dist[adjNode.to] = curNode.weight + adjNode.weight;
}

↓↓↓↓↓↓

if (dist[adjNode.to] > Math.max(curNode.weight, adjNode.weight)) {
	dist[adjNode.to] = effort;
}

Fact 4 : 산봉우리까지 가는 intensity 가 같은 경로가 여러 개라면, 산봉우리의 번호가 가장 작은 것을 반환하라고 지문에서 나와있으므로 산봉우리-intensity 배열에서 최소값을 찾을 때 산봉우리 배열을 먼저 정렬해야 한다.

4. 문제전략

팩트추출에서 소개한 다이젝스트라 변형 알고리즘을 사용하면 된다.

5. 소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    static class Node implements Comparable<Node> {
        int index;
        int effort;
        public Node(int index, int effort) {
            this.index = index;
            this.effort = effort;
        }
        @Override
        public int compareTo(Node o) {
            return this.effort - o.effort;
        }
    }
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] efforts;
    static int[] gatesSave, summitsSave;
    private static void initGraph(int v, int[][] data) {
        for(int i=0; i < v+1; i++){
            graph.add(new ArrayList<>());
        }
        for (int[] datum : data) {
            graph.get(datum[0]).add(new Node(datum[1], datum[2]));
            graph.get(datum[1]).add(new Node(datum[0], datum[2]));
        }
        efforts = new int[v+1];
        for (int i = 1; i < v+1; i++) {
            efforts[i] = Integer.MAX_VALUE;
        }
    }

    private static int[] dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        // 시작지점 삽입
        for (int gate : gatesSave) {
            pq.offer(new Node(gate, 0));
            efforts[gate] = 0;
        }

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (isSummit(curNode.index))
                continue;
            if (efforts[curNode.index] < curNode.effort) {
                continue;
            }
            for (Node adjNode : graph.get(curNode.index)) {
                int effort = (adjNode.effort == Integer.MAX_VALUE) ? curNode.effort : Math.max(curNode.effort, adjNode.effort);
                if (efforts[adjNode.index] > effort) {
                    efforts[adjNode.index] = effort;
                    pq.offer(new Node(adjNode.index, efforts[adjNode.index]));
                }
            }
        }

        Arrays.sort(summitsSave);
        int index = -1;
        int minEffort = Integer.MAX_VALUE;
        for (int summit : summitsSave) {
            if (efforts[summit] < minEffort) {
                minEffort = efforts[summit];
                index = summit;
            }
        }
        return new int[]{index, minEffort};
    }

    private static boolean isSummit(int num) {
        for (int summit : summitsSave) {
            if (num == summit) return true;
        }
        return false;
    }

    public static int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        gatesSave = gates;
        summitsSave = summits;
        initGraph(n, paths);
        return dijkstra();
    }
}