[알고리즘풀이]백준 9489 : 사촌 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 9489번 사촌을 풀었습니다. 이를 정리해보고자 합니다.

9489번: 사촌

 

본문

1) 문제

2) 과정

NoSuchElement... 진짜... 검색을 하고 다른 분들을 참고해도 왜 자꾸 틀렸다고 하는거지???? 하면서 의문만 수만개 갖고 고민했어요. 그리고 깨달았습니다. n이나 k가 1일때 0을 출력하게 한다는 건 그 뒤에 값을 읽지 않으니 StringTokenizer가 읽어오는 부분이 어긋난다는 것을 말이죠. 그래서 7시간만에 이 부분을 지워냈더니 성공했어요. 이제 보면 멍청한 실수지만 당사자로 있을 땐 너무 어렵고,, 포기하고 싶고,,, (하지만 포기는 없습니다..)(자세한 저의 삽질로그는 깃헙가시면 볼 수 있어요 ...)

 

이번 코드의 방식을 빠르게 설명드리면 

1. tree에 입력받은 값과 부모를 저장해 인덱싱으로 그룹을 찾아갈 수 있도록 한다.
2. 그리고 이와 함께 k의 위치(kIdx)를 찾아 저장한다.
3. tree를 돌면서 k와 부모는 다르나 조부모는 같은 경우 ans를 증가시켜 그 결과를 StringBuilder에 append한다.
4. StringBuilder의 값을 출력하며 마무리한다.

 

단순 요약하면 "입력받기 -> 트리만들기 -> k의 조부모 찾기 -> 출력하기"로도 볼 수 있습니다. 저는 tree만드는게 가장 어려웠어요 ㅠㅠㅠㅠ 

 

다 main에 들어있는거긴한데, main을 입력, 로직, 출력으로 나눠서 보여드리고자해요!

 

2-1) Input

	// Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true){
            // get n,k info
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            // end condition            
            if(n==0 && k==0) break;
            // input node values and make tree
            int[][] tree = new int[n][2]; //[노드의 입력 인덱스][0=자신의값,1=부모의 인덱스]
            int kIdx = 0; // k의 인덱스
            int pIdx = 0; // 트리를 만들때 부모 노드가 뭔지 기억하기 위함.
            int prev = -1; // 이전 값을 담기위한 변수
            st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++){
                // get a node number
                int input = Integer.parseInt(st.nextToken());
                // save k's Idx
                if(input==k) kIdx = i;
                // if not continuous pIdx++
                if(prev+1!=input&&i>1) pIdx++;
                // if first Input -> parent Idx = -1 / other -> pIdx
                tree[i] = new int[]{input,i==0?-1:pIdx};
                // set prev for the next
                prev = input;
            }

입력부분은 위와 같아요. 예전이라면 tree를 new Node[]로 만들었겠지만 요즘엔 값 2개,3개를 담은 클래스를 만드는것보단 array의 배열을 하나 늘리자! 라는 마음이라 tree를 [노드를 입력받을 때의 인덱스][0=자신의 값, 1=부모의 인덱스]로 만들었어요.

 

값을 읽을 때 처리해야 했던 건 다음과 같아요.

1) k의 인덱스 찾기

2) 연속 여부에 따라 pIdx의 증가

3) 루트의 부모값은 따로 처리

 

이 점만 고려해서 짜면 무리없이 인풋은 완성할 수 있답니다!

 

2-2) Logic + Output

	// Logic
            int ans = 0; // 정답을 담을 변수(k의 사촌의 수)
            int kpIdx = tree[kIdx][1]; // k의 부모 인덱스
            for(int idx = 1; idx < n; idx++){
            int iVal = tree[idx][1]; // 현재 노드의 부모 인덱스
            if(tree[kpIdx][0] != tree[iVal][0] // 부모는 다른데
            && tree[kpIdx][1] == tree[iVal][1]) ans++; // 부모의부모(조부모)는 같다면 ans++
            }
            // follow the answer
            sb.append(ans).append("\n");
        }
        // Output
        System.out.print(sb.toString());
    }

output이 짧아서 그냥 로직과 함께 설명할게요!

 

로직부분의 주요 부분은 아무래도 이부분이 아닐까 싶어요

if(tree[kpIdx][0] != tree[iVal][0] // 부모는 다른데
&& tree[kpIdx][1] == tree[iVal][1]) ans++; // 부모의부모(조부모)는 같다면 ans++

이 부분만 생각한다면 금방 답이 나올겁니다!

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다. 깃헙엔 이런저런 주석도 마구 달아놨는데, 블로그엔 최소한의 주석만 달도록 정리했습니다. 세부적인 주석이 궁금하시다면 아래쪽에 링크된 깃헙 레포짓토리에 방문하여 확인해주세요!

이번건 진짜 제가 개선해나가는 과정 에러로그까지 알차게 담았습니다...!!! 꽤나 유익하실거라 생각합니다.

package sujeong.tree;

import java.util.*;
import java.io.*;

public class BOJ9489 {
	public static void main(String[] args) throws IOException{
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true){
            // get n,k info
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            // end condition            
            if(n==0 && k==0) break;
            // input node values and make tree
            int[][] tree = new int[n][2]; //[노드의 입력 인덱스][0=자신의값,1=부모의 값]
            int kIdx = 0; // k의 인덱스
            int pIdx = 0; // 트리를 만들때 부모 노드가 뭔지 기억하기 위함.
            int prev = -1; // 이전 값을 담기위한 변수
            st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++){
                // get a node number
                int input = Integer.parseInt(st.nextToken());
                // save k's Idx
                if(input==k) kIdx = i;
                // if not continuous pIdx++
                if(prev+1!=input&&i>1) pIdx++;
                // if first Input -> parent Idx = -1 / other -> pIdx
                tree[i] = new int[]{input,i==0?-1:pIdx};
                // set prev for the next
                prev = input;
            }
            // Logic
            int ans = 0; // 정답을 담을 변수(k의 사촌의 수)
            int kpIdx = tree[kIdx][1]; // k의 부모 인덱스
            for(int idx = 1; idx < n; idx++){
                int iVal = tree[idx][1]; // 현재 노드의 부모 인덱스
                if(tree[kpIdx][0] != tree[iVal][0] // 부모는 다른데
                && tree[kpIdx][1] == tree[iVal][1]) ans++; // 부모의부모(조부모)는 같다면 ans++
            }
            // follow the answer
            sb.append(ans).append("\n");
        }
        // Output
        System.out.print(sb.toString());
    }
}

 

소요시간, 아이디어, 에러로그 등 더 자세히 이번 문제를 보고싶으시다면, 아래 깃헙 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/tree/BOJ9489.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비