공부 기록

그룹화 하기 위해 sorted된 string을 key로 해서 map에 넣도록 했다.

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
class Solution {
	public List<List<String>> groupAnagrams(String[] strs) {
		List<List<String>> answer = new ArrayList<>();

		HashMap<String, ArrayList<String>> map = new HashMap<>();
		for (String str : strs) {
			String key = Stream.of(str.split("")).sorted().collect(Collectors.joining());

			if (!map.containsKey(key)) {
				map.put(key, new ArrayList<String>());
			}
			map.get(key).add(str);
		}

		for (String key : map.keySet()) {
			answer.add(map.get(key));
		}

		return answer;
	}
}

single string을 정렬하는 방법으로는 스트림으로 정렬하는 방법도 있고,

char로 바꾼 다음에 Arrays.sort를 쓴 후 다시 스트링으로 합치는 방법이 있는데 테스트 해 보니 후자가 더 빠르다는 것을 알게 되었다.

import java.util.*;
class Solution {
	public List<List<String>> groupAnagrams(String[] strs) {
		List<List<String>> answer = new ArrayList<>();
		HashMap<String, ArrayList<String>> map = new HashMap<>();

		for (String str : strs) {
			char[] keys = str.toCharArray();
			Arrays.sort(keys);
			String key = new String(keys);

			if (!map.containsKey(key))
				map.put(key, new ArrayList<>());
			map.get(key).add(str);
		}

		for (String key : map.keySet()) {
			answer.add(map.get(key));
		}

		return answer;
	}
}

문제 조건

• k[encoded_string] => encoded_string을 k번 반복
• 3a 또는 2[4] 등의 경우는 없다고 생각한다

먼저, 괄호 중 ']' 을 만나는 순간, 뒤에서부터 가장 먼저 만나게 되는 '[' 의 위치를 찾아 그 부분을 반복하는 문제이다.

=> 뒤에서 부터 꺼내는 것이니까 스택을 사용하자

예를 들어 예시2와 같이 `3[a2[c]]` 가 주어졌다고 해 보자

아래와 같이 일단 닫는 괄호를 만나기 전까지는 스택에 push를 한다.

그 다음 여는 괄호를 만나기 전까지 pop을 하며 stringbuilder에 더해주고,

여는 괄호까지 pop한 뒤에 top이 숫자가 될 수 있는지 확인한다. 숫자이면 pop해주고, stringbuilder를 그 숫자만큼 반복해준다.

결과를 스택에 다시 넣어주고 위 규칙을 반복한다.

한가지 더 문제를 풀면서 주의할 점은 예시 4번과 같이 `abc3[cd]xyz`로 들어오게 되면 숫자와 문자의 분리가 필요하고,

스택에는 문자열로 집어넣기 때문에 문자열을 숫자로 바꿀 수 있는지 확인이 필요하다. 이는 아래와 같은 방법으로 해결했다.

class Solution {
	public String decodeString(String s) {
		Pattern p = Pattern.compile("(\\D)+|(\\d)+"); // 숫자와 숫자가 아닌것에 대한 분리
		Matcher m = p.matcher(s);
		
		while(m.find()) {
			System.out.println(m.group());
		}
	}

	private int isNumber(String str) { // 숫자인지 확인
		try {
			int n = Integer.parseInt(str);
			return n; // 맞다면 정수 리턴
		} catch (Exception e) {
			return -1; // 아니라면 -1 리턴
		}
	}
}

이를 코드로 옮겨보면 아래와 같다.

import java.util.*;
import java.util.regex.*;

class Solution {
	public String decodeString(String s) {
		Stack<String> stack = new Stack<String>();
		Queue<String> queue = new LinkedList<String>();

		Pattern p = Pattern.compile("(\\D)+|(\\d)+");
		Matcher m = p.matcher(s);

		while (m.find()) {
			StringTokenizer st = new StringTokenizer(m.group(), "[]", true);
			while (st.hasMoreElements()) {
				queue.add(st.nextToken());
			}
		}
		
		StringBuilder sb = new StringBuilder("");
		while (!queue.isEmpty()) {
			String str = queue.poll();

			if (str.equals("]")) {
				while (true) {
					String buffer = stack.pop();

					if (buffer.equals("[")) {
						break;
					}
					sb.insert(0, buffer);
				}

				if (!stack.isEmpty()) {
					int k = isNumber(stack.peek());
					if (k != -1) {
						stack.pop();
						for (int i = 0; i < k; i++) {
							stack.add(sb.toString());
						}
					}
				}
				
				sb.setLength(0);
			} else {
				stack.add(str);
			}
		}
		
		while(!stack.isEmpty()) {
			sb.insert(0, stack.pop());
		}
		return sb.toString();
	}

