프로그래머스 PCCP 기출문제 2번 / 석유 시추

🧫 문제 분석

✔️ 출처

프로그래머스 PCCP 기출문제 2번 / 석유 시추

📖 문제

핵심
그래프 bfs or dfs을 사용하여 각 석유 덩어리에 개수를 따로 저장하고 번호를 매긴다. 각 열이 어떤 번호를 가졌는지 저장한다음 반복문으로 각 열을 돌아서 가진 번호에 대한 석유 덩어리 개수들을 뽑아서 최대값을 찾는다.

---

🔅 문제 풀이

row = 깊이
col = 1 2 3 4 .. 등 시추할 위치 열

import java.util.*;

class Solution {
    private static int[][] graph;
    private static int[] upDown = {0, 0, 1, -1};
    private static int[] leftRight = {1, -1, 0, 0};

    public int solution(int[][] land) {
        graph = land;
        int number = 2;
        int maxAmount = 0;
        int tempAmount = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        Set<Integer> numberSet = new HashSet<>();
        int[] depth = new int[land[0].length];

        for (int col = 0; col < land[0].length; col++) {
            for (int row = 0; row < land.length; row++) {

                // 석유 덩어리 넘버링 및 개수 map에 저장
                if (graph[row][col] == 1) {
                    // 석유 덩이리인 number에 대한 값을 가짐
                    map.put(number, bfs(row,col,number,tempAmount));
                    number++;

                }
                // set에 한 열에 대한 덩어리 넘버링을 저장
                if (graph[row][col] > 1) {
                    numberSet.add(graph[row][col]);
                }

            }
            // 저장해뒀던 넘버링을 꺼내서 각 열에 저장
            for (Integer i : numberSet) {
                depth[col] += map.getOrDefault(i, 0);
            }

            numberSet.clear();
        }
        
        // int max = 0;
        // for (int ia : depth) {
        //     max = Math.max(max, ia);
        // }

        // return max;

        return Arrays.stream(depth)
                .max()
                .getAsInt();
    }

    public  int bfs(int row, int col, int number, int temp) {

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{row, col});
        graph[row][col] = number;

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            temp++;

            for (int i = 0; i < 4; i++) {
                int tempCol = poll[0] + upDown[i];
                int tempRow = poll[1] + leftRight[i];

                if (tempCol>= 0 && tempRow >= 0 && tempCol < graph.length && tempRow < graph[0].length) {
                    if(graph[tempCol][tempRow] == 1) {
                        q.add(new int[]{tempCol, tempRow});
                        graph[tempCol][tempRow] = number;
                    }

                }
            }
        }
        return temp;
    }
}

스트림 연습한다고 return에 깨알 스트림을 사용했다ㅎㅎㅎㅎㅎ

---

❗ 오답노트 / 필요한 지식

처음에 할 때는 정확성만 통과하고 효율성에서 다 시간초과로 떴는데 이유는
1. 넘버링 하지 않았기에 같은 석유 덩어리 라인에 대한 중복 조회가 계속 이루어졌다.
2. 덩어리 값을 반복문 안에서 더하고 Math.max계속 호출하였다.

이 두가지 인 것 같다.

넘버링 하고 그런 것은 처음 문제 볼때 생각하긴 했었는데 일단 그냥 해보자 해서 정확성 매우빠르게 나오고 통과하길래 잘된줄 알았더니 효율성에서 시간초과가 떴다.

효율성 테스트에서는 항상 최소한의 반복문, 참조, 접근으로 코드를 짜주자..