공부 기록

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
		PriorityQueue<Job> pq = new PriorityQueue<Job>((j1, j2) -> j1.duration - j2.duration);
		Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
		int answer = 0;
		int time = 0;
		int index = 0;

		while (index < jobs.length || !pq.isEmpty()) {
			while (index < jobs.length && jobs[index][0] <= time) { // 이미 뭔가 실행중...
				pq.add(new Job(jobs[index][0], jobs[index][1]));
				index++;
			}
			if (pq.isEmpty()) {
				time = jobs[index][0];
			} else {
				Job job = pq.poll();
				answer += (time - job.start + job.duration);
				time += job.duration;
			}
		}
		return answer / jobs.length;
	}
}

class Job {
	int start;
	int duration;

	public Job(int start, int duration) {
		this.start = start;
		this.duration = duration;
	}
}

DP 문제로 보고 풀었는데 다른 분들이 실행 시간이 현저히 적어서 비교해 봐야겠음...

import java.util.Scanner;

public class Solution {
	public static int mat[][], dp[][];

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		int row = in.nextInt();
		int col = in.nextInt();
		mat = new int[row][col];
		dp = new int[row][col];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				mat[i][j] = in.nextInt();
				dp[i][j] = -1;
			}
		}

		System.out.println(getRouteNums(row - 1, col - 1, row, col));
	}

	public static int getRouteNums(int row, int col, int maxRow, int maxCol) {
		if (row == 0 && col == 0) {
			return 1;
		}
		if (dp[row][col] != -1) {
			return dp[row][col];
		}

		int left = row - 1 >= 0 && mat[row][col] < mat[row - 1][col] ? getRouteNums(row - 1, col, maxRow, maxCol) : 0;
		int right = row + 1 < maxRow && mat[row][col] < mat[row + 1][col] ? getRouteNums(row + 1, col, maxRow, maxCol): 0;
		int up = col - 1 >= 0 && mat[row][col] < mat[row][col - 1] ? getRouteNums(row, col - 1, maxRow, maxCol) : 0;
		int down = col + 1 < maxCol && mat[row][col] < mat[row][col + 1] ? getRouteNums(row, col + 1, maxRow, maxCol): 0;
		return dp[row][col] = left + right + up + down;
	}
}

1. bufferedReader 대신 Scanner를 쓴 점

2. getRouteNums의 4방향 값을 구할 때, dp에 있는 값이더라도 굳이 재귀함수 호출을 하게 되어 시간이 더 걸린 것 같다.

쉬운 완전 탐색 문제

import java.util.Scanner;

public class Solution {
	public static int max = 0;

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		int testcase = in.nextInt();
		for (int t = 1; t <= testcase; t++) {
			max = 0;
			int n = in.nextInt();
			int limitCalories = in.nextInt();
			int ingredients[][] = new int[n][2];

			for (int i = 0; i < n; i++) {
				ingredients[i][0] = in.nextInt();// 맛
				ingredients[i][1] = in.nextInt();// 칼로리
			}

			for (int i = 0; i < n; i++) {
				findMaxTaste(i, ingredients[i][0], ingredients[i][1], ingredients, limitCalories);
			}

			System.out.println("#" + t + " " + max);
		}
	}

	public static void findMaxTaste(int index, int taste, int calories, int ingredients[][], int limit) {
		if (calories > limit || index == ingredients.length) {
			return;
		}

		max = Math.max(max, taste);

		for (int i = index + 1; i < ingredients.length; i++) {
			if (calories + ingredients[i][1] <= limit) {
				findMaxTaste(i, taste + ingredients[i][0], calories + ingredients[i][1], ingredients, limit);
			}
		}
	}
}

원래 풀이는 for문을 돌며 쿼리에 매칭되는 word의 수를 하나하나 구하도록 했다.

시간 복잡도는 O(쿼리 길이 X 쿼리 갯수 X 워드 갯수)로 효율성 테스트 1, 2, 3 을 통과하지 못했다. 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		String words[] = { "frodo", "front", "frost", "frozen", "frame", "kakao" };
		String queries[] = { "fro??", "????o", "fr???", "fro???", "pro?" };
		Solution solution = new Solution();
		int[] answer = solution.solution(words, queries);
		for (int i = 0; i < answer.length; i++) {
			System.out.println(answer[i]);
		}
	}
}