	private int isNumber(String str) {
		try {
			int n = Integer.parseInt(str);
			return n;
		} catch (Exception e) {
			return -1;
		}
	}
}

문제 조건

• cpu에 태스크가 들어올건데 태스크의 순서는 맘대로 실행할 수 있다.
• 각 태스크는 한 시간 단위로 수행되고, 태스크를 실행하거나 idle 상태에 있을 수 있다.
• 두 개의 동일한 태스크를 실행하기 위한 사이에는 최소 n개의 태스크/idle이 있어야 한다.

흠... 일단은 그냥 가장 자주 나오는 글자를 배치하고 그 사이에 n개의 빈 칸을 둔 뒤에 다른 애들을 적절히 배치하면 될 것 같다고 생각했다.

class Solution {
	public int leastInterval(char[] tasks, int n) {
		int[] frequency = new int[26];
		for (int task : tasks) {
			frequency[task - 'A']++;
		}

		Arrays.sort(frequency);

		int maxFrequency = frequency[25];
		int betweenTime = (maxFrequency - 1) * n;

		int index = frequency.length - 2;
		while (index >= 0 && betweenTime > 0) {
			betweenTime -= Math.min(maxFrequency - 1, frequency[index]);
			index--;
		}
		betweenTime = Math.max(0, betweenTime);

		return betweenTime + tasks.length;
	}
}

처음에는 단순하게 maxHeap을 이용해서 O(N)만에 풀면 되지 않을까 생각했다.

윈도우를 maxHeap에 넣고 움직이면서 맨 앞의 값은 빼고, 뒤에 새로 들어오는 값은 더해주는 방식으로 구현했다.

import java.util.*;
class Solution {
	public int[] maxSlidingWindow(int[] nums, int k) {
		int length = nums.length;
		int answer[] = new int[length - k + 1];

		PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
		for (int i = 0; i < k; i++) {
			maxHeap.add(nums[i]);
		}
		answer[0] = maxHeap.peek();

		for (int i = 1; i < length - k + 1; i++) {
			Integer remove = nums[i - 1];
			int add = nums[i + k - 1];
			maxHeap.remove(remove);
			maxHeap.add(add);

			answer[i] = maxHeap.peek();
		}

		return answer;
	}
}

결과는 Hard 문제 답게 TLE가 떴다...ㅠ

다시 문제 조건을 자세히 살펴봤다. 문제 조건은 아래와 같다.

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

내가 구현한 코드가 O(N)이 맞다면 nums.length<=10^5이기 때문에 시간내에 동작해야 했다.

다시 생각 해 보니 maxHeap에 넣고 빼는 동작이 logk씩 일어나기 때문에 O(NlogK)로 시간초과가 날 수 있다는 점을 생각하지 못했다.

뭔가 윈도우를 하나씩 옮기는 방법은 맞는 것 같으니, 최댓값을 구할 때 O(logK)보다 줄일 수 있는지 생각해 봤다.

일단은 문자열을 넣고 뺄때 힙구조가 아닌 Deque를 사용하는게 좋을 것 같았다. Deque는 맨앞과 맨뒤의 요소를 넣고 뺄 때 O(1)이 걸린다.

문제 풀이 방법은 아래와 같다.

1. 위의 경우와 마찬가지로 첫 k개는 Deque에 넣고 최댓값을 구한다.

2. 윈도우를 움직인다. 이 때,

