공부 기록

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

풀이 로직은 아래와 같다.

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;
	}
}

dp[n]: n원을 낼 수 있는 가짓수로 정의한다.

class Solution {
	public int solution(int n, int[] money) {
		int dp[] = new int[n + 1];
		dp[0] = 1;

		for (int coin : money) {
			for (int i = 1; i <= n; i++) {
				if (i - coin >= 0) {
					dp[i] += dp[i - coin];
				}
			}
		}

		return dp[n];
	}
}

왜 2중for문의 안과 밖이 바뀌면 중복된 값, 예를 들어 [10, 20, 10]과 [10, 10, 20]을 다른 경우로 체크해서 더 많은 값이 나온다.

예시 1 답: (트리의 지름) - 1

예시 2 답: (트리의 지름)

1차 시도 - 시간초과

트리의 지름을 가지는 노드가 2쌍 이상이면 2번 예시에 들어가고, 한 쌍이면 1번 예시에 들어가게 된다.

트리의 지름을 구하는 방법은

1. 임의의 노드에서 가장 먼 거리의 노드을 찾는다.

2. 찾은 노드에서 또 가장 먼 거리의 노드를 찾는다. => 이 값이 트리의 지름, 두 노드가 트리의 끝점이다.

class Solution {
	public static int radius = 0;
	public static HashSet<NodePair> endPoints = new HashSet<NodePair>();

	public int solution(int n, int[][] edges) {
		int[] distanceFromNodeOne = new int[n + 1];

		LinkedList<Integer> connectedNodes[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			connectedNodes[i] = new LinkedList<Integer>();
		}
		for (int i = 0; i < edges.length; i++) {
			int start = edges[i][0];
			int end = edges[i][1];

			connectedNodes[start].add(end);
			connectedNodes[end].add(start);
		}

		findRadius(1, connectedNodes, n, true);
		
		int maxSize = 0;
		for(NodePair nodepair:endPoints) {
			if(radius<=nodepair.distance) {
				maxSize++;
			}
		}

		if (maxSize >= 2) {
			return radius;
		}
		return radius - 1;
	}

	public void findRadius(int startPoint, LinkedList<Integer> connectedNodes[], int n, boolean isFirstTurn) {
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(new Node(startPoint, 0));

		int maxDistance = 0;
		int distanceFromNodeOne[] = new int[n + 1];

		// 1번 노드에서 가장 먼 노드 구하기
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			distanceFromNodeOne[node.name] = node.distance;
			maxDistance = Math.max(maxDistance, node.distance);

			LinkedList<Integer> connection = connectedNodes[node.name];
			for (int nextNode : connection) {
				if (distanceFromNodeOne[nextNode] == 0 && nextNode != startPoint) {
					queue.add(new Node(nextNode, node.distance + 1));
				}
			}
		}

		LinkedList<Integer> maxNodes = new LinkedList<Integer>();
		for (int i = 1; i <= n; i++) {
			if (distanceFromNodeOne[i] == maxDistance) {
				maxNodes.add(i);
			}
		}

		if (!isFirstTurn) {
			for (int nextPoint : maxNodes) {
				if (radius <= maxDistance) {
					endPoints.add(new NodePair(Math.min(startPoint, nextPoint), Math.max(startPoint, nextPoint),
							maxDistance));
					radius = maxDistance;
				}
			}
			return;
		}

		HashSet<Integer> nodeSet = new HashSet<Integer>();
		nodeSet.addAll(endPoints.stream().map(nodepair -> nodepair.node1).collect(Collectors.toSet()));
		nodeSet.addAll(endPoints.stream().map(nodepair -> nodepair.node2).collect(Collectors.toSet()));
		for (int nextPoint : maxNodes) {
			if (!nodeSet.contains(nextPoint)) {
				findRadius(nextPoint, connectedNodes, n, false);
			}
		}
	}
}

class Node {
	int name;
	int distance;

	public Node(int name, int distance) {
		this.name = name;
		this.distance = distance;
	}

	public String toString() {
		return name + " " + distance;
	}
}

class NodePair {
	int node1;
	int node2;
	int distance;

	public NodePair(int node1, int node2, int distance) {
		this.node1 = node1;
		this.node2 = node2;
		this.distance = distance;
	}

	public String toString() {
		return node1 + "-" + node2 + " " + distance;
	}
}

정확성: 84.6

합계: 84.6 / 100.0

시간초과가 난 이유는 아무래도 nodeSet을 계속 계산해 주어서가 아닐까 생각해본다.

2차 시도 - nodeSet을 static으로 빼기, 쓸데없는 객체 안쓰기 => 테스트케이스19 TL

import java.util.*;
class Solution {
	public static int radius = 0;// 트리의 지름
	public static HashSet<Integer> nodeSet = new HashSet<Integer>();// 지름이 되는 노드의 집합

