원하는 것은 뭐든지

99클럽 코테 스터디 12일차 - 프로그래머스, 도넛과 막대 그래프 본문

개발/문제풀이

99클럽 코테 스터디 12일차 - 프로그래머스, 도넛과 막대 그래프

댕로그😏 2024. 11. 9. 12:37
반응형

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 

문제

풀이

문제 해석

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 전혀 없이 풀었는데 어려운 문제를 이렇게 푼 건 처음인 듯하다. 깔끔한 게 맘에 든다.
반응형
Comments