• deque에는 index를 넣어두고, 현재 윈도우 안의 요소가 될 수 있는 인덱스들만 넣어 둔다.
• 새로 집어 넣는 값에 비해 작은 값들을 앞에서 부터 다 뺀다. 왜냐면 윈도우는 오른쪽으로 움직이고 있고, 현재 넣는 값보다 작은 기존의 deque에 있는 값은 영원히 최대값이 될 수 없기 때문이다.

아래는 구현한 코드이다.

import java.util.*;
class Solution {
	public void moveWindow(int i, int k, ArrayDeque<Integer> deque, int[] nums) {
		if (!deque.isEmpty() && deque.getFirst() == i - k) {
			deque.removeFirst();
		}

		while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]) {
			deque.removeLast();
		}
	}

	public int[] maxSlidingWindow(int[] nums, int k) {
		ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
		int length = nums.length;
		if (length * k == 0) {
			return new int[0];
		}
		if (k == 1) {
			return nums;
		}

		int maxIndex = 0;
		for (int i = 0; i < k; i++) {
			moveWindow(i, k, deque, nums);
			deque.addLast(i);

			if (nums[i] > nums[maxIndex]) {
				maxIndex = i;
			}
		}

		int[] answer = new int[length - k + 1];
		answer[0] = nums[maxIndex];

		for (int i = k; i < length; i++) {
			moveWindow(i, k, deque, nums);
			deque.addLast(i);
			answer[i - k + 1] = nums[deque.getFirst()];
		}
		return answer;
	}
}

2021/01/15 - [알고리즘 공부/boj] - boj 3745: 오름세

위 문제와 동일하다. 지난번에 푼 기억이 있어서 비교적 수월하게 풀었다.

세그먼트 트리로도 한번 구현해 봐야하는데 언제하지...

class Solution {
	public int lengthOfLIS(int[] nums) {
		int n = nums.length;
		int[] lis = new int[n];

		lis[0] = nums[0];
		int lastIndex = 0;

		for (int i = 1; i < n; i++) {
			if (lis[lastIndex] < nums[i]) {
				lastIndex++;
				lis[lastIndex] = nums[i];
			} else {
				int index = findIndex(lis, nums[i], lastIndex);
				lis[index] = nums[i];
			}
		}
		return lastIndex + 1;
	}

	public static int findIndex(int[] lis, int target, int right) {
		int left = 0;

		while (left < right) {
			int mid = (left + right) / 2;
			if (lis[mid] == target) {
				return mid;
			}

			if (lis[mid] > target) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}

		return right;
	}
}

문제 조건

• num 배열 원소는 음이 아닌 정수
• 배열의 마지막 요소까지 점프해서 무조건 도달 가능 => 0이 아닌 이상 1칸씩 가면 되니까
• 배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타낸다.

class Solution {
	public int jump(int[] nums) {
		int n = nums.length;
		if (n < 2) {
			return 0;
		}

		int maxPosition = nums[0];
		int maxLength = nums[0];

		int jumps = 1;
		for (int i = 1; i < n; ++i) {
			if (maxLength < i) {
				jumps++;
				maxLength = maxPosition;
			}
			maxPosition = Math.max(maxPosition, nums[i] + i);
		}

		return jumps;
	}
}

먼저, 브루트포스로 모든 점에 대해 DFS를 돌려 가장 긴 path를 찾는 방법이 있을 것이다. 하지만 이 방법의 경우 시간초과가 발생한다.

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

	public int longestIncreasingPath(int[][] matrix) {
		if (matrix.length == 0) {
			return 0;
		}

		int maxRow = matrix.length;
		int maxCol = matrix[0].length;

		int answer = 0;
		for (int i = 0; i < maxRow; ++i)
			for (int j = 0; j < maxCol; ++j)
				answer = Math.max(answer, dfs(matrix, i, j, maxRow, maxCol));
		return answer;
	}

	private int dfs(int[][] matrix, int row, int col, int maxRow, int maxCol) {
		int ans = 0;
		for (int i = 0; i < 4; i++) {
			int r = row + dr[i];
			int c = col + dc[i];
			if (isBoundary(r, c, maxRow, maxCol) && matrix[r][c] > matrix[row][col]) {
				ans = Math.max(ans, dfs(matrix, r, c, maxRow, maxCol));
			}
		}
		return ++ans;
	}

	public boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= maxRow || col >= maxCol) {
			return false;
		}
		return true;
	}
}

