- 프로래머스 Lv2 도넛과 막대 그래프 문제
- 해당 문제의 난이도 상승 원인
- 데이터의 양이 적을 때는 괜찮지만 많아질 시, 효율성까지 고려해야함
- 8자 그래프와 도넛 그래프의 유사점으로 인해 판별을 하기위한 조건을 고려해야함
- 해당 문제를 해결한 방법
- 기준이 될 수 있는 생성 노드가 어떤 것인지부터 찾아내기로 하였었고 처음 받은 data 2차원 배열을 그대로 사용하기엔 속도가 걸림돌이 되어 이를 토대로 2개의 long배열을 생성하였다. 각각의 배열은 시작번호를 기준으로, 도착 번호를 기준으로 정렬을 시켜 나중에 생성노드에 연결된 노드의 번호로 검색 시, 모든 항목을 검색하지 않고 해당 번호로만 검색을 하게끔하였다. 또한 해당 배열은 long 자료형을 사용했기 때문에 상위 32비트엔 시작번호를 그리고 하위 32비트에는 도착 번호를 입력하여 차원을 한단계 낮춰서 효율을 증진시켰다.
- 시작 노드를 찾기 위해 이미 시작번호를 기준으로 정렬시킨 배열에서 찾은 최대 번호로 순환문을 돌려서 도착 번호에 없을 경우 + 카운트가 2인 경우로 시작 노드의 번호를 찾음
- 그 다음, 시작 노드에서 연결된 노드의 번호를 찾아 그번호로 시작해 재귀함수를 돌려서 연결된 경우가 없다면 막대그래프로 순환 중에 갈림길이 2개 이상이면 8자 그래프, 시작번호와 도착 번호가 같은 경우 도넛 그래프로 판단하여 카운팅하였다.
- 처음 방식에서 변경한 방식
- 처음
- 처음에는 들어온 자료형이 int라서 무조건 이를 보존하여 사용하려 하였으나, 효율성이 최저 수준이라 이를 변경함
- 변경
- 검색을 통해 long 자료형을 이용해 int 2차원 배열 값을 저장하는 방식이 있어 이를 채택하여사용하기로 하였고 이를 통해 기존에 사용해본적 없던 long에 대한 메소드를 사용해 범위 검색 및 처리법 등을 알게 됨
- 문제의 핵심
- 생성 노드의 번호가 어떤 것인지 찾아내는 방법
- 그 후 생성 노드와 연결된 노드번호를 이용해 그래프의 종류를 밝혀낼 지 판단하는 방법
- 이 문제의 목적
- 들어온 데이터의 양을 최소화 시켜서 속도에 영향이 없게끔 사용하는 것
- long 자료형과 비트처리를 사용해 데이터를 사용하는 것
package DonutsAndGraphs;
import java.util.*;
class DonutsAndGraphs {
static private long[] conEdge;
static private int[] answer;
public int autoSettingInt(long[] targetArr, long value){
int conVal = Arrays.binarySearch(targetArr, value);
return (conVal >= 0) ? conVal : -conVal - 1;
}
public void searchingRoute(int to, int first){
int start = autoSettingInt(conEdge, (long)(to) << 32);
int end = autoSettingInt(conEdge, (long)(to + 1) << 32);
int nextLeng = end - start;
if(nextLeng <= 0){
answer[2] = answer[2] + 1;
return;
}
else if(nextLeng >= 2){
answer[3] = answer[3] + 1;
return;
}
int next = (int)(conEdge[start] & 0xFFFFFFFFL);
if(first == next){
answer[1] = answer[1] + 1;
return;
}
searchingRoute(next, first);
}
public int[] solution(int[][] edges) {
answer = new int[]{0, 0, 0, 0};
int data_length = edges.length;
long[] rvsConEdge = new long[data_length];
conEdge = new long[data_length];
for(int i = 0; i < data_length; i++){
conEdge[i] = ((long)edges[i][0] << 32) | ((long)edges[i][1] & 0xffffffffL);
rvsConEdge[i] = ((long)edges[i][1] << 32) | ((long)edges[i][0] & 0xffffffffL);
}
Arrays.sort(conEdge);
Arrays.sort(rvsConEdge);
int max = (int)(conEdge[data_length-1] >>> 32); // 정렬시킨 이유
int startPoint = -1;
int startIdx = -1;
int endIdx = -1;
for(int i = 1; i <= max; i++){
long rvs_from = ((long)i) << 32;
long rvs_to = ((long)(i+1)) << 32;
int con_rvs_to = autoSettingInt(rvsConEdge, rvs_to);
int con_rvs_from = autoSettingInt(rvsConEdge, rvs_from);
int rvs_dist = con_rvs_to - con_rvs_from;
if(rvs_dist == 0){
int con_to = autoSettingInt(conEdge, rvs_to);
int con_from = autoSettingInt(conEdge, rvs_from);
int dist = con_to - con_from;
if(dist >= 2){
startPoint = i;
startIdx = con_from;
endIdx = con_to;
break;
}
}
}
// 연결된 곳 저장
int[] links = new int[endIdx - startIdx];
int idx = 0;
for(int i = startIdx; i < endIdx; i++){
links[idx] = (int)(conEdge[i] & 0xFFFFFFFFL);
idx++;
}
answer[0] = startPoint;
for(int i = 0; i < links.length; i++){
searchingRoute(links[i], links[i]);
}
return answer;
}
public static void main(String[] args) {
int[][] edges = {
{4, 11}, {1, 12}, {8, 3}, {12, 7}, {4, 2},
{7, 11}, {4, 8}, {9, 6}, {10, 11}, {6, 10},
{3, 5}, {11, 1}, {5, 3}, {11, 9}, {3, 8}
};
DonutsAndGraphs obj = new DonutsAndGraphs();
System.out.println("결과 : " + Arrays.toString(obj.solution(edges)));
}
}