[알고리즘] 그리디 풀이 - 3

Kevin·2025년 3월 8일
백준 자바 11000백준 자바 1339백준 자바 1744

Algorithm

목록 보기
4/10
post-thumbnail

1️⃣ 단어 수학 - 1339

문제

정답

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

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        String[] words = new String[n];

        for (int i = 0; i < n; i++) {
            words[i] = br.readLine();
        }

        HashMap<Character, Integer> weightMap = new HashMap<>(); // 각 알파벳의 가중치(자리수 값)를 저장하는 HashMap

        for (String word : words) {

            int len = word.length();

            for (int i = 0; i < len; i++) {
                char c = word.charAt(i);
                int weight = (int) Math.pow(10, len - i - 1); // 10의 자리수만큼 가중치 부여

                weightMap.put(c, weightMap.getOrDefault(c, 0) + weight);
            }
        }

        List<Map.Entry<Character, Integer>> entries = new ArrayList<>(weightMap.entrySet());

        entries.sort((o1, o2) -> o2.getValue() - o1.getValue()); // 가중치 순대로 정렬

        HashMap<Character, Integer> valueMap = new HashMap<>(); // 가중치 값

        int num = 9;
        for (Map.Entry<Character, Integer> entry : entries) {
            valueMap.put(entry.getKey(), num--);
        }

        int totalSum = 0;
        for (String word : words) {
            StringBuilder numStr = new StringBuilder();
            for (char c : word.toCharArray()) {
                numStr.append(valueMap.get(c)); // 매핑된 숫자로 변환
            }
            totalSum += Integer.parseInt(numStr.toString()); // 합산
        }

        bw.write(totalSum + "\n");

        br.close();
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

문제의 핵심은 자리수가 더 큰 숫자일 수록 가중치를 더 높게 배정 하여서 더 큰 숫자를 부여해야 한다는 점이다.

GCF와 ACDEB를 예로 들어보자.

A와 C는 GCF의 어떤 글자보다 더욱 자리수가 크다.

이는 A와 C는 더욱 큰 수를 부여 받아야 한다.

즉 A는 9, C는 8를 부여 받아야 한다.

이를 구현 하기 위해서는 각 문자에 자리수 가중치를 부여 해줄 필요가 있다.

int len = word.length();

for (int i = 0; i < len; i++) {
    char c = word.charAt(i);
    int weight = (int) Math.pow(10, len - i - 1); // 10의 자리수만큼 가중치 부여

    weightMap.put(c, weightMap.getOrDefault(c, 0) + weight);
}

위 코드를 통해서 각 문자에 대해서 자리수 가중치를 부여 해줄 수 있다.

배운 점

  • Map.Entry를 사용하여서, key와 value를 getKey()와 getValue() 메서드를 사용하여 접근할 수 있다.
    • Entry라는 객체는 HashMap에 대한 key-value 쌍을 하나의 객체로 가지고 있어서 getKey()와 getValue() 메서드로 key와 value에 접근할 수 있게 해준다.

https://seungjjun.tistory.com/270

https://www.acmicpc.net/problem/1339


2️⃣ 수 묶기 - 1744

문제

틀린 답

import java.io.*;
import java.util.Arrays;

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        int idx = 0;
        int ans = 0;

        while (idx < n) {

            if (idx != n - 1) { // 마지막 인덱스가 아닐 떄
                int firstNum = arr[idx];
                int secNum = arr[idx + 1];

                int mul = firstNum * secNum;
                int add = firstNum + secNum;

                if (mul > add) { // 곱하기 더 크면 두 수를 묶어야 함.
                    idx += 2;
                    ans += mul;
                } else { // 하나의 수로만 진행
                    idx += 1;
                    ans += firstNum;
                }

            } else { // 마지막 인덱스일 때
                ans += arr[idx]; // 바로 더해줌
                idx += 1;
            }
        }

        if (n == 1) {
            bw.write(arr[0] + "\n");
        } else {
            bw.write(ans + "\n");
        }

        br.close();
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

위 코드로는 예시의 테스트 케이스들은 모두 맞췄지만, 바로 오답 처리 되었다.

위 코드는 아래의 반례를 해결 하지 못한다.

5
-3
-2
2
3
4

위 반례를 위 코드로 풀면 다음과 같다.

