공부 기록

시간초과를 해결하기 위해 사용

• BufferdReader
• StringBuilder

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

public class Main {
	public static void main(String[] args) throws Exception {
		PriorityQueue<Integer> maxQueue = new PriorityQueue<>();
		PriorityQueue<Integer> minQueue = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));

		StringBuilder sb = new StringBuilder("");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(br.readLine());
			maxQueue.add(num);
			if ((maxQueue.size() + minQueue.size()) % 2 != 0) {
				minQueue.add(maxQueue.poll());
			} else {
				if (minQueue.peek() > num) {
					maxQueue.add(minQueue.poll());
					minQueue.add(maxQueue.poll());
				}
			}
			sb.append(minQueue.peek() + "\n");
		}

		System.out.println(sb);
	}
}

import java.util.*;

public class Main {
	public static final int[] dr = { -1, 0, 0, 1 };
	public static final int[] dc = { 0, -1, 1, 0 };

	public static final int SPACE = 0;
	public static final int HOME = 1;
	public static final int CHICKEN = 2;

	public static int min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = in.nextInt();
		int chickenNum = in.nextInt();

		int mat[][] = new int[size][size];
		ArrayList<Point> chickens = new ArrayList<Point>();
		ArrayList<Point> homes = new ArrayList<Point>();

		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				int position = in.nextInt();

				if (position == CHICKEN) {
					chickens.add(new Point(i, j));
				} else if (position == HOME) {
					homes.add(new Point(i, j));
				}
			}
		}

		for (int i = 0; i < chickens.size(); i++) {
			boolean check[] = new boolean[chickens.size()];
			check[i] = true;
			findAll(mat, homes, chickens, i, 1, chickenNum, check);
		}

		System.out.println(min);
	}

	public static void findAll(int mat[][], ArrayList<Point> homes, ArrayList<Point> chickens, int index, int num,
			int chickenNum, boolean[] check) {
		if (num == chickenNum) {
			min = Math.min(min, calcChickenDistance(mat, homes, chickens, check));
			return;
		}
		if (index == chickens.size()) {
			return;
		}

		for (int i = index + 1; i < chickens.size(); i++) {
			check[i] = true;
			findAll(mat, homes, chickens, i, num + 1, chickenNum, check);
			check[i] = false;
		}
	}

	public static int calcChickenDistance(int mat[][], ArrayList<Point> homes, ArrayList<Point> chickens,
			boolean[] check) {
		int distanceSum = 0;
		for (Point home : homes) {
			int distance = Integer.MAX_VALUE;
			for (int i = 0; i < check.length; i++) {
				if (check[i]) {
					Point chicken = chickens.get(i);
					distance = Math.min(distance, Math.abs(home.row - chicken.row) + Math.abs(home.col - chicken.col));
				}
			}
			distanceSum += distance;
		}

		return distanceSum;
	}
}

class Point {
	int row;
	int col;

	public Point(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

풀이1) Trie 자료구조

1. Trie 자료구조 구현

    - Node 필드 정의: character, 해당 prefix를 가지는 단어의 수

2. Node를 따라가면서 해당 단어의 count = 1일때 멈춘다.

로직을 대충 생각해보니까 굳이 Trie 자료구조가 필요없을 것 같으나...

그래도 한번 구현해 보는 것이 좋을 것 같아서 아래와 같이 짜봤다.

import java.util.*;
class Solution {
	public int solution(String[] words) {
		Trie trie = new Trie();
		for (String word : words) {
			trie.insert(word);
		}

		int answer = 0;
		for (String word : words) {
			answer += trie.searchWordFromFront(word);
		}

		return answer;
	}
}

class Trie {
	private Node rootNode;

	Trie() {
		rootNode = new Node();
	}

	public void insert(String word) {
		Node node = rootNode;
		for (int i = 0; i < word.length(); i++) {
			node = node.children.computeIfAbsent(word.charAt(i), c -> new Node());
			node.count++;
		}
	}

	public int searchWordFromFront(String word) {
		Node node = rootNode;
		int move = 0;
		for (int i = 0; i < word.length(); i++) {
			node = node.children.get(word.charAt(i));
			move++;

			if (node.count == 1) {
				break;
			}
		}

		return node.count == 1 ? move : word.length();
	}
}

class Node {
	Map<Character, Node> children;
	int count;

	Node() {
		this.children = new HashMap<>();
		this.count = 0;
	}
}

풀이2) 정렬 후 인접하는 두 단어 비교

만약 두 단어 before, word가 0 이상 길이의 동일한 prefix를 가진다고 하면, before을 찾기 위해서는

1. before과 word가 같은 서브트리에 존재

   - before.length > prefix.length : prefix+1개 입력

   - before.length == prefix.length : prefix개 입력

2. before과 word가 다른 서브트리에 존재

   - prefix+1개 입력

