❓문제설명
[PCCP 기출문제] 2번 / 석유 시추
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.
예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.
시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.
- 시추관의 위치획득한 덩어리총 석유량
| 1 | [8] | 8 |
| 2 | [8] | 8 |
| 3 | [8] | 8 |
| 4 | [7] | 7 |
| 5 | [7] | 7 |
| 6 | [7] | 7 |
| 7 | [7, 2] | 9 |
| 8 | [2] | 2 |
오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.
석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
- 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
- land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
- land[i][j]는 0 또는 1입니다.
- land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.
정확성 테스트 케이스 제한사항
- 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
- 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100
효율성 테스트 케이스 제한사항
- 주어진 조건 외 추가 제한사항 없습니다.
입출력 예
| [[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]] | 9 |
| [[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]] | 16 |
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
입출력 예 #2
시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.
시추관의 위치획득한 덩어리총 석유량
| 1 | [12] | 12 |
| 2 | [12] | 12 |
| 3 | [3, 12] | 15 |
| 4 | [2, 12] | 14 |
| 5 | [2, 12] | 14 |
| 6 | [2, 1, 1, 12] | 16 |
6번 열에 시추관을 설치하면 크기가 2, 1, 1, 12인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 16으로 가장 많습니다. 따라서 16을 return 해야 합니다.
🧐 문제풀이
1️⃣ 1차시도
각 시추관(x)의 석유 저장량을 알아내고자 이중 for문을 사용하면서 값이 1인 곳을 발견하면 bfs로 계산하였다.
하나의 시추 위치를 계산할때 방문한 위치를 visit true로 해버리면 다음 시추관에서는 방문할 수 없어 카운팅이 불가능하기 때문에
시추관의 위치가 변경 될때마다 (y의 for문을 시작할때마다) visit 배열을 새로 만들었다. (이게 패착)
정확성은 성공했으나 효율성에서 와장창 실패하였다.
import java.util.*;
class Solution {
public int solution(int[][] land) {
int max = Integer.MIN_VALUE;
int n = land.length; // 세로길이
int m = land[0].length; // 가로길이
int [] dn = {1,-1,0,0};
int [] dm = {0,0,1,-1};
for(int i = 0; i<m; i++){
int amount = 0;
boolean [][] visit = new boolean[n][m];
for(int j = 0; j <n;j++){
if(land[j][i] == 1 && visit[j][i] == false){
Queue<int[]> q = new LinkedList<>();
amount++;
visit[j][i] = true;
q.offer(new int[]{j,i});
while (!q.isEmpty()){
int size = q.size();
for(int s = 0; s< size; s++){
int [] c = q.poll();
for(int d = 0; d < 4; d++){
int nn = c[0] + dn[d];
int nm = c[1] + dm[d];
if(nn > -1 && nm > -1 && nn < n && nm < m && land[nn][nm] == 1 && visit[nn][nm] == false){
amount++;
visit[nn][nm] = true;
q.offer(new int[]{nn,nm});
}
}
}
}
}
}
max = Math.max(max,amount);
}
int answer = max;
return answer;
}
}
🥲..
2️⃣ 2차시도
아무래도 모든 석유 위치를 방문하면서 저장량을 계산하는게 시간이 오래걸리는 이유라고 생각되었다.
아예 초창기에는 방문한 위치의 값을 0으로 바꿔서 재방문을 하지 못하게 짰었는데
그렇게 하면 오답이 나와서 1차시기의 방문배열을 새로 생성하는 코드로 변경하였다.
다시 초기로 돌아가서 재방문을 하지 못하지만, 타 위치의 시추관에서도 석유저장량을 계산할 수 있도록 코드를 만들어보도록 했다.
그렇게 해서 생각해 본 방법이 하나의 석유저장량을 계산할때 방문한 시추위치(x)을 set에 저장한 뒤, (중복제거가 되기에 set을 사용)
하나의 석유량이 계산되면 지나왔던 시추위치마다 석유량을 합산하는 것이다.
예를 들어, 저장량 5의 석유가 시추관 1,2,3의 위치에 걸쳐 분포하고 있다면. 시추관 1이 처음에 bfs로 석유저장량을 계산할때
set에 석유위치 1,2,3을 넣어두고 5의 석유량 계산을 마치면, 각 위치의 석유량을 담고 있는 배열의 1,2,3 인덱스에 5를 더한다.
모든 1이 없어질때까지 석유량을 계산하고 마지막에는 각 시추위치의 석유량을 담고 있는 배열 중에 가장 큰 값을 답으로 return한다.
！제출코드
import java.util.*;
class Solution {
public int solution(int[][] land) {
int n = land.length; // 세로길이
int m = land[0].length; // 가로길이
int [] dn = {1,-1,0,0};
int [] dm = {0,0,1,-1};
int [] oil = new int[m];
for(int i = 0; i<m; i++){
for(int j = 0; j <n;j++){
if(land[j][i] == 1){
Queue<int[]> q = new LinkedList<>();
int amount = 1;
land[j][i] = 0;
q.offer(new int[]{j,i});
Set<Integer> set = new HashSet<>();
while (!q.isEmpty()){
int size = q.size();
for(int s = 0; s< size; s++){
int [] c = q.poll();
set.add(c[1]); // x축의 위치 저장
for(int d = 0; d < 4; d++){
int nn = c[0] + dn[d];
int nm = c[1] + dm[d];
if(nn > -1 && nm > -1 && nn < n && nm < m && land[nn][nm] == 1){
amount++;
land[nn][nm] = 0;
q.offer(new int[]{nn,nm});
}
}
}
}
for(int st : set) oil[st] += amount; // 방문했었던 석유 위치에 저장량 합산
}
}
}
int answer = Integer.MIN_VALUE;
for(int o : oil) answer = Math.max(answer,o);
return answer;
}
}
✅ 풀이 요약
- 각 시추관 위치마다 담겨있는 석유량을 저장하는 배열을 하나 만들고(배열 oil), 배열 중 가장 큰 값을 구하려고 한다.
- y축을 1차 for문으로 x축을 2차 for문으로 실행한다
- 석유가 있는 곳, 배열의 값이 1이면 그 지점을 시작으로 상하좌우를 탐색하며 석유(1)를 계산한다.
- 탐색하면서 석유가 있던 시추관 위치(x축)를 set에 넣고, 재방문 하지 않도록 1을 0으로 변경한다.
- 한 건의 석유량이 계산 완료되면 set에 있던 방문 시추관 위치에 석유량을 더한다 (ex. oil[set 항목] += 석유량)
- 배열 중에 가장 큰 값을 구한다.
'개발 공부 > 코딩테스트 연습' 카테고리의 다른 글
| [프로그래머스 Lv2][JAVA] 연속된 부분 수열의 합 (0) | 2024.08.24 |
|---|---|
| [프로그래머스 Lv2][JAVA] 두 원 사이의 정수 쌍 (1) | 2024.08.22 |
| [프로그래머스 Lv2][JAVA] 요격 시스템 (0) | 2024.08.17 |
| [프로그래머스 Lv2][JAVA][PCCP 기출문제] 3번 / 아날로그 시계 (0) | 2024.08.16 |
| [프로그래머스 Lv2][JAVA] 도넛과 막대 그래프 (0) | 2024.08.14 |