[BaekJoon] 백준 20364번 부동산다툼(Java)

https://www.acmicpc.net/problem/20364

20364번: 부동산 다툼

---

문제

백준 알고리즘 20364번 오리들의 부동산 다툼 문제이다.

한번에 풀긴 했으나 처음 정답 때 Java11 기준 소요시간에 꼴지를 기록했다 ㅠ-ㅠ

그래서 간단한 수정으로 시간개선을 이룬 것 까지 공유하려고 한다!

문제는 위와같다.

---

문제풀이

배열로 풀면 시간초과가 날거같기도 하고 값의 포함여부를 체크하기에 편리한 HashSet을 사용하여 풀었다.

① 입력받은 수가 점유된 땅이라면 possession 변수에 저장한다.

② 입력받은 수를 2로 나눠가며(부모노드는 *2 or *2+1 이기에) 점유된 땅의 최소값을 구한다.

③ 만약 목적지까지 가는길에 점유된 땅이 없다면 목적지를 점유 해 주고 0을 출력한다.

④ 만약 목적지까지 가는길에 점유된 땅이 있다면 점유지의 최소값(possession)을 출력한다.

---

해결코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Scanner;
import java.util.StringTokenizer;

public class BJ20364 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		StringTokenizer st = new StringTokenizer(br.readLine());
		HashSet<Integer> own = new HashSet<Integer>();
		int cur;
		int possession = 0;
		int search;
		
		int N = Integer.parseInt(st.nextToken()); /* 땅 개수 */
		int Q = Integer.parseInt(st.nextToken()); /* 오리 수*/
	
		for(int i=0; i<Q; i++) {
			cur = Integer.parseInt(br.readLine());
			search = cur;
			while(search > 1) {
				/* 현재 값이 점유된 땅이라면 possession을 갱신 */
				if(own.contains(search)) {
					possession = search;
					/* cnt변수를 통해 점유된 땅이 만났었는지를 체크했는데 시간을 굉장히 잡아먹어서 possession의 값이 0인지 아닌지로 체크 방법 변경 */
				}
				/* 부모노드로 이동 */
				search = search/2;	
			}
			if(possession == 0) {
				/* 가는 길에 점유된 땅이 없었다면 목적지를 점유하고 0을 출력! */
				own.add(cur);
				bw.write(String.valueOf("0\n"));
			} else {
				/* 점유된 땅을 만났었다면 possession의 최솟값을 출력! */
				bw.write(String.valueOf(possession + "\n"));
				possession = 0;
			}
		}
		bw.close();
	}
}

---

소요시간

첫 정답 때 무려 4400ms가 걸렸는데 java11기준 꼴찌 기록이였다 ...

그래서 개선을 위해 두번의 수정과정을 겪었고, 중위권 수준까지는 올라올 수 있었다.. !!

 

①첫번 째 수정 = Scanner 대신 bufferReader를 사용하였다. 입력받는 수가 많지 않아 scanner를 사용해도 무방하다 생각하였는데 이 땅과 오리의 수의 최대값을 생각하지 못했다. (2 ≤ N < 220, 1 ≤ Q ≤ 200,000), 케이스의 수가 많아질수록 

scanner 와 bufferReader간의 유의미 한 차이가 난다는 것을 유념하자.

②두번 째 수정 = while문 안에서 목적지까지 점유지가 있었는지를 체크하기 위해 cnt변수를 통해 if문 안에 들어가면 cnt++을 해주었는데 이 연산 대신에 possession의 초기값을 0으로 설정하고 possession이 0이냐 아니냐 여부로 점유지가 있었는지를 체크 + bufferWriter를 통해 출력

※연산과 bufferWriter를 각각 체크 해 봤는데 bufferWriter가 시간단축에 있어 지대한 영향을 끼친 것으로 보인다 !