class Solution {
	public int solution(String[] words) {
		Arrays.sort(words);
		String before = "";
		int beforePressCount = 1;
		int beforeSameCount = 0;
		int answer = 0;

		for (String cur : words) {
			int sameCount = 0;
			boolean isSimilar = false;

			// 이전 단어와 동일한 prefix 길이 구하기
			for (int i = 0; i < before.length(); i++) {
				if (before.charAt(i) == cur.charAt(i)) {
					sameCount++;
					isSimilar = true;
				} else {
					break;
				}
			}

			if (isSimilar && sameCount >= beforeSameCount) {

				// before 단어에 대한 입력 수 업데이트
				answer -= beforePressCount;
				if (before.length() > sameCount) {
					answer += (sameCount + 1);
				} else if (before.length() == sameCount) {
					answer += sameCount;
				}

				// word 단어에 대한 입력 수 업데이트
				beforePressCount = sameCount + 1;
				answer += beforePressCount;
			} else {
				beforePressCount = sameCount + 1;
				answer += beforePressCount;
			}

			before = cur;
			beforeSameCount = sameCount;
		}

		return answer;
	}
}

브루트포스 방법으로 양 옆을 다 보는 방법의 경우 시간복잡도 O(N^2)이 걸릴 것이다.

이 문제의 경우 아래와 같이 왼쪽에  있는 높이 중에서 가장 높은 높이만 보고 있는 상태이므로

=> 스택을 사용한다면 O(N)만에 문제를 풀 수 있다.

문제풀이 로직은 아래와 같다.

1. index를 오른쪽으로 움직이면서 스택의 맨 위에 담은 높이와 비교했을때 height[index]이 크거나 같으면 스택에 담는다.

2. 높이가 바뀌면 이전까지 물을 계산해서 answer에 더해주며, 이전 높이는 pop 시켜준다.

import java.util.*;
class Solution {
	public int trap(int[] height) {
		int answer = 0;

		Stack<Integer> stack = new Stack<Integer>();
		int index = 0;
		while (index < height.length) {
			while (!stack.isEmpty() && height[index] >= height[stack.peek()]) {
				int top = stack.pop();

				if (stack.isEmpty()) {
					break;
				}
				int distance = index - stack.peek() - 1;
				int bounded_height = Math.min(height[index], height[stack.peek()]) - height[top];
				answer += distance * bounded_height;
			}
			stack.push(index++);
		}

		return answer;
	}
}

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int testcase = in.nextInt();
		for (int t = 1; t <= testcase; t++) {
			int limit = in.nextInt();
			int relationNum = in.nextInt();

			List<List<Integer>> relations = new ArrayList<List<Integer>>();
			for (int i = 0; i <= limit; i++) {
				relations.add(new ArrayList<Integer>());
			}
			for (int i = 0; i < relationNum; i++) {
				int start = in.nextInt();
				int end = in.nextInt();
				relations.get(start).add(end);
				relations.get(end).add(start);
			}

			HashSet<Integer> invited = isBestFriend(new HashSet<Integer>(), relations, true);
			invited.remove(1);
			System.out.println("#" + t + " " + invited.size());
		}
	}

	public static HashSet<Integer> isBestFriend(HashSet<Integer> invited, List<List<Integer>> relations, boolean isFirst) {
		if (!isFirst) {
			HashSet<Integer> newHashSet = new HashSet<Integer>(invited);
			Iterator<Integer> it = invited.iterator();
			while (it.hasNext()) {
				newHashSet.addAll(relations.get(it.next()));
			}

			return newHashSet;
		}

		invited.addAll(relations.get(1));
		return isBestFriend(invited, relations, false);
	}
}

+ 주의할 점

JAVA concurrent memory error

class Solution {
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int nums1Length = nums1.length;
		int nums2Length = nums2.length;

		int size = nums1Length + nums2Length;

		int nums1Index = 0;
		int nums2Index = 0;
		int mergedArray[] = new int[size];
		int index = 0;
		while (true) {

			if (nums1Index >= nums1Length && nums2Index >= nums2Length) {
				break;
			} else if (nums1Index >= nums1Length) {
				mergedArray[index++] = nums2[nums2Index++];
			} else if (nums2Index >= nums2Length) {
				mergedArray[index++] = nums1[nums1Index++];
			} else if (nums1[nums1Index] > nums2[nums2Index]) {
				mergedArray[index++] = nums2[nums2Index++];
			} else {
				mergedArray[index++] = nums1[nums1Index++];
			}
		}

		if (size % 2 == 0) {
			return (mergedArray[size / 2] + mergedArray[size / 2 - 1]) / (double) 2;
		}
		return mergedArray[size / 2];
	}
}

N=nums1.length, M=nums2.length라고 두면

위 방법대로 푼다면 시간복잡도는 O(N+M)이 나오고,