	public int solution(int n, int[][] edges) {
		// 인접 노드 전처리
		LinkedList<Integer> connectedNodes[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			connectedNodes[i] = new LinkedList<Integer>();
		}
		for (int i = 0; i < edges.length; i++) {
			int start = edges[i][0];
			int end = edges[i][1];
			connectedNodes[start].add(end);
			connectedNodes[end].add(start);
		}
		findRadius(1, connectedNodes, n, true);
		if (nodeSet.size() == 2) {
			return radius - 1;
		}
		return radius;
	}

	/*
	 * 1. 임의의 노드에서 가장 먼 거리의 노드을 찾는다. 
	 * 2. 찾은 노드에서 또 가장 먼 거리의 노드를 찾는다. => 값이 트리의 지름, 두 노드가 트리의 끝점이다.
	 */
	public void findRadius(int startPoint, LinkedList<Integer> connectedNodes[], int n, boolean isFirstTurn) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(startPoint);
		int maxDistance = 0;// startPoint에서 가장 먼 길이
		int distanceFromStartNode[] = new int[n + 1];// startPoint에서 다른 노드들까지 거리
		// startPoint 노드에서 가장 먼 노드 구하기 - bfs
		LinkedList<Integer> maxNodes = new LinkedList<Integer>();// 가장 먼 노드의 집합
		while (!queue.isEmpty()) {
			int node = queue.poll();

			// 가장 먼 노드 집합 업데이트
			if (maxDistance < distanceFromStartNode[node]) {
				maxDistance = distanceFromStartNode[node];
				maxNodes.clear();
				maxNodes.add(node);
			} else if (maxDistance == distanceFromStartNode[node]) {
				maxNodes.add(node);
			}
			LinkedList<Integer> connection = connectedNodes[node];
			for (int nextNode : connection) {
				if (distanceFromStartNode[nextNode] == 0 && nextNode != startPoint) {
					queue.add(nextNode);
					distanceFromStartNode[nextNode] = distanceFromStartNode[node] + 1;
				}
			}
		}
		if (!isFirstTurn) { // 첫번째 턴이 아니면 = 지름 다 구했으니 리턴
			if (radius < maxDistance) {
				nodeSet.clear();
				nodeSet.add(startPoint);
				radius = maxDistance;
				for (int nextPoint : maxNodes) {
					nodeSet.add(nextPoint);
				}
			} else if (radius == maxDistance) {
				nodeSet.add(startPoint);
				radius = maxDistance;
				for (int nextPoint : maxNodes) {
					nodeSet.add(nextPoint);
				}
			}
			return;
		}
		
		// 첫번째 턴이면 여기서 다시 가장 먼 노드를 구한다
		for (int nextPoint : maxNodes) {
			if (!nodeSet.contains(nextPoint)) {
				findRadius(nextPoint, connectedNodes, n, false);
			}
		}
	}
}

채점 결과

정확성: 96.2

합계: 96.2 / 100.0

3차 시도 - 첫번째 턴에서 구한 모든 노드에서 다시 가장 먼 노드를 구할 때 중복된 연산이 존재한다는 것을 깨달았다.

그래서 기존 로직에서 살짝 바꿔서 트리의 지름이 될 수 있는 쌍이 몇쌍인지 먼저 생각해 보기로 했다.

1. 임의의 노드 A 에서 가장 먼 거리의 노드을 찾는다.

2. 찾은 노드 B 에서 또 가장 먼 거리의 노드 C 를 찾는다. => 이 값이 트리의 지름, 두 노드가 트리의 끝점이다.

    => C 노드가 2개 이상 == 예시 2

3. C 노드가 1개인 경우 다시 가장 먼 거리의 노드 D 를 찾는다 => D 노드가 2개 이상 == 예시 2 / 1개 == 예시 1

class Solution {
	public static int radius = 0;

	public int solution(int n, int[][] edges) {
		LinkedList<Integer> connectedNodes[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			connectedNodes[i] = new LinkedList<Integer>();
		}
		for (int i = 0; i < edges.length; i++) {
			int start = edges[i][0];
			int end = edges[i][1];

			connectedNodes[start].add(end);
			connectedNodes[end].add(start);
		}

		boolean isonepair = isOnePair(1, connectedNodes, n, 0);

		if (isonepair) {
			return radius - 1;
		}
		return radius;
	}

	public boolean isOnePair(int startPoint, LinkedList<Integer> connectedNodes[], int n, int turn) {

		int[] distanceFromStartPoint = calculateDistanceBFS(startPoint, connectedNodes, n);
		int maxNode = findMaxNode(distanceFromStartPoint, n);

		if (turn >= 1) {
			int maxNodeNum = 0;
			radius = Math.max(radius, distanceFromStartPoint[maxNode]);
			for (int i = 1; i <= n; i++) {
				if (distanceFromStartPoint[maxNode] == distanceFromStartPoint[i]) {
					maxNodeNum++;
				}
			}

			if (maxNodeNum >= 2) {
				return false;
			}

			if (turn > 1) {
				return true;
			}

			return isOnePair(maxNode, connectedNodes, n, 2);
		}

		return isOnePair(maxNode, connectedNodes, n, 1);
	}