class Solution {
	public static char WILD_CARD = '?';

	public int[] solution(String[] words, String[] queries) {
		int queryLength = queries.length;
		int[] answer = new int[queryLength];

		for (int i = 0; i < queryLength; i++) {
			answer[i] = matchedQuery(queries[i], words);
		}

		return answer;
	}

	public int matchedQuery(String query, String[] words) {
		int answer = 0;
		for (int i = 0; i < words.length; i++) {
			if (isMatched(query, words[i])) {
				answer++;
			}
		}

		return answer;
	}

	public boolean isMatched(String query, String word) {
		if (query.length() != word.length()) {
			return false;
		}

		for (int i = 0; i < query.length(); i++) {
			if (query.charAt(i) != word.charAt(i)) {
				if (query.charAt(i) != WILD_CARD && word.charAt(i) != WILD_CARD) {
					return false;
				}
			}
		}
		return true;
	}
}

이 문제는 특수한 자료구조를 사용하여 문제를 풀어야 한다.

바로바로~~ trie

[Trie 자료구조]

Trie 자료구조란?

• 텍스트 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조이다.

Trie 자료구조의 형태는?

• 각 노드는 <Key, Value> 맵을 가지고 있다. Key는 하나의 알파벳이 되고, Value는 그 Key에 해당하는 자식 노드가 된다.
• 다음은 DEV, DEAR, PIE, POP, POW라는 단어가 들어있는 Trie 자료구조를 도식화한 것이다. 휴대폰 전화번호부에서 검색을 하거나 사전에서 단어를 찾는 것과 같다.
• 예를 들어, 아래 그림에서 'DEV’라는 문자열을 찾으려면 루트 노드에서부터 순차적으로 [D] -> [E] -> [V] 를 탐색한다.

• 그림에서 볼 수 있듯이 루트 노드는 특정 문자를 의미하지 않고, 자식 노드만 가지고 있다.
• 유의할 점은 '부모 노드’나 '자신이 어떤 알파벳(Key)에 해당하는 노드(Value)'인지를 가지고 있는게 아니라는 점

• 즉, 루트 노드는 [D], [P]라고 하는 알파벳을 Key로 하는 자식 노드들을 가지고 있고, [D]는 [E]를 Key로 하는 자식 노드, [P]는 [I]와 [O]를 Key로 하는 자식 노드들을 가지고 있는 것이다.
• 또 루트 노드를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다는 특징이 있다. 즉, ‘DE’ 노드의 자손인 'DEAR’와 'DEV’는 'DE-'를 공통 접두어로 가지며, 'P’의 자손인 'POW’와 'PIE’는 'P-'를 공통 접두어로 가진다.

Java에는 Trie가 라이브러리로 없기 때문에 직접 구현해줘야 한다.

이때 쿼리가 "??odo", "fro??", "?????" 등의 형태이므로

1. front에서 검색 / back에서 검색할 수 있도록 구현해야 한다.

2. 그리고 단어의 길이에 따라 알맞은 단어를 검색 할 수 있도록 해야 한다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		String words[] = { "frodo", "front", "frost", "frozen", "frame", "kakao" };
		String queries[] = { "fro??", "????o", "fr???", "fro???", "pro?" };
		Solution solution = new Solution();
		int[] answer = solution.solution(words, queries);
		for (int i = 0; i < answer.length; i++) {
			System.out.print(answer[i] + " ");
		}
	}
}

class Solution {

	public int[] solution(String[] words, String[] queries) {

		Trie[] tries = new Trie[100001];
		for (String word : words) {
			int wordLength = word.length();
			if (tries[wordLength] == null) {
				tries[wordLength] = new Trie();
			}

			tries[wordLength].insert(word);
		}

		int[] answer = new int[queries.length];
		for (int i = 0; i < queries.length; i++) {
			int len = queries[i].length();
			if (tries[len] == null) {
				answer[i] = 0;
			} else {
				answer[i] = tries[len].getCount(queries[i]);
			}
		}
		return answer;
	}
}

class Trie {
	public static char WILD_CARD = '?';

	private Node frontRootNode;
	private Node backRootNode;

	Trie() {
		frontRootNode = new Node();
		backRootNode = new Node();
	}

	public void insert(String word) {
		insertFront(word);
		insertBack(word);
	}

