공부 기록

풀이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();
				}
			}
		}
	}
}

최소 거리를 구하는 방법보다는 최소 거리를 찍어놓고 그 거리가 가능한지 여부를 확인한다.

풀이 로직은 아래와 같다.

1. 이분탐색으로 가능한 거리 mid를 찍는다.

2. 없앨 돌의 수(remove)를 계산한다 - 돌 사이의 거리가 mid보다 짧으면 없애서 돌 사이의 거리를 늘린다.

3. 없앨 돌의 수가 n보다 큰 경우 돌 사이가 더 가깝다는 의미이므로 왼쪽탐색, n보다 작거나 같은 경우는 오른쪽을 탐색하면서 업데이트

import java.util.*;
import java.util.stream.Collectors;
class Solution {
	public int solution(int distance, int[] rocks, int n) {
		List<Integer> rock = Arrays.stream(rocks).boxed().collect(Collectors.toList());
		rock.add(0);
		rock.add(distance);
		Collections.sort(rock);

		int right = distance;
		int left = 0;
		int mid = 0;
		int answer = 0;

		while (left <= right) {
			mid = (right + left) / 2;
			int remove = 0;

			int i = 0;
			int j = 1;
			while (i < rock.size() && j < rock.size()) {
				if (rock.get(j) - rock.get(i) < mid) {
					remove++;
					j++;
				} else {
					i = j;
					j++;
				}
				if (remove > n) {
					break;
				}
			}

			if (remove <= n) {
				left = mid + 1;
				answer = Math.max(answer, mid);
			} else {
				right = mid - 1;
			}

		}

		return answer;
	}
}

1 ≤ n, m ≤ 1,000 이므로 브루트포스로 다 구해본다면 O(N^2M^2)로 시간 제한에 걸릴 것이다.

array를 무조건 한 번은 봐야하기 때문에 O(NM) * ???가 2초 안에 실행 되어야 한다.

DP로 풀어볼 수 있는 방법을 생각해 보자

dp[i][j]: (i,j)를 오른쪽 아래로 포함한 가장 크게 만들 수 있는 정사각형의 한 변 길이로 잡고, mat[i][j]==1일때 dp를 업데이트 한다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int row = in.nextInt();
		int col = in.nextInt();
		int mat[][] = new int[row][col];
		int dp[][] = new int[row][col];
		int maxLength = 0;

		for (int i = 0; i < row; i++) {
			String rowInput = in.next();
			int j = 0;
			for (char ch : rowInput.toCharArray()) {
				mat[i][j] = ch - '0';
				dp[i][j] = ch - '0';
				maxLength = ch - '0' > 0 ? 1 : 0;
				j++;
			}
		}

		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				if (mat[i][j] != 0) {
					dp[i][j] = findMinValueBetweenThree(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
					maxLength = Math.max(maxLength, dp[i][j]);
				}
			}
		}
		System.out.println(maxLength * maxLength);
	}

	public static int findMinValueBetweenThree(int a, int b, int c) {
		return Math.min(a, Math.min(b, c));
	}
}