(-3 -2) + (2 3) + 4 = 16

그러나 최적의 답은 다음과 같다.

(-3 -2) + 2 + (3 4) = 20

즉 단순히 오름차순으로 푸는 것은 답이 아니라는 것이다.

여기서 힌트를 얻어서 음수와 0과 이보다 큰 숫자들의 리스트를 나누고 음수와 0 리스트는 오름차순을 이보다 큰 숫자들 리스트는 내림차순으로 하여서 최적의 답을 찾고자 하였다.

정답

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        ArrayList<Integer> lowArr = new ArrayList<>();
        ArrayList<Integer> bigArr = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());

            if (num <= 0) {
                lowArr.add(num);
            } else {
                bigArr.add(num);
            }
        }

        lowArr.sort((o1, o2) -> o1 - o2);
        bigArr.sort((o1, o2) -> o2 - o1);

        int ans = 0;

        ans += getAns(lowArr);
        ans += getAns(bigArr);

        if (n == 1) {
            bw.write(lowArr.get(0) + "\n");
        } else {
            bw.write(ans + "\n");
        }

        br.close();
        bw.close();
    }

    public static int getAns(List<Integer> arr) {

        int idx = 0;
        int ans = 0;

        while (idx < arr.size()) {

            if (idx != arr.size() - 1) { // 마지막 인덱스가 아닐 떄
                int firstNum = arr.get(idx);
                int secNum = arr.get(idx + 1);

                int mul = firstNum * secNum;
                int add = firstNum + secNum;

                if (mul > add) { // 곱하기 더 크면 두 수를 묶어야 함.
                    idx += 2;
                    ans += mul;
                } else { // 하나의 수로만 진행
                    idx += 1;
                    ans += firstNum;
                }

            } else { // 마지막 인덱스일 때
                ans += arr.get(idx); // 바로 더해줌
                idx += 1;
            }
        }

        return ans;
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

배운 점

  • GPT에게 답을 구하기 보다는 현재 코드에서 어떤 방향성으로 나가야 할지에 대해서 물어보면 도움이 된다.
  • 입력 값을 굳이 하나의 리스트로 진행 할 필요는 없다.

다른 이들의 코드 풀이 방식

https://tussle.tistory.com/900

→ 리스트 대신 우선순위 큐를 사용하여 처리함.

https://www.acmicpc.net/problem/1744


3️⃣ 강의실 배정 - 11000

문제

위 문제에 대해서 아래와 같은 입력값 예시가 있다고 하자.

7
0 7
32 42
32 40
45 46
0 8
24 32
9 19

이 때 두번째 숫자(종료 시간)를 기준으로 오름차순 하여 정렬한다.

그렇다면 아래와 같이 정렬 될 것이다.

0 7
0 8
9 19
24 32
32 40
32 42
45 46

첫번째 시간인 0~ 7 을 예시로 들자.

이 때 그 다음 행(0 ~8)의 첫번째 숫자0 이 0~ 7 중 두번째 숫자의 값 7 보다 작을 경우에는 같은 강의실에서 연속적으로 수업을 들을 수 있다.

0~ 7 시간으로 진행하는 수업은 7시에 끝이 난다. 그렇다면 7시 이상으로 시작하는 숫자가 와야 같은 강의실을 쓸 수 있다는 것이 된다.

해당 문제의 핵심은 이렇게 연속적인 시간의 흐름에서 최소의 강의실을 사용 해야 한다는 것이다.

틀린 답

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

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1]; // 두 번째 값을 기준으로 오름차순 정렬
            }
        });

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            pq.offer(new int[]{a, b});
        }

        int ans = 1;

        int val = Integer.MIN_VALUE;

        List<int[]> tmpList = new ArrayList<>();

        while (!pq.isEmpty()) { // 우선순위 큐에서 정렬된 요소를 하나씩 꺼내기

            int[] pair = pq.poll();

            if (val <= pair[0]) {
                val = pair[1];
            } else {
                tmpList.add(pair);
            }

            if (pq.isEmpty() && !tmpList.isEmpty()) { // 우선순위 큐가 비었지만, 남은 요소가 있다면 다시 넣기
                val = Integer.MIN_VALUE;
                pq.addAll(tmpList);
                tmpList.clear();
                ans ++;
            }
        }

        bw.write(ans + "\n");

        br.close();
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

