[Coding Test] 석유 시추 / C++

https://school.programmers.co.kr/learn/courses/30/lessons/250136?language=cpp#

프로그래머스

 

가장 먼저 시도한 방법은 각 열에 대한 배열을 두고 DFS로 석유 덩어리를 탐색하여 해당하는 모든 열에 덩어리의 크기를 더해주는 방식을 사용했다.

#include <iostream>
#include <vector>
using namespace std;

inline bool OutRange(vector<vector<int>> land, int x, int y)
{
    if(x < 0) return true;
    if(y < 0) return true;
    if(land.size() <= y) return true;
    if(land[0].size() <= x) return true;

    return false;
}
int minX;
int maxX;
int oilSize;
void dfs(vector<vector<int>>* land, int x, int y)
{

    if(OutRange(*land, x,y)) return;
    if((*land)[y][x] == 0) return;

    if(minX > x) minX = x;
    if(maxX < x) maxX = x;
    
    (*land)[y][x] = 0;

    dfs(land, x+1, y);
    dfs(land, x-1, y);
    dfs(land, x, y+1);
    dfs(land, x, y-1);


    oilSize++;
}


int solution(vector<vector<int>> land) {
    int answer = 0;
    vector<int> oil(land[0].size());
    for (int i = 0; i < land.size(); i++)
    {
        for(int j = 0; j< land[0].size(); j++)
        {
            minX = 499;
            maxX = 0;
            oilSize = 0;
            dfs(&land, j, i);

            if(oilSize > 0)
            {
                for(int k = minX; k<=maxX; k++)
                {
                    oil[k] += oilSize;
                }
            }
        }
    }

    for (int i = 0; i < oil.size(); i++)
    {
        if(oil[i] > answer) answer = oil[i];
    }
    return answer;
}

채점 결과

정확성: 60.0

효율성: 0.0

합계: 60.0 / 100.0

 

정확성은 만점이 나왔지만 효율성은 모두 탈락했다.

문제는 OutRange의 land를 참조가 아닌 값으로 전달하고 있었다.

즉 land가 OutRange가 실행 될 때 마다 복제되고 있던것.

inline bool OutRange(vector<vector<int>> land, int x, int y)
{
    if(x < 0) return true;
    if(y < 0) return true;
    if(land.size() <= y) return true;
    if(land[0].size() <= x) return true;

    return false;
}

 

그래서 다음과 같이 값으로 전달하는 대신 참조하도록 바꿔주었다.

inline bool OutRange(const vector<vector<int>>& land, int x, int y) {
    if(x < 0) return true;
    if(y < 0) return true;
    if(land.size() <= y) return true;
    if(land[0].size() <= x) return true;

    return false;
}

 

이것만으로 시간이 크게 단축되어 효율성도 모두 통과 할 수 있었다.

	개선 전	개선 후
테스트 1 〉	(0.04ms, 3.63MB)	(0.01ms, 4.14MB)
테스트 2 〉	(0.31ms, 4.15MB)	(0.01ms, 4.13MB)
테스트 3 〉	(0.05ms, 4.2MB)	(0.01ms, 4.17MB)
테스트 4 〉	(0.27ms, 4.15MB)	(0.01ms, 4.14MB)
테스트 5 〉	(0.22ms, 4.21MB)	(0.01ms, 4.14MB)
테스트 6 〉	(5.58ms, 4.23MB)	(0.03ms, 4.14MB)
테스트 7 〉	(11.39ms, 3.59MB)	(0.04ms, 3.75MB)
테스트 8 〉	(3.50ms, 4.14MB)	(0.02ms, 4.13MB)
테스트 9 〉	(79.53ms, 4.2MB)	(0.11ms, 4.2MB)