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

 

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

프로그래머스

 

 

첫번째 생각

class Solution {
    
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int result;
    static int[] resultArray;
    static int oil = 1;
    
    public int solution(int[][] land) {
        int answer = 0;
        resultArray = new int[land[0].length];
        
        for(int j = 0; j < land[0].length; j++) {
            for(int i = 0; i < land.length; i++) {
                if(land[i][j] == oil || land[i][j] == 1) {
                    result = 1;
                    dfs(i, j, land);
                    resultArray[j] += result;
                }
            }
            oil++;
        }
        
       // for(int i = 0; i< resultArray.length; i++) {
       //      System.out.println(resultArray[i]);
       //  }
        
        for(int i = 0; i< resultArray.length; i++) {
            answer = Math.max(answer, resultArray[i]);
        }
        
        
        return answer;
        
    }
    
    void dfs(int x, int y, int[][] land) {
        // 0인덱스 : 1을 2로, 1인덱스 : 2를 3으로
        land[x][y] = oil + 1;
                
        for(int i = 0; i < 4; i++){
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            
            if(nextX >= 0 && nextX < land.length && nextY >=0 && nextY < land[0].length) {
                if(land[nextX][nextY] == oil || land[nextX][nextY] == 1) {
                    result++;
                    dfs(nextX, nextY, land);
                }
            }
                    
        }

    }
    
}

 

 

답은 다 맞았는데 시간 초과를 잡아야함

이전에 겹친 영역을 계산해줬으면 그곳은 다시 아예 안돌도록 해야할거같음🤔🤔

 

 

두번째 생각

import java.util.*;

class Solution {
    
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int result;
    static int[] resultArray;
    static int oil = 1;
    
    //static int[] num;
    static Map<Integer, Integer> num = new HashMap<>();
    static Map<Integer, Integer> check = new HashMap<>();
    
    public int solution(int[][] land) {
        int answer = 0;
        resultArray = new int[land[0].length];
        
//         num = new int[land[0].length]; // 각 열에 1이 몇 개 있는지 기록하는 배열
//         for(int j = 0; j < land[0].length; j++) {
//             for(int i = 0; i < land.length; i++) {
//                 if(land[i][j] == 1) {
//                     num[j] += 1;
//                 }
//             }
//         }
        
        
        for(int j = 0; j < land[0].length; j++) {
            for(int i = 0; i < land.length; i++) {
                if(land[i][j] == 1) {
                    num.put(j, num.getOrDefault(j, 0) +1);
                }
            }
        }
        
        
        
        
        for(int j = 0; j < land[0].length; j++) {
            
            if(check.get(j) != null && check.get(j) == num.get(j)) {
            //if(check.get(j) != null && check.get(j) == num[j]) {
                resultArray[j] = result;
                continue;
            }
            else{
                for(int i = 0; i < land.length; i++) {
                    if(land[i][j] == oil || land[i][j] == 1) {
                        result = 1;
                        dfs(i, j, land);
                        resultArray[j] += result;
                    }
                }
                oil++;
            }

        }
        
        
        
       for(int i = 0; i< resultArray.length; i++) {
            System.out.println(resultArray[i]);
        }
        
        for(int i = 0; i< resultArray.length; i++) {
            answer = Math.max(answer, resultArray[i]);
        }
        
        
        return answer;
        
    }
    
    void dfs(int x, int y, int[][] land) {
        // 0인덱스 : 1을 2로, 1인덱스 : 2를 3으로... 반복반복
        land[x][y] = oil + 1;
                
        for(int i = 0; i < 4; i++){
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            
            if(nextX >= 0 && nextX < land.length && nextY >=0 && nextY < land[0].length) {
                if(land[nextX][nextY] == oil || land[nextX][nextY] == 1) {
                    result++;
                    check.put(nextY, check.getOrDefault(nextY, 0) +1);
                    dfs(nextX, nextY, land);
                }
            }
                    
        }

    }
    
}

 

각 열에서 1이 몇개인지 담은 HashMap과 (처음에는 배열로 저장해서 했고 혹시나 시간줄어들까 싶어서 나중에 HashMap으로도 해봤다 배열로 했던 부분은 주석으로 기록이 남아있다)

dfs 실행시 nextY 즉, 포함된 열들이 있는지 있다면 몇번 나오는지 기록한 HashMap

두개를 비교해서 값이 같지 않다면 dfs 실행

값이 같으면 이전 열에서 구한값을 넣어준 후 다음 for문으로 넘어간다

→ 두 값이 같다면 이전 열에서 계산할때 현재 열에 있는 1 영역 모두가 포함됐다는거니까 굳이 다시 돌지 않고 이전값을 그대로 가져와도 된다는 생각이었다

 

그러나 답은 맞고 여전히 시간초과🤔🤔

오히려 결과가 더 안좋아졌다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 계산 안하고 넘어가는 열이 생기면 시간 초과가 안 날줄 알았는데 맵 만들고 비교하고 이러는게 더 효율성이 안좋은가보다(?? 확실치 않음,,)