원하는 것은 뭐든지
99클럽 코테 스터디 12일차 - 프로그래머스, 도넛과 막대 그래프 본문
반응형
문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다.
문제
풀이
문제 해석
1. 도넛, 막대, 8 자 모양의 그래프들이 여러 개 있다.
2. 이 그래프 사이에 한 정점을 넣고 그 정점과 그래프의 어떤 정점과 모두 연결한다.
3. 전체로 이어진 그래프에 무작위로 값을 넣는다. 1~1,000,000
4. 들어간 정점의 번호와 각 그래프의 개수를 구하라
5. 모든 그래프의 수는 두개 이상이다.
문제 풀이
1. 각 그래프의 특성을 알아야 한다.
2. 도넛그래프는 무조건 한개씩의 in과 out을 가진다.
3. 막대그래프는 마지막 정점은 out이 없다.
4. 8자 그래프는 두 개의 도넛그래프를 이어주는 두 개의 in, out을 가지는 정점이 하나 있다.
5. 삽입 정점은 in은 없고 out이 두 개 이상이다.
6. 주의 할 점은 막대그래프에서 out이 0인 것만 찾게 되면 틀린다. 그 이유는 그래프에 들어가는 값이 1,2,3 순차적인 게 아니고 범위 내에서 아무렇게나 들어가기 때문이다.
소스코드
class Solution {
public int[] solution(int[][] edges) {
int addNum = 0;
int donut = 0;
int stick = 0;
int eight = 0;
//크기 찾기
int maxIdx = 0;
for(int[] edge : edges){
maxIdx = Math.max(maxIdx,Math.max(edge[0],edge[1]));
}
//값 넣기
int[] in = new int[maxIdx];
int[] out = new int[maxIdx];
for(int[] edge : edges){
out[edge[0]-1]++;
in[edge[1]-1]++;
}
//삽입된 정점 찾기
//in이 없고 out이 두개
for (int i = 0; i < maxIdx; i++) {
if(in[i] == 0 && out[i] >= 2){
addNum = i+1;
}
}
//8자 찾기
//두개의 in/out을 가지는 정점의 개수
for (int i = 0; i < maxIdx; i++) {
if(in[i] >= 2 && out[i] == 2){
eight++;
}
}
//막대 찾기
//0이지만 들어오는 값이 없을 수가 없다.
for (int i = 0; i < maxIdx; i++) {
if(out[i] == 0){
if(in[i] != 0){
stick++;
}
}
}
donut = out[addNum-1] - eight - stick;
return new int[]{addNum, donut, stick, eight};
}
}
TIL
- 들어가는 값이 순차적이라고 생각하고 풀이해서 오래걸렸다.
- import 전혀 없이 풀었는데 어려운 문제를 이렇게 푼 건 처음인 듯하다. 깔끔한 게 맘에 든다.
반응형
'개발 > 문제풀이' 카테고리의 다른 글
99클럽 코테 스터디 14일차 - 프로그래머스, 미로 탈출 명령어 (0) | 2024.11.11 |
---|---|
99클럽 코테 스터디 13일차 - 백준, 미로 보수 (1) | 2024.11.10 |
99클럽 코테 스터디 11일차 - 백준, 도서관 (0) | 2024.11.07 |
99클럽 코테 스터디 10일차 - 백, 좋다 (0) | 2024.11.06 |
99클럽 코테 스터디 9일차 - 프로그래머, 다단계 칫솔 판매 (0) | 2024.11.05 |
Comments