위 코드는 시간 초과가 나왔다.

pq.poll() 이후 tmpList를 별도로 관리 하기 위해서 다시 pq.addAll(tmpList) 할 시 O(N log N) 연산이 중첩 되는 문제가 있었다.

그렇기에 최적화를 위해 tmpList 관리를 위해 우선순위 큐를 사용하여 관리 하고자 하였다.

정답

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

public class Main {
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int[][] lectures = new int[n][2];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            lectures[i][0] = Integer.parseInt(st.nextToken()); // 시작 시간
            lectures[i][1] = Integer.parseInt(st.nextToken()); // 종료 시간
        }

        Arrays.sort(lectures, Comparator.comparingInt(a -> a[0])); // 시작 시간을 기준으로 정렬

        PriorityQueue<Integer> endTimes = new PriorityQueue<>();

        int rooms = 0;

        for (int[] lecture : lectures) {
            int start = lecture[0];
            int end = lecture[1];

            while (!endTimes.isEmpty() && endTimes.peek() <= start) { // 현재 강의 시작 시간 이전에 끝나는 강의들은 제거
                endTimes.poll();
            }

            endTimes.offer(end);  // 새로운 강의 종료 시간 추가

            rooms = Math.max(rooms, endTimes.size()); // 최대 강의실 개수 갱신
        }

        bw.write(rooms + "\n");
        bw.flush();
        br.close();
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

위 코드의 흐름은 다음과 같다.

  1. 현재 강의를 하나씩 확인한다.
  2. 기존 강의 중에서 만약 끝난 강의가 있다면 강의실을 반환한다.
    1. 이 때 만약 이전 시간의 강의가 아직 끝나지 않았는데 강의실이 필요하다면 그 만큼 강의실 개수가 추가 되어야 한다.
  3. 새로운 강의의 종료시간을 큐에 추가한다.
  4. 현재 사용중인 강의실 개수를 업데이트 한다.

위 흐름에 따른 value는 다음과 같다.

0 771
0 87, 82
9 198 → 제거, 192
24 3219 → 제거, 322
32 4032 → 제거, 402
32 4240, 422
45 4640 → 제거, 42 → 제거, 462

다른 이들의 코드 풀이 방식

https://steady-coding.tistory.com/253

  • 그리디와 우선순위큐를 사용하여 푸셨으며, 별도 while 문을 사용하지 않고 큐에서 남은 원소들의 개수를 답으로 사용 하셨다.

큐에서 맨 처음 원소를 로직 시작 부터 넣어두었다면 최소 강의실의 개수를 1로 지정 하고 시작한 것과 마찬가지이다.

별도 반복문이 돌지 않아도 되기에 나의 로직보다 더욱 효율적인 로직이다.

pq.offer(lectures[0].end);

for (int i = 1; i < N; i++) {
// 우선순위 큐에서 가장 작은 종료 시간과
// 현재 lectures[i]의 시작 시간을 비교한다.
if (pq.peek() <= lectures[i].start) {
   pq.poll();
}
pq.offer(lectures[i].end);
}

배운 점

  • 문제를 푸면 풀 수록 이제는 풀이 방법으로 틀리는게 아닌 시간 복잡도로 인해서 틀리는 경우가 대다수인 것 같다.
    • 풀이를 생각하고, 이를 코드로 옮겼을 때 내 코드가 시간 복잡도가 얼마 나올지를 판단할 수 있는 능력을 키우자. https://adjh54.tistory.com/186
  • 우선순위 큐의 peek은 삭제하지 않고 첫 원소를 가지고 온다.
  • ArrayList의 경우 삽입 / 삭제시 많은 리소스가 소모 된다.
    • 이렇게 시간 자체가 짧게 주어지는 경우에서는 문제에서 자료 구조 자체에 대해서 힌트를 준 것이기에 그에 맞는 자료구조를 사용하는 방식으로 생각 해봐야 한다.

https://www.acmicpc.net/problem/11000

profile
Kevin
Hello, World! \n
이전 포스트

[알고리즘] 그리디 풀이 - 2

다음 포스트

[알고리즘] 그리디 풀이 - 4

0개의 댓글