프로그래머스 코딩테스트 고득점 Kit - 완전탐색(최소직사각형, 모의고사, 소수 찾기, 카펫, 피로도, 전력망을 둘로 나누기, 모음사전)

1번 문제: 최소직사각형

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

풀이

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어질 때 모든 명함을 수납할 수 있는 가장 작은 지갑의 크기를 return 하도록 solution 함수를 완성해야 한다.

접근

모든 명함을 수납할 수 있으려면 모든 명함 중 가장 큰 가로, 그리고 모든 명함 중 가장 큰 세로 길이로 지갑을 만들어야 한다. sizes 배열을 순회하며 가장 큰 가로 길이, 가장 큰 세로 길이를 찾으면 된다.

코드

class Solution {
    public int solution(int[][] sizes) {
        int horizontalMax = 0, verticalMax = 0;
        for (int[] size : sizes) {
            int horizontal = Math.max(size[0], size[1]);
            horizontalMax = Math.max(horizontalMax, horizontal);
            int vertical = Math.min(size[0], size[1]);
            verticalMax = Math.max(verticalMax, vertical);
        }
        return horizontalMax * verticalMax;
    }
}

---

2번 문제: 모의고사

https://school.programmers.co.kr/learn/courses/30/lessons/42840

프로그래머스

풀이

수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 할 때 1번 문제부터 마지막 문제까지 다음과 같이 찍는다.

• 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
• 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
• 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해야 한다.

접근

말 그대로 위의 수포자들이 찍은 번호와 실제 정답과 비교해서 맞으면 점수를 올리고, 그 중 가장 높은 점수를 받은 수포자(들)의 번호를 반환하면 된다.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[] scores = new int[3];
        int[][] arr = {
                { 1, 2, 3, 4, 5 },
                { 2, 1, 2, 3, 2, 4, 2, 5 },
                { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 }
        };
        for (int i = 0; i < answers.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[j][i % arr[j].length] == answers[i]) {
                    scores[j]++;
                }
            }
        }
        int max = Math.max(Math.max(scores[0], scores[1]), scores[2]);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            if (scores[i] == max) {
                list.add(i + 1);
            }
        }
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}

---

3번 문제: 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

풀이

흩어진 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각을 붙여만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해야 한다.

접근

만들 수 있는 모든 숫자에 소수인지 여부를 저장하는 boolean 배열 prime을 만들고 소수라면 true를, 아니라면 false를 저장하도록 한다. 이후 dfs를 활용하여 numbers 문자열을 붙여가며 숫자를 만들어 이 숫자가 소수라면 Set<Integer> 타입의 set에 저장하고, 마지막에 set의 size를 반환한다.

코드

import java.util.*;

class Solution {
    
    private boolean[] visited, prime;
    private Set<Integer> set = new HashSet<>();

    public void getPrime(String numbers) {
        prime = new boolean[(int) Math.pow(10, numbers.length()) + 1];
        Arrays.fill(prime, 2, prime.length, true);
        for (int i = 2; i <= Math.sqrt(Math.pow(10, numbers.length())); i++) {
            if (!prime[i]) continue;
            for (int j = i * i; j <= Math.pow(10, numbers.length()); j += i) {
                prime[j] = false;
            }
        }
    }

    public void dfs(int dpth, int num, String numbers) {
        if (prime[num]) set.add(num);
        if (dpth == numbers.length()) return;
        for (int i = 0; i < numbers.length(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(dpth + 1, num * 10 + numbers.charAt(i) - '0', numbers);
                visited[i] = false;
            }
        }
    }

    public int solution(String numbers) {
        visited = new boolean[numbers.length()];
        getPrime(numbers);
        dfs(0, 0, numbers);
        int answer = set.size();
        return answer;
    }
}

---

4번 문제: 카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

풀이

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

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

접근

제한사항을 보면 brown은 8 이상, yellow는 1 이상이므로 최소 3 X 3 크기의 카펫이며, 카펫의 가로 길이는 세로 길이보다 길거나 같다.

brown + yellow는 카펫의 넓이라고 봐도 무방하므로, for문에서 세로를 의미하는 i의 범위는 3 이상, (brown + yellow) / 3 이하이며, 가로를 의미하는 j는 (brown + yellow) / i이다.
(brown + yellow)가 i의 배수일 때 가로 X 2 + 세로 X 2 - 모서리 4가 brown, 즉 갈색 테두리의 개수와 같다면 이를 반환하면 된다.

코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int row = 3, col = 3;
        for (int i = 3; i <= (brown + yellow) / 3; i++) {
            if ((brown + yellow) % i == 0) {
                int j = (brown + yellow) / i;
                if (2 * i + 2 * j - 4 == brown) {
                    row = j;
                    col = i;
                    break;
                }
            }
        }
        return new int[]{ row, col };
    }
}