mergedArray라는 새 자료구조로 nums1, nums2를 옮겨야 하기 때문에 추가적인 공간 복잡도는 O(N+M)가 된다.

문제에서는 제시되지 않았으나, nums1, nums2가 정렬되어있다고 치고 이분탐색으로 문제를 푼다면 O(log(N+M)) 풀이도 가능하다.

class Solution {
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		if (nums2.length < nums1.length) { // 짧은 길이를 nums1로 둔다.
			return findMedianSortedArrays(nums2, nums1);
		}

		int start = 0;
		int end = nums1.length;
		int size = nums1.length + nums2.length;

		while (start < end) {
			int p1 = (start + end) / 2;
			int p2 = (size + 1) / 2 - p1;

			if (p1 == 0 || nums1[p1 - 1] <= nums2[p2]) {
				if (p2 == 0 || nums2[p2 - 1] <= nums1[p1]) {
					break;
				} else {
					start = p1 + 1;
				}
			} else {
				end = p1 - 1;
			}
		}

		int p1 = (start + end) / 2;
		int p2 = (size + 1) / 2 - p1;
		int m = Integer.MIN_VALUE;
		int n = Integer.MAX_VALUE;
		if (size % 2 == 1) {
			return Math.max(p1 - 1 >= 0 ? nums1[p1 - 1] : m, p2 - 1 >= 0 ? nums2[p2 - 1] : m);
		} else {
			return (Math.max(p1 - 1 >= 0 ? nums1[p1 - 1] : m, p2 - 1 >= 0 ? nums2[p2 - 1] : m)
					+ Math.min(p1 < nums1.length ? nums1[p1] : n, p2 < nums2.length ? nums2[p2] : n)) / 2.0;
		}
	}
}

마지막으로 아래는 O(min(N,M)) 풀이이다. 이 풀이는 이해하기 어렵지만 일단 추가해둔다... 시간날때 읽어봐야지...

leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation

class Solution {
	public List<String> letterCombinations(String digits) {
		List<String> answer = new ArrayList<String>();

		Map<Integer, String> numberToString = new HashMap<Integer, String>() {
			{
				put(2, "abc");
				put(3, "def");
				put(4, "ghi");
				put(5, "jkl");
				put(6, "mno");
				put(7, "pqrs");
				put(8, "tuv");
				put(9, "wxyz");
			}
		};

		for (char ch : digits.toCharArray()) {
			int number = ch - '0';
			answer = addCharacter(numberToString.get(number), answer);
		}

		return answer;
	}

	public List<String> addCharacter(String str, List<String> answer) {
		List<String> nextAnswer = new ArrayList<String>();

		if (answer.isEmpty()) {
			return str.chars().mapToObj(ch -> Character.toString(ch)).collect(Collectors.toList());
		}

		for (int i = 0; i < str.length(); i++) {
			String lastString = str.substring(i, i + 1);

			for (String substring : answer) {
				nextAnswer.add(substring + lastString);
			}
		}

		return nextAnswer;
	}
}

어차피 모든 경우의 수를 구하긴 해야한다.

하지만, 팰린드롬임을 한번 체크했다면 계속 그 글자가 팰린드롬인지 체크를 하지 않도록 어딘가 저장하는 방법은 없을지? => DP

팰린드롬 s의 서브스트링 s.substring(1, n-1) 또한 팰린드롬임을 이용하자.

=> DP[indexStart][indexEnd]: s.substring(indexStart, indexEnd)의 팰린드롬 여부

맨 첫 글자와 끝 글자가 같은 경우 중에서 팰린드롬이 될 수 있는 경우

1. 맨첫글자 위치 == 끝글자 위치 ex) "a"

2. 두 글자가 연속인 경우 ex) "aa"

3. 중간에 한 글자가 껴있는 경우 ex) "aba"

4. s.substring(첫 글자의 다음 글자, 끝 글자의 이전 글자)가 팰린드롬인 경우

import java.util.*;
class Solution {
	public List<List<String>> partition(String s) {
		List<List<String>> answer = new ArrayList<List<String>>();

		int length = s.length();
		boolean[][] dp = new boolean[length][length];

		palindrome(s, 0, answer, new Stack<String>(), dp);

		return answer;
	}

	public void palindrome(String s, int indexStart, List<List<String>> answer, Stack<String> currentList, boolean[][] dp) {
		if (indexStart >= s.length()) {
			answer.add(new ArrayList<>(currentList));
			return;
		}

		for (int end = indexStart; end < s.length(); end++) {
			if (s.charAt(indexStart) == s.charAt(end)) {
				if (end - 1 <= indexStart + 1 || dp[indexStart + 1][end - 1]) {
					dp[indexStart][end] = true;
					currentList.add(s.substring(indexStart, end + 1));
					palindrome(s, end + 1, answer, currentList, dp);
					currentList.pop();
				}
			}
		}
	}
}