[알고리즘풀이]백준 20364 : 부동산 다툼 JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 20364번 부동산 다툼을 풀었습니다. 이를 정리해보고자 합니다.

20364번: 부동산 다툼

본문

1) 문제

오리 너무 귀여워요...ㅠㅠㅠㅠ

2) 과정

처음 풀 트리로 풀었던 문제입니다! 푸는데는 1시간 정도 걸렸고 (밖에서 짬날때 풀다보니 IDE가 없어서 IOException같은 에러 하나하나 해결하는 것도 오래걸리더라구요 ㅠㅠㅠㅠ 1주정도 됐는데도 자꾸 깜빡해요...) 에러없이 한번에 성공했습니다! 

 

처음 풀었던 방식은 Tree를 만들고, 루트에서부터 오리를 보내 가는 길에 소유주가 있는 땅을 만나면 땅번호를 출력하자! 는 방식이었는데요...! 이것도 땅을 Node[]를 사용하다가 int[][]로 바꿨음에도 시간이 오래걸리더라고요 ... 통과는 했는데 JAVA11 유저 기준 뒤에서 3등이라는 사실을 믿을 수 없어서 조금 더 개선해 시간과 길이 모두 줄여봤어요!

 

제가 풀었던 방식은 다음처럼 설명할 수 있습니다!

1) 문제의 트리구조의 규칙성을 파악하여 각 오리의 목적지를 받아 nowGoal에 저장하고

2) nowGoal을 2로 나눈 것의 몫으로 목적지에서 루트(1)까지 타고 올라가며 이미 주인이 있는지 owned(주인 목록)에 검색하여

3) 주인있는 땅이면 땅번호를 blockedNum에 저장하여 루트와 가장 가까운 주인있는 땅을 for문의 마지막엔 blockedNum에 담게 합니다.

4) 이때 주인 있는 땅을 지난 적 없다면 blockedNum의 초기값인 0이 담겨져 있기 때문에 요구되는 결과대로 0이 출력되고

5) 주인있는 땅을 지났다면 blockedNum에 저장된 값이 출력된다.
6) 출력을 마친 뒤 주인있는 땅을 지난 적 없을 땐 owned에 nowGoal을 넣어 주인목록을 업데이트한다.

 

코드 길이도 줄이고 속도도 생각하다보니 숏코딩 3위할만큼 줄여서 Main하나로 전체 코드가 끝이 되었습니다!

 

2-1) main

public static void main(String[] args) throws IOException{
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        HashSet<Integer> owned = new HashSet<>();
        // Logic
        // go ahead ducks!
        for(int i=1;i<=q;i++){
            // set nowGoal
            int nowGoal = Integer.parseInt(br.readLine());
            // check is route already blocked
            int blockedNum = 0;
            for(int tmp=nowGoal;tmp>=2;tmp/=2) if(owned.contains(tmp)) blockedNum = tmp;
            // Output
            System.out.println(blockedNum);
            // for next
            if(blockedNum==0) owned.add(nowGoal);
        }
    }

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

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

public class Main{
    // Main
    public static void main(String[] args) throws IOException{
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        HashSet<Integer> owned = new HashSet<>();
        // Logic
        // go ahead ducks!
        for(int i=1;i<=q;i++){
            // set nowGoal
            int nowGoal = Integer.parseInt(br.readLine());
            // check is route already blocked
            int blockedNum = 0;
            for(int tmp=nowGoal;tmp>=2;tmp/=2) if(owned.contains(tmp)) blockedNum = tmp;
            // Output
            System.out.println(blockedNum);
            // for next
            if(blockedNum==0) owned.add(nowGoal);
        }
    }
}

 

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

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

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