---

5번 문제: 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

풀이

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있을 때, 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모된다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해야 한다.

접근

dfs를 활용하여 탐험할 수 있는 던전을 순회하며 깊이를 의미하는 매개변수 dpth와 answer를 비교하며 마지막에 가장 큰 값을 반환한다.

코드

class Solution {

    private int answer = 0;
    private boolean[] visited;

    public void dfs(int dpth, int k, int[][] dungeons) {
        if (dpth > dungeons.length) return;
        answer = Math.max(answer, dpth);
        for (int i = 0; i < dungeons.length; i++) {
            int[] dungeon = dungeons[i];
            if (!visited[i] && k >= dungeon[0]) {
                visited[i] = true;
                dfs(dpth + 1, k - dungeon[1], dungeons);
                visited[i] = false;
            }
        }
    }

    public int solution(int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            int[] dungeon = dungeons[i];
            visited = new boolean[dungeons.length];
            if (k >= dungeon[0]) {
                visited[i] = true;
                dfs(1, k - dungeon[1], dungeons);
            }
        }
        return answer;
    }

}

---

6번 문제: 전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

풀이

전선을 통해 하나의 트리 형태로 연결된 n개의 송전탑이 있을 때 이 전선들 중 하나를 끊어서 2개로 분할된 네트워크 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추어야 한다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어지고, 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해야 한다.

접근

말 그대로 전선을 하나씩 잘라보며 bfs를 활용하여 각 네트워크 전력망이 갖는 송전탑의 개수를 구하고, 둘의 차이(절대값)이 가장 작을 때 반환하면 된다.

코드

import java.util.*;

class Point {

    private int x;
    private List<Point> list;

    public Point(int x) {
        this.x = x;
        this.list = new ArrayList<>();
    }

    public void add(Point point) {
        list.add(point);
    }

    public void delete(Point point) {
        list.remove(point);
    }

    public int getX() {
        return x;
    }

    public List<Point> getList() {
        return list;
    }

}

class Solution {

    private boolean[] visited;

    public int bfs(Point point) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(point);
        visited[point.getX()] = true;
        int count = 1;
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            for (Point e : p.getList()) {
                if (!visited[e.getX()]) {
                    visited[e.getX()] = true;
                    queue.add(e);
                    count++;
                }
            }
        }
        return count;
    }

    public int solution(int n, int[][] wires) {
        Point[] points = new Point[n + 1];
        for (int i = 1; i <= n; i++) {
            points[i] = new Point(i);
        }
        for (int[] wire : wires) {
            points[wire[0]].add(points[wire[1]]);
            points[wire[1]].add(points[wire[0]]);
        }
        int answer = Integer.MAX_VALUE;
        for (int[] wire : wires) {
            visited = new boolean[n + 1];
            points[wire[0]].delete(points[wire[1]]);
            points[wire[1]].delete(points[wire[0]]);
            int a = bfs(points[wire[0]]);
            int b = bfs(points[wire[1]]);
            points[wire[0]].add(points[wire[1]]);
            points[wire[1]].add(points[wire[0]]);
            answer = Math.min(answer, Math.abs(a - b));
        }
        return answer;
    }
}

---

7번 문제: 모음사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

풀이

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있다.

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"이며, 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해야 한다.

접근

dfs를 활용하여 cnt를 하나씩 늘려가며 알파벳을 하나씩 붙였다가 뗐다가를 반복하며, word와 같을 때 마지막에 그 cnt 값을 반환하면 된다.

코드

class Solution {

    private char[] alphabet = {'A', 'E', 'I', 'O', 'U'};
    private int answer = 0, cnt = 0;
    private StringBuilder sb = new StringBuilder();

    public void dfs(int dpth, String word) {
        if (dpth > 5) {
            return;
        }
        if (word.equals(sb.toString())) {
            answer = cnt;
            return;
        }
        cnt++;
        for (int i = 0; i < alphabet.length; i++) {
            sb.append(alphabet[i]);
            dfs(dpth + 1, word);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public int solution(String word) {
        dfs(0, word);
        return answer;
    }

}

---

결론

dfs, bfs의 개념을 알고 있다면 쉽게 풀 수 있는 브루트 포스(완전 탐색) 알고리즘에 관련된 문제였다. 딱히 헤매거나 어려운 문제는 없었고, 설명할 내용도 딱히 없어서 하나의 글에 모두 정리하게 됐다.

문제는 그 다음 파트인 그리디 알고리즘인데.. 원래 해당 알고리즘에 약하다는 것을 알고 있었지만 생각보다 더 많이 헤맨 파트였다. 다음 글에서 내가 설명을 잘 할 수 있을까..?