위 코드에서 시간을 줄일 수 있는 부분은 어디일까? 위 코드에서 중복되는 부분은 dfs로 계산하여 max를 업데이트 하는 부분이다.

이 부분을 줄이기 위해 모든 점에 대해 가장 긴 path를 찾는 도중에 이미 갔던 길의 경우는 저장해 두고,

다시 방문할 때 저장했던 길이를 바로 리턴해주면 더 효율적일 것이다. => 메모이제이션

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

	public int longestIncreasingPath(int[][] matrix) {
		if (matrix.length == 0) {
			return 0;
		}

		int maxRow = matrix.length;
		int maxCol = matrix[0].length;

		int[][] memo = new int[maxRow][maxCol];

		int answer = 0;
		for (int i = 0; i < matrix.length; ++i) {
			for (int j = 0; j < matrix[i].length; ++j) {
				answer = Math.max(answer, dfs(matrix, memo, i, j, maxRow, maxCol));
			}
		}
		return answer;
	}

	public int dfs(int[][] matrix, int[][] memo, int row, int col, int maxRow, int maxCol) {
		if (memo[row][col] != 0) {
			return memo[row][col];
		}

		for (int i = 0; i < 4; i++) {
			int r = row + dr[i];
			int c = col + dc[i];
			if (isBoundary(r, c, maxRow, maxCol) && matrix[r][c] > matrix[row][col]) {
				memo[row][col] = Math.max(memo[row][col], dfs(matrix, memo, r, c, maxRow, maxCol));
			}
		}

		memo[row][col]++;
		return memo[row][col];
	}

	public boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= maxRow || col >= maxCol) {
			return false;
		}
		return true;
	}
}

nums 배열에 있는 값을 적절히 더하고 빼서 target과 같은 값을 만들 수 있는 방법의 수를 구하는 문제이다.

일단 문제를 풀 수 있는 방법으로 가장 먼저 떠오른 것은 브루트 포스,,, 시간복잡도는 O(2^N)이다.

class Solution {
	public int answer = 0;

	public int findTargetSumWays(int[] nums, int S) {
		findAll(nums, 0, 0, S);
		return answer;
	}

	public void findAll(int[] nums, int index, int sum, int target) {
		if (index >= nums.length) {
			if (sum == target) {
				answer++;
			}
			return;
		}

		findAll(nums, index + 1, sum - nums[index], target);
		findAll(nums, index + 1, sum + nums[index], target);
	}
}

이 방법 외에 다른 방법이 있지 않을까 생각해 봤다.

• The length of the given array is positive and will not exceed 20.
• The sum of elements in the given array will not exceed 1000.
• Your output answer is guaranteed to be fitted in a 32-bit integer.

문제 조건을 다시 보면 num의 합은 1000을 넘지 않는다고 했다.

합이 있으면 차도 가능하니 num을 적절히 더하고 빼면 그 범위는 -1000~1000일것이다.

이를 dp를 이용해서 구하도록 하는데, 음수 인덱스는 불가능 하니

dp[i][sum+1000]: num의 i번째 요소까지 더하고 뺐을 때, sum을 만들 수 있는 가짓수로 정의하도록 한다. 이 경우 시간복잡도는 O(N)이다.

import java.util.*;
class Solution {
	public int findTargetSumWays(int[] nums, int S) {
		int[][] memo = new int[nums.length][2001];
		for (int[] row : memo) {
			Arrays.fill(row, Integer.MIN_VALUE);
		}
		return calculate(nums, 0, 0, S, memo);
	}

	public int calculate(int[] nums, int i, int sum, int S, int[][] memo) {
		if (i == nums.length) {
			if (sum == S) {
				return 1;
			}
			return 0;
		}

		if (memo[i][sum + 1000] != Integer.MIN_VALUE) {
			return memo[i][sum + 1000];
		}

		int add = calculate(nums, i + 1, sum + nums[i], S, memo);
		int subtract = calculate(nums, i + 1, sum - nums[i], S, memo);
		memo[i][sum + 1000] = add + subtract;
		return memo[i][sum + 1000];
	}
}