	private void insertFront(String word) {
		Node node = frontRootNode;
		for (int i = 0; i < word.length(); i++) {
			node.count++;
			// word.charAt(i) 가 children에 없는 경우 새로운 Node를 만든다.
			node = node.children.computeIfAbsent(word.charAt(i), c -> new Node());
		}
	}

	private void insertBack(String word) {
		Node node = backRootNode;
		for (int i = word.length() - 1; i >= 0; i--) {
			node.count++;
			node = node.children.computeIfAbsent(word.charAt(i), c -> new Node());
		}
	}

	public int getCount(String query) {
		if (query.charAt(0) == WILD_CARD) {
			return getCountFromBack(query);
		}

		return getCountFromFront(query);
	}

	private int getCountFromFront(String query) {
		Node node = frontRootNode;

		for (int i = 0; i < query.length(); i++) {
			if (query.charAt(i) == WILD_CARD) {
				break;
			}
			if (!node.children.containsKey(query.charAt(i))) {
				return 0;
			}
			node = node.children.get(query.charAt(i));
		}
		return node.count;
	}

	private int getCountFromBack(String query) {
		Node node = backRootNode;

		for (int i = query.length() - 1; i >= 0; i--) {
			if (query.charAt(i) == WILD_CARD) {
				break;
			}
			if (!node.children.containsKey(query.charAt(i))) {
				return 0;
			}
			node = node.children.get(query.charAt(i));
		}
		return node.count;
	}

}

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

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

참고

https://woovictory.github.io/2020/04/22/Java-Trie/

https://leveloper.tistory.com/99

"연속된" 파일을 합쳐서 하나의 파일로 만들 때 비용이 최소일 때를 구하는 문제이다.

DP[i][j] = i ~ j번 파일을 합치는 최소 비용이라고 할 때,

DP[i][j] = min(DP[i][k] + DP[k+1][j]) + (A[i] ~ A[j] 까지의 합) 일 것이고 시간 복잡도는 O(N^3)이다.

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner in = new Scanner(System.in);
		int test = in.nextInt();
		for (int t = 0; t < test; t++) {
			int n = in.nextInt();
			int page[] = new int[n + 1];
			int pageSum[] = new int[n + 1];
			for (int i = 1; i <= n; i++) {
				page[i] = in.nextInt();
				pageSum[i] = pageSum[i - 1] + page[i];
			}
			int dp[][] = new int[n + 1][n + 1];
			for (int i = 1; i <= n; i++) {
				Arrays.fill(dp[i], -1);
			}
			System.out.println(DP(dp, pageSum, 1, n));
		}
	}

	public static int DP(int dp[][], int pageSum[], int i, int j) {
		if (i == j) {
			dp[i][j] = 0;
			return dp[i][j];
		}

		if (dp[i][j] != -1) {
			return dp[i][j];
		}

		for (int k = i; k < j; k++) {
			int temp = DP(dp, pageSum, i, k) + DP(dp, pageSum, k + 1, j) + pageSum[j] - pageSum[i - 1];
			if (dp[i][j] == -1 || dp[i][j] > temp) {
				dp[i][j] = temp;
			}
		}
		return dp[i][j];
	}
}

어떤 문자열을 팰린드롬으로 분할하는데, 분할 개수의 최솟값을 구하는 문제이다.

일단 팰린드롬의 연속이 되어야 하고,

정답의 최댓값은 N이 될 것이다. (길이가 1인 문자열은 항상 팰린드롬이니까)

DP[i]: str[i]까지 문자열까지의 팰린드롬 분할 갯수의 최솟값

DP[i] = Math.min(D[j-1]) + 1(단, j ~ i까지는 팰린드롬)

=> 시간복잡도는 DP를 채워야 하는 갯수 N * j를 찾는 시간 N * i~ j가 팰린드롬인지 아닌지 찾을 때 O(1): O(N^2)

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

public class Main {
	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;

		String str = br.readLine();
		char[] arr = str.toCharArray();

