방을 방문하기 위한 순서가 있다. 2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다. 2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다. 2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다. 2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다. => 사이클이 없다
문제 조건을 읽으니 가장 먼저 위상 정렬을 이용해서 풀어야겠다는 생각이 들었다.
풀이 로직은 아래와 같다.
1. path를 이용하여 양방향 그래프를 생성한다.
2. 양방향 그래프를 bfs를 이용하여 방향 그래프로 바꾸어 준다.
3. 그래프에 order을 적용하여 위상 정렬 알고리즘을 돌린다.
class Solution {
public static boolean solution(int n, int[][] path, int[][] order) {
List<Integer>[] childs = new ArrayList[n];
for (int i = 0; i < n; i++) {
childs[i] = new ArrayList<>();
}
for (int i = 0; i < path.length; i++) {
childs[path[i][0]].add(path[i][1]);
childs[path[i][1]].add(path[i][0]);
}
return isPossible(createGraph(childs), order);
}
public static List<Integer>[] createGraph(List<Integer>[] graph) {
Queue<Integer> q = new LinkedList<>();
List<Integer>[] directedGraph = new ArrayList[graph.length];
for (int i = 0; i < directedGraph.length; i++)
directedGraph[i] = new ArrayList<>();
boolean[] v = new boolean[directedGraph.length];
q.offer(0);
v[0] = true;
while (!q.isEmpty()) {
int cur = q.poll();
for (int i = 0; i < graph[cur].size(); i++) {
int next = graph[cur].get(i);
if (v[next])
continue;
directedGraph[cur].add(next);
v[next] = true;
q.offer(next);
}
}
return directedGraph;
}
public static boolean isPossible(List<Integer>[] childs, int[][] order) {
Queue<Integer> queue = new LinkedList<>();
int[] parentNum = new int[childs.length];
for (int i = 0; i < childs.length; i++) {
for (Integer next : childs[i]) {
parentNum[next]++;
}
}
for (int i = 0; i < order.length; i++) {
childs[order[i][0]].add(order[i][1]);
parentNum[order[i][1]]++;
}
for (int i = 0; i < childs.length; i++) {
if (parentNum[i] == 0) {
queue.add(i);
}
}
int cnt = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
cnt++;
for (int i = 0; i < childs[cur].size(); i++) {
int next = childs[cur].get(i);
parentNum[next]--;
if (parentNum[next] == 0) {
queue.add(next);
}
}
}
return cnt == childs.length ? true : false;
}
}
출발지점부터 distance 사이에 바위를 제거했을 때, 제거한 바위의 최솟값 중에 가장 큰 값을 구하는 문제이다.
이 문제는 바위를 제거하는 모든 경우를 구한 후 최솟값을 구한다면,
바위가 N개, R개를 제거할 수 있다면 O(NCR)로 시간초과가 발생하게 된다.
이러한 경우에는 바위를 제거하는 모든 경우의 수를 구하기보다는,
바위간의 최소 거리를 정해두고 이 조건이 가능한지 여부를 보는 쪽으로 생각하면 된다.
바위간의 최소 거리를 정할 때에는 이분 탐색을 사용하도록 했다. 풀이 방식은 아래와 같다.
1. 이분 탐색으로 최대 사잇값 diff를 정한다.
2. 돌을 n개 지웠을 때 최소 거리가 diff인지 확인한다.
=> 즉, 돌 사이의 거리가 diff보다 작으면 돌을 없애고,
최종적으로 없애야 하는 돌의 수가 n보다 크면 diff를 너무 크게 잡은 것이므로 왼쪽을 탐색하도록 한다.
class Solution {
public int solution(int distance, int[] rocks, int n) {
int length = rocks.length;
int start = 0;
int end = distance;
int answer = 0;
Arrays.sort(rocks);
while (start <= end) {
int mid = (start + end) / 2;
if (!isPossible(rocks, n, length, mid, distance)) {
// diff가 너무 크니까 줄이자
end = mid - 1;
} else { // 가능하니까 일단 answer에 저장하고 더 늘려보자
answer = Math.max(answer, mid);
start = mid + 1;
}
}
return answer;
}
public boolean isPossible(int[] rocks, int n, int length, int diff, int distance) {
int remove = 0;
int before = 0;
for (int i = 0; i < length; i++) {
if (rocks[i] - before < diff) { // diff보다 작으니 돌을 없애자
remove++;
} else {
before = rocks[i];
}
if (remove > n) { // 돌을 n개보다 더 없애야 하는 경우
return false;
}
}
if (distance - before < diff) {
remove++;
}
return remove <= n;
}
}
N x N크기의 정사각형 격자 형태에서 (0, 0) ~ (N-1, N-1)까지 경주로를 만드는데
직선 도로하나를 만들 때는 100원이 소요되며,코너를 하나 만들 때는 500원이 든다.
경주로를 만드는 데 최소 비용을 구하는 문제이다.
1차 시도 - BFS로 모든 방향에 대한 비용을 구하면서 재방문의 경우는 제외해주도록 한다. -> O(3^N)이 걸릴 것이기 때문에 시간 초과..
심지어 정확도도 틀림
import java.util.*;
class Solution {
public static int dr[] = { 0, 1, 0, -1 };
public static int dc[] = { 1, 0, -1, 0 };
public int solution(int[][] board) {
Queue<Move> queue = new LinkedList<Move>();
for (int i = 0; i < 4; i++) {
queue.add(new Move(dr[i], dc[i], i, 100)); // 이 부분이 벽일 수도 있기 때문에 정확도가 틀린 것이었다.
}
int min = Integer.MAX_VALUE;
int length = board.length;
while (!queue.isEmpty()) {
Move now = queue.poll();
if (now.row == length - 1 && now.col == length - 1) {
min = Math.min(min, now.value);
}
for (int i = 0; i < 4; i++) {
if (Math.abs(i - now.direction) == 2) {
continue;
}
int newRow = now.row + dr[i];
int newCol = now.col + dc[i];
int newValue = now.direction == i ? 100 : 600;
newValue += now.value;
if (isBoundary(newRow, newCol, length) && newValue > 0 && newValue < min
&& board[newRow][newCol] == 0) {
queue.add(new Move(newRow, newCol, i, newValue));
}
}
}
return min;
}
public boolean isBoundary(int row, int col, int N) {
if (row < 0) {
return false;
}
if (col < 0) {
return false;
}
if (row >= N) {
return false;
}
if (col >= N) {
return false;
}
return true;
}
}
class Move {
int row;
int col;
int direction;
int value;
public Move(int row, int col, int direction, int value) {
this.row = row;
this.col = col;
this.direction = direction;
this.value = value;
}
}
채점 결과
정확성: 30.4
합계: 30.4 / 100.0
2차시도 - 재 방문을 줄이자 => DP를 사용해볼까? 그런데 방향마다 더해지는 값이 달라서 DP에도 다르게 저장해야함
DP[i][j][k]: (0, 0) ~ (i, j)까지 k방향으로 움직였을 때 최소비용이라고 정의하도록 하자
import java.util.*;
import java.util.*;
class Solution {
public static int dr[] = { 0, 1, 0, -1 };
public static int dc[] = { 1, 0, -1, 0 };
public int solution(int[][] board) {
int min = Integer.MAX_VALUE;
int length = board.length;
int dp[][][] = new int[length][length][4];
Queue<Move> queue = new LinkedList<Move>();
for (int i = 0; i < 4; i++) {
queue.add(new Move(0, 0, i, 0));
}
while (!queue.isEmpty()) {
Move now = queue.poll();
if (now.row == length - 1 && now.col == length - 1) {
min = Math.min(min, dp[now.row][now.col][now.direction]);
}
for (int i = 0; i < 4; i++) {
if (Math.abs(i - now.direction) != 2) { // 후진 제외
int newRow = now.row + dr[i];
int newCol = now.col + dc[i];
int newValue = (now.direction == i ? 100 : 600) + now.value;
if (isBoundary(newRow, newCol, length) && board[newRow][newCol] == 0) {
if (dp[newRow][newCol][i] >= newValue || dp[newRow][newCol][i] == 0) {
dp[newRow][newCol][i] = newValue;
queue.add(new Move(newRow, newCol, i, newValue));
}
}
}
}
}
return min;
}
public boolean isBoundary(int row, int col, int N) {
if (row < 0) {
return false;
}
if (col < 0) {
return false;
}
if (row >= N) {
return false;
}
if (col >= N) {
return false;
}
return true;
}
}
class Move {
int row;
int col;
int direction;
int value;
public Move(int row, int col, int direction, int value) {
this.row = row;
this.col = col;
this.direction = direction;
this.value = value;
}
}
class Solution {
public int[] solution(int n, int s) {
LinkedList<Integer> answer = new LinkedList<Integer>();
if (s / n == 0) {
answer.add(-1);
} else {
answer.addAll(findSimilarElements(n, s));
}
return answer.stream().sorted().mapToInt(i -> i).toArray();
}
public LinkedList<Integer> findSimilarElements(int n, int s) {
LinkedList<Integer> list = new LinkedList<Integer>();
int quotient = s / n;
int remainder = s % n;
for (int i = 0; i < remainder; i++) {
list.add(quotient + 1);
}
for (int i = remainder; i < n; i++) {
list.add(quotient);
}
return list;
}
}
결과 - 시간초과
2차 시도 - sorting 부분을 지우자
1 <= n <= 10,000 이고 1 <= s <= 100,000,000이며 위의 경우는 sorting때문에 시간 복잡도가 O(NlogN)이었을 것이다.
아래와 같은 코드로 바꾼다면 O(N)만에 동작할 수 있다.
class Solution {
public int[] solution(int n, int s) {
LinkedList<Integer> answer = new LinkedList<Integer>();
if (s / n == 0) {
answer.add(-1);
} else {
answer.addAll(findSimilarElements(n, s));
}
return answer.stream().mapToInt(i -> i).toArray();
}
public LinkedList<Integer> findSimilarElements(int n, int s) {
LinkedList<Integer> list = new LinkedList<Integer>();
int quotient = s / n;
int remainder = s % n;
int quotientNumber = n - remainder;
for (int i = 0; i < quotientNumber; i++) {
list.add(quotient);
}
for (int i = quotientNumber; i < n; i++) {
list.add(quotient + 1);
}
return list;
}
}
결과는 마찬가지로 시간초과...
3차시도 - 아무래도 stream부분과 list를 addAll하는 곳 때문에 시간 초과가 난 것 같다.
어차피 원소의 개수는 n개로 일정하기 때문에 LinkedList를 array로 바꾸는 방식이 아니라 바로 array를 구하도록 하자
class Solution {
public int[] solution(int n, int s) {
if (s / n == 0) {
return new int[] { -1 };
}
return findSimilarElements(n, s);
}
public int[] findSimilarElements(int n, int s) {
int[] answer = new int[n];
int quotient = s / n;
int remainder = s % n;
int quotientNumber = n - remainder;
for (int i = 0; i < quotientNumber; i++) {
answer[i] = quotient;
}
for (int i = quotientNumber; i < n; i++) {
answer[i] = quotient + 1;
}
return answer;
}
}
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;
}
}