	public static int findMaxNode(int[] distance, int n) {
		int maxNode = 1;
		for (int i = 1; i <= n; i++) {
			if (distance[i] > distance[maxNode]) {
				maxNode = i;
			}
		}
		return maxNode;
	}

	public static int[] calculateDistanceBFS(int startPoint, LinkedList<Integer> connectedNodes[], int n) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(startPoint);

		int distanceFromNode[] = new int[n + 1];
		while (!queue.isEmpty()) {
			int node = queue.poll();

			LinkedList<Integer> connection = connectedNodes[node];
			for (int nextNode : connection) {
				if (distanceFromNode[nextNode] == 0 && nextNode != startPoint) {
					queue.add(nextNode);
					distanceFromNode[nextNode] = distanceFromNode[node] + 1;
				}
			}
		}

		return distanceFromNode;
	}
}

규칙

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

1차시도 - 가장 먼저 떠오른 풀이로는 배정된 방 리스트를 해시맵에 넣어두고 있으면 다음 번호를 리턴해주면 되지 않을까 생각했다.

아래 코드를 설명해 보자면, 이미 예약된 호텔의 경우 해시 맵에 넣고 해시맵에 있으면 다음 번호를 확인하는 식이다.

import java.util.*;
class Solution {
	public long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		HashSet<Long> reservedRoomNumber = new HashSet<Long>();
		
		for(int i=0;i<room_number.length;i++) {
			answer[i] = getRoomNumber(room_number[i], reservedRoomNumber);
		}
		
		return answer;
	}

	public long getRoomNumber(long target, HashSet<Long> reservedRoomNumber) {
		if(reservedRoomNumber.contains(target)) {
			long emptyRoom = getRoomNumber(target+1, reservedRoomNumber);
			return emptyRoom;
		}
		
		reservedRoomNumber.add(target);
		return target;
	}
}

결과는 효율성 테스트에서 전멸했다...ㅎㅎ

생각해보니 이렇게 짜면 남아있는 다음 방을 찾을 때

10번방 다음 번호로 가능한 방 번호가 100번이면 11~100번까지 순차적으로 모두 봐야하니 시간초과가 날 수밖에 없었음

=> 순차적으로 본다고 해도 다음에 같은 번호를 찾을 때에는 다시 안 보도록 어딘가 저장을 해 두자 => DP를 사용해 볼까?

2차시도 - 그렇다면 10번방 바로 다음 번호가 100번인걸 어떻게 바로 알려줄까 생각해봤다.

DP라고 하기엔 조금 애매하지만,

dp[roomNumber] = nextEmptyRoomNumber 이런식으로 저장해서 다음에는 이 배열만 access하면 되도록 만들어 봤다.

import java.util.*;
class Solution {
	public long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		long[] dp = new long[(int) (k + 1)];

		for (int i = 0; i < room_number.length; i++) {
			answer[i] = getRoomNumber(room_number[i], dp);
		}

		return answer;
	}

	public long getRoomNumber(long target, long[] dp) {
		if (dp[(int) target] == 0.0) {
			dp[(int) target] = target + 1;
			return target;
		}

		long nextRoom = dp[(int) target];
		long nextEmptyRoom = getRoomNumber(nextRoom, dp);
		dp[(int) nextRoom] = nextEmptyRoom + 1;
		return nextEmptyRoom;
	}
}

엄청 빠르다...!! 그치만 메모리 초과와 런타임 에러가 생겼다. 

왜 이런지 생각해 봤는데 일단 k는 1 이상 10^12 이하인 자연수이다. (java에서 선언할 수 있는 최대 배열 길이는 2^31 − 1이다.)

3차 시도 - Long을 key로 할 수 있는 HashMap에다가 넣자!

왜냐면 쓸데 없이 만들어진 뒤에 쓰지 않는 배열 원소가 있어서 OOME가 났기 때문이다. 풀이는 아래와 같다.

2차시도에서처럼 array를 직접 접근하지 않고 logn으로 계속 찾는 형식이기 때문에 시간은 훨씬 오래 걸리지만 통과..

hashmap 외에 treemap, linkedhashmap은 더 느리다는 것을 확인했다.

class Solution {
	public long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		HashMap<Long, Long> roomRemainNumber = new HashMap<Long, Long>();

		for (int i = 0; i < room_number.length; i++) {
			answer[i] = getRoomNumber(room_number[i], roomRemainNumber);
		}

		return answer;
	}

	public long getRoomNumber(long target, HashMap<Long, Long> roomRemainNumber) {
		if (!roomRemainNumber.containsKey(target)) {
			roomRemainNumber.put(target, target + 1);
			return target;
		}

		long room = roomRemainNumber.get(target);
		long emptyRoom = getRoomNumber(room, roomRemainNumber);
		roomRemainNumber.put(target, emptyRoom + 1);
		return emptyRoom;
	}
}

배운점

2020/12/19 - [Java] - Java HashMap vs LinkedHashMap vs TreeMap

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;
	}
}

원래 풀이는 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