		int n = str.length();
		int dp[][] = calcPalindrome(arr, n);
		int ans = calcDividedPalindrome(dp, n);
		bw.write(String.valueOf(ans));
		bw.flush();
		bw.close();
	}

	public static int[][] calcPalindrome(char arr[], int n) {
		int dp[][] = new int[n + 1][n + 1];

		// 길이가 1일 때
		for (int i = 1; i <= n; i++) {
			dp[i][i] = 1;
		}

		// 길이가 2일 때
		for (int i = 1; i <= n - 1; i++) {
			if (arr[i - 1] == arr[i]) {
				dp[i][i + 1] = 1;
			}
		}

		// 길이가 3 이상
		for (int i = 3; i <= n; i++) {
			for (int j = 1; j <= n - i + 1; j++) {
				int k = j + i - 1;
				if (arr[j - 1] == arr[k - 1] && dp[j + 1][k - 1] == 1) {
					dp[j][k] = 1;
				}
			}
		}

		return dp;
	}

	public static int calcDividedPalindrome(int dp[][], int n) {
		int maxDivided[] = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			maxDivided[i] = -1;
			for (int j = 1; j <= i; j++) {
				if (dp[j][i] == 1) {
					if (maxDivided[i] == -1 || maxDivided[i] > maxDivided[j - 1] + 1) {
						maxDivided[i] = maxDivided[j - 1] + 1;
					}
				}
			}
		}

		return maxDivided[n];
	}
}

BufferedWriter is a method that flush the buffer and write the characters directly to the underlying stream.

따라서 int형의 ans를 바로 bw.write하게 되면 char형으로 output이 나온다.

따라서 String형으로 바꿔준 뒤 쓰도록 한다.

어떤 문자열이 팰린드롬인지 확인하는 2가지 방법 --> O(N)

• s == reverse(s) 인지 확인
• 모든 ch[i] == ch[s.length-i] 인지 확인

이 때, 쿼리의 갯수가 M개이므로 총 걸리는 시간은 O(MN)인데 시간 제한에 걸린다.

팰린드롬을 검사하는 다른 방법

1. 길이가 1인 부분 수열은 반드시 팰린드롬 --> O(N)
2. 길이가 2인 부분 수열은 두 수가 같을 때만 팰린드롬 --> O(N)
3. 길이가 3이상인 경우는 DP를 이용한다.-->O(N^2)
   1. DP[i][j]: i ~ j까지 팰린드롬인지 아닌지 저장
   2. ch[i] == ch[j]이면 DP[i][j] = DP[i+1][j-1]이다.

=> O(N^2+M)만에 구할 수 있다.

public class Main {
	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;

		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int dp[][] = new int[n + 1][n + 1];

		dp = calcPalindrome(arr, n);

		int m = Integer.parseInt(br.readLine());
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			bw.write(dp[start][end] + "\n");
		}
		bw.flush();
		bw.close();
	}

	public static int[][] calcPalindrome(int arr[], int n) {
		int dp[][] = new int[n + 1][n + 1];

		// 길이가 1일 때
		for (int i = 1; i <= n; i++) {
			dp[i][i] = 1;
		}

		// 길이가 2일 때
		for (int i = 1; i <= n - 1; i++) {
			if (arr[i] == arr[i + 1]) {
				dp[i][i + 1] = 1;
			}
		}

		// 길이가 3 이상
		for (int i = 3; i <= n; i++) {
			for (int j = 1; j <= n - i + 1; j++) {
				int k = j + i - 1;
				if (arr[j] == arr[k] && dp[j + 1][k - 1] == 1) {
					dp[j][k] = 1;
				}
			}
		}

		return dp;
	}
}

(1, 1) -> (n, n)으로 가는 경로의 개수를 구하는 문제이다.

DP[i][j] = (i, j) 칸에 갈 수 있는 경로의 개수라고 하면 DP[1][1] = 1로 초기화한다.

(i, j)는 오른쪽 또는 아래로 이동하므로 (i+arr[i][j], j) 또는 (i, j+arr[i][j])로 이동한다.

총 시간 복잡도는 N^2 칸 * O(1) 이므로 O(N^2)이다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int arr[][] = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				arr[i][j] = in.nextInt();
			}
		}

		long dp[][] = new long[n + 1][n + 1];
		dp[1][1] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {

				if (arr[i][j] == 0) {
					continue;
				}

				if (i + arr[i][j] <= n) {
					dp[i + arr[i][j]][j] += dp[i][j];
				}
				if (j + arr[i][j] <= n) {
					dp[i][j + arr[i][j]] += dp[i][j];
				}

			}
		}
		System.out.println(dp[n][n]);
	}
}