uk's study

# https://ukyonge.tistory.com/21 문제와 같이 분할 정복 문제로써 행렬을 나누어 진행하면 됨 

https://ukyonge.tistory.com/21에서는 9개로 분할하였지만, 이 문제에서는 4개로 분할하여 해결

package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p1992 {
	static int arr[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		arr = new int[N][N];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			String str = br.readLine();
			for(int j=0; j<N; j++) {
				arr[i][j] = (str.charAt(j)-'0');
			}
		}
		solve(N,0,0);
		
		
	}
	
	public static void solve(int n, int x, int y) {
		if(n==1) {
			System.out.print(arr[y][x]);
			return;
		}
		
		if(check(n, x, y)) {
			System.out.print(arr[y][x]);
		}else {
			int div = n/2;
			System.out.print('(');
			solve(div, x, y);
			solve(div, x+div, y);
			solve(div, x, y+div);
			solve(div, x+div, y+div);
			System.out.print(')');
		}
	}
	
	public static boolean check(int n, int x, int y) {
		
		int val = arr[y][x];
		
		boolean rs=true;
		
		for(int i=y; i<y+n; i++) {
			for(int j=x; j<x+n; j++) {
				if(val != arr[i][j]) {
					rs = false;
					return rs;
				}
			}
		}
		
		return rs;
	}
}

# 하노이탑 알고리즘만 알면 바로 풀 수 있던 문제. 그러나 출력문이 많아 System.out.print를 사용하면 시간 초과 발생하니 유의할것

package bj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class p11729 {
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		System.out.println((int)Math.pow(2, N)-1);
		hanoi(N,1,2,3);
		bw.close();
	}
	
	public static void hanoi(int N, int a, int b, int c) throws IOException {
		if(N>0) {
			hanoi(N-1, a, c, b);
			bw.write(a+" "+c+"\n");
			hanoi(N-1, b, a, c);
		}
	}
}

# 행렬을 분할하여 함수를 짜면 쉽게 해결할 수 있는 문제, 편리하게 진행하기 위해 check 함수로 분할 여부 체크

package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p1780 {
	static int arr[][];
	static int result[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		result = new int[3];
		StringTokenizer st;
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//종이가 모두 같은 수로 되어 있는지 체크
		solve(N,0,0);
		for(int i:result)
			System.out.println(i);
	}
	
	public static void solve(int n,int x, int y) {
		if(n==1) {
			int val = arr[y][x]+1;
			result[val]++;
			return;
		}
		
		if(check(n, x ,y)) {
			int val = arr[y][x]+1;
			result[val]++;
		}else {
			int next = n/3;
			
			solve(next, x, y);
			solve(next, x + next, y);
			solve(next, x + 2*next, y);
			
			solve(next, x, y + next);
			solve(next, x + next, y+next);
			solve(next, x + 2*next, y+next);
			
			solve(next, x, y + 2 * next);
			solve(next, x + next, y + 2 * next);
			solve(next, x + 2 * next, y + 2 * next);
			
		}
	}
	
	public static boolean check(int n, int x, int y) {
		int val = arr[y][x];
		boolean rs = true;
		for(int i=y; i<y+n; i++) {
			for(int j=x; j<x+n; j++) {
				if(val != arr[i][j]) {
					rs = false;
					return rs;
				}
			}
		}
		return rs;
	}
}

# 처음에는 병합 정렬로 접근하였음. 출력에 있어 System.out.print는 당연히 시간 초과, Stringbuilder, BufferWriter를 사용했는데도 시간 초과가 떠서 그냥 PriorityQueue를 사용하여 해결하였다.

질문 검색에 들어가서 확인도 해봤는데 자바에는 시간리미트를 수정해줘야 할거 같다. 어디에서 봤는데 Arrays.Sort로도 성공한 사람이 있다고 하였음.

< 정답 코드 >

package bj;

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

public class p11728 {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		PriorityQueue pq = new PriorityQueue<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens())
			pq.offer(Integer.parseInt(st.nextToken()));
		
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens())
			pq.offer(Integer.parseInt(st.nextToken()));
		
		while(!pq.isEmpty())
			bw.write(pq.poll()+" ");
		
		bw.close();
	}
}

병합 정렬 코드도 첨부는 하지만, 통과는 못한 코드입니다. 틀린게 보이신다면 조언 부탁드립니다.

package bj;

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

public class p11728_timeout {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int arr[] = new int[N+M];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=N; i<M+N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		mergeSort(arr, 0, M+N-1);
//		StringBuilder sb = new StringBuilder();
		for(int i=0; i<M+N; i++) {
			bw.write(arr[i]+" ");
//			sb.append(arr[i]+" ");
		}
		bw.flush();
		
	}
	public static void mergeSort(int arr[], int m ,int n) {
		if(m<n) {
			int middle = (m+n)/2;
			mergeSort(arr, m, middle);
			mergeSort(arr, middle+1, n);
			merge(arr,m, middle, n);
		}
	}
	
	public static void merge(int arr[], int m, int middle, int n) {
		int i = m;
		int j = middle+1;
		int t=1;
		int tmp[] = new int[arr.length+1];
		
		while(i<=middle && j<=n) {
			if(arr[i] < arr[j]) {
				tmp[t++] = arr[i++];
			}else {
				tmp[t++] = arr[j++];
			}
		}
		
		while(i<=middle) {
			tmp[t++] = arr[i++];
		}
		while(j<=n)
			tmp[t++] = arr[j++];
		
		i = m;
		t = 1;
		
		while(i <= n)
			arr[i++] = tmp[t++];
	}
}

# BFS 두 번 사용하여, 첫 번째에는 BFS를 통해 그룹화 시키고 두 번째에는 그룹화 된 배열을 가지고 BFS를 수행하며 최단거리를 구함

package bj;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class p2146 {
	static int arr[][];
	static int graph[][];
	static int n;
	static int moveX[] = {0,1,0,-1};
	static int moveY[] = {-1,0,1,0};
	static boolean visit[][];
	static int cnt=1;
	static int rs=9999;
	static ArrayList<Point>[] arrList;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		arr = new int[n][n];
		visit = new boolean[n][n];
		graph = new int[n][n];
		arrList = new ArrayList[10001];
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(arr[i][j] == 1 && !visit[i][j]) {
					arrList[cnt-1] = new ArrayList<>();
					make_graph(new Point(j,i), cnt);
					cnt++;
					
				}
			}
		}
//		for(int i=0; i<n; i++) {
//			for(int j=0; j<n; j++) {
//				System.out.print(graph[i][j] +" ");
//			}System.out.println();
//		}
		
		
		for(int i=0; i<cnt-1; i++) {
			bfs(arrList[i]);
		}
		System.out.println(rs);
		
	}
	public static void bfs(ArrayList<Point> ar) {
		visit = new boolean[n][n];
		Queue<Point> q = new LinkedList<>();
		int val = graph[ar.get(0).y][ar.get(0).x];
		
		for(int i=0; i<ar.size(); i++) {
			int x = ar.get(i).x;
			int y = ar.get(i).y;
			visit[y][x] = true;
			q.add(new Point(x,y));
		}
		int result=0;
		while(!q.isEmpty()) {
			int size = q.size();
			for(int i=0; i<size; i++) {
				Point p = q.poll();
				int x = p.x;
				int y = p.y;
				
				for(int d=0; d<4; d++) {
					int newY = y + moveY[d];
					int newX = x + moveX[d];
					if(0<=newX && newX<n && 0<=newY && newY<n) {
						if(graph[newY][newX]!=0 && graph[newY][newX] != val) {
							
							rs = Math.min(rs, result);
//							System.out.println(y+" "+x+ " // " +newY+" "+newX + " // "+result);
							return;
						}else if(graph[newY][newX]==0 && !visit[newY][newX]) {
							visit[newY][newX] = true;
							q.add(new Point(newX,newY));
						}
					}
				}
				
				
			}
			result++;
		}
	}
	public static void make_graph(Point p, int cnt) {
		
		Queue<Point> queue = new LinkedList<Point>();
		
		queue.add(p);
		
		while(!queue.isEmpty()) {
			Point tmp = queue.poll();
			
			int x = tmp.x;
			int y = tmp.y;
			arrList[cnt-1].add(new Point(x,y));
			
			visit[y][x] = true;
			graph[y][x] = cnt;
			
			for(int d=0; d<4; d++) {
				int newX = x + moveX[d];
				int newY = y + moveY[d];
				
				if(0<=newX && newX<n && 0<=newY && newY<n) {
					if(!visit[newY][newX] && arr[newY][newX]==1) {
						visit[newY][newX] = true;
						queue.add(new Point(newX,newY));
					}
				}
			}
			
		}
	}
}

https://ukyonge.tistory.com/17?category=870877

#위와 같은 방식으로 접근하여 풀 수있는 문제. 개인적으로는 1967번 문제를 먼저 풀고, 1167번 문제를 푸는 것을 추천.

지름을 구하는 법을 알지 못하면 한참동안 헤매는 문제.

유형 : 트리

# 트리에서 탐색은 dfs,bfs가 많이 사용됨.

맨 처음에는 배열로 접근하여 dfs로 문제를 풀었으나, 메모리 초과가 나옴. 대신 인접리스트를 사용하여 문제를 해결하였더니 메모리 제한은 뜨지 않았음. 

트리의 지름을 구하는 방법을 알아야 풀 수 있던 문제, 맨 처음에 dfs를 사용하여 가장 긴 길이를 갖고 있는 정점을 구한 후, 그 정점을 기준으로 다시 dfs를 사용하여 트리의 지름을 얻어야함.

트리의 지름 구하는법

1. 가장 긴 길이를 갖고있는 정점을 구한다.

2. 가장 긴 길이의 정점을 기준으로 다시 거리를 측정한다.

3. 거리를 저장한 배열 중 최대값이 트리의 지름이다.

1) 메모리 초과 났던 코드

2) 정답 코드

유형 : 링크드 리스트

# 처음에는 입력받아서 arrayList를 사용하고 index를 조절하며 switch case 문으로 해결하려 했으나 시간초과로 문제를 풀 수 없었다. 다른 방법을 찾아보던 중 스택으로 해결할 수 있다는 글을 보고 스택으로 수정하여 풀었더니 통과하였다. 시간 제한을 신경써야 함.

시간 초과남, 따라서 선형 리스트인 스택을 사용하여 문제를 접근하였고 해결하였음