알고리즘 문제 풀이 / 프로그래머스 (programmers) - 도넛과 막대 그래프
문제 내용을 설명하기엔 너무 길어서 문제에 대한 요약 따로 하지 않고, 문제의 제한사항과 내가 푼 풀이법에 대해서만 설명하겠다.
▏문제 설명
제한사항
- 1 ≤ edges의 길이 ≤ 1,000,000
- edges의 원소는 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
- 1 ≤ a, b ≤ 1,000,000
- 문제의 조건에 맞는 그래프가 주어집니다.
- 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.
▏문제 풀이
각 그래프의 구분하는데 중점을 두고 문제를 해결했다.
제일 쉽게 구분할 수있는 것은 막대 그래프였다. 다른 두 그래프와는 달리, 그래프의 꼭대기 정점은 다른 곳으로 향하는 간선이 없다. 다시 말해, 이 정점에서 출발하는 간선이 없다는 것이다.
두 번째로 구분한 것은 8자 모양 그래프다. 내가 생각한 이 그래프의 특징은, 모든 정점이 주고 받는 간선을 가지고 있어 총 2개의 간선이 연결되어 있다. 또한, 8자 모양의 중심은 4개의 간선이 존재하게 된다. 때문에 주고 받는 간선이 각각 2개씩 있는 정점을 찾는 방법으로 문제를 해결했다.
마지막으로 구분해야할 그래프는 도넛 모양이다. 이 문제를 해결하면서 가장 고민이 되었던 부분은 도넛과 8자 모양을 구분하는 것이었다. 정점 간의 연결 관계를 기억하지 않고 간선의 수만을 고려하며 해결하고 싶었지만, 그렇게 할 경우 8자 모양과 도넛을 구분하기 어려워 보였다. 그러던 중 번뜩이게 생각한 아이디어는, 너무나 간단하게도 임의의 정점에서 반드시 모든 그래프로 1개의 간선을 보내야 한다는 점을 이용하여, 해당 정점에서 보내는 간선의 개수에서 다른 두 그래프의 총 개수를 빼면 도넛이 나오는 것이었다.
그렇게 풀게된 풀이는 아래와 같다.
public static int[] solution(int[][] edges) {
int[] answer = new int[4];
Map<Integer, Integer> fromMap = new HashMap<>(); //주는애
Map<Integer, Integer> toMap = new HashMap<>(); // 받는애
int count = 0;
int fromNum = 0;
int toNum = 0;
for(int i = 0; i < edges.length; i++){
fromNum = edges[i][0];
toNum = edges[i][1];
fromMap.put(fromNum, fromMap.getOrDefault(fromNum,0)+1);
toMap.put(toNum,toMap.getOrDefault(toNum,0)+1);
if(count < fromNum)count = fromNum;
if(count < toNum)count = toNum;
}
for(int i = 1; i <= count; i++){
if(toMap.get(i) == null){
if(fromMap.get(i) >= 2){
answer[0] = i;
}
}else if (fromMap.get(i)== null){
answer[2]++;
}else if( fromMap.get(i) == 2 && toMap.get(i) >= 2){
answer[3]++;
}
}
answer[1] = fromMap.get(answer[0]) - answer[2] - answer[3];
return answer;
}
위와 같이 풀었을 때, 마지막 테스트 케이스에서 런타임 에러가 났다.
어느 부분을 더 효율적으로 처리할 수 있을지 고민해 보았을 때, 정점의 개수를 세는 과정을 개선할 수 있을 것이라는 생각이 들었다. 기존엔 각 정점을 'count' 변수를 사용하여 일일이 비교하는 방식을 사용했다. 그러나 이는 번거로울 뿐 아니라 실행시간도 오래걸릴 것으로 판단했다. 그래서 HashSet 을 활용하여 중복된 원소를 허용하지 않고 모든 정점을 세는 방법을 선택했다. 변경된 코드는 아래와 같다.
▏문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/258711
댓글