진짜 오랜만입니다
551. Student Attendance Record I
class Solution {
public boolean checkRecord(String s) {
int absent = 0;
int consecLate = 0;
for (int i = 0; i < s.length(); i++) {
char attendance = s.charAt(i);
if (attendance == 'A') {
absent++;
consecLate = 0;
if (absent >= 2) {
return false;
}
} else if (attendance == 'L') {
consecLate++;
if (consecLate >= 3) {
return false;
}
} else {
consecLate = 0;
}
}
return true;
}
}Runtime: 0 ms, faster than 100.00% of Java online submissions for Student Attendance Record I.
Memory Usage: 36.9 MB, less than 79.79% of Java online submissions for Student Attendance Record I.
너무 쉬워서 마 카카오 니 구글처럼 글로벌 기업 되려면 이렇게 문제 내라 하려고 했건만......^^
루션이
public class Solution {
public boolean checkRecord(String s) {
return !s.matches(".*(A.*A|LLL).*");
}
}public class Solution {
public boolean checkRecord(String s) {
int count=0;
for(int i=0;i<s.length() && count<2 ;i++)
if(s.charAt(i)=='A')
count++;
return count<2 && s.indexOf("LLL")<0;
}
}
제 루션이는 simple solution보다 못하네요..^^
743. Network Delay Time
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
//update total time with max
Map<Integer, Map<Integer, Integer>> neighbor = new HashMap<Integer, Map<Integer, Integer>>();
for (int[] time : times) {
if (! neighbor.containsKey(time[0])) {
neighbor.put(time[0], new HashMap<Integer, Integer>());
}
neighbor.get(time[0]).put(time[1], time[2]);
}
//Dijkstra 시작.
//minheap
PriorityQueue<int[]> dist = new PriorityQueue<int[]>((n1, n2) -> n1[0] - n2[0]);
//시작점
int[] first = new int[]{0, k};
dist.add(first);
int totalTime = 0;
while (!dist.isEmpty()) {
int[] d = dist.remove();
int goal = d[0];
int distance = d[1];
totalTime = distance;
if (neighbor.containsKey(goal)) {
for (int ne : neighbor.get(goal).keySet()) {
int newDist = distance + neighbor.get(goal).get(ne);
dist.add(new int[]{newDist, ne});
}
}
}
return totalTime;
}
}3 / 52 test cases passed.
아놔 이거 루션이 보기도 싫어요ㅠ
나름 dijkstra 예전 수업 노트까지 뒤져가면서 풀었는데 안풀리네요^^
노력은 배신한다는 점~
참고한 dijkstra 코드
루션이
DFS
class Solution {
Map<Integer, Integer> dist;
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, List<int[]>> graph = new HashMap();
for (int[] edge: times) {
if (!graph.containsKey(edge[0]))
graph.put(edge[0], new ArrayList<int[]>());
graph.get(edge[0]).add(new int[]{edge[2], edge[1]});
}
for (int node: graph.keySet()) {
Collections.sort(graph.get(node), (a, b) -> a[0] - b[0]);
}
dist = new HashMap();
for (int node = 1; node <= N; ++node)
dist.put(node, Integer.MAX_VALUE);
dfs(graph, K, 0);
int ans = 0;
for (int cand: dist.values()) {
if (cand == Integer.MAX_VALUE) return -1;
ans = Math.max(ans, cand);
}
return ans;
}
public void dfs(Map<Integer, List<int[]>> graph, int node, int elapsed) {
if (elapsed >= dist.get(node)) return;
dist.put(node, elapsed);
if (graph.containsKey(node))
for (int[] info: graph.get(node))
dfs(graph, info[1], elapsed + info[0]);
}
}Dijkstra
class Solution {
Map<Integer, Integer> dist;
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, List<int[]>> graph = new HashMap();
for (int[] edge: times) {
if (!graph.containsKey(edge[0]))
graph.put(edge[0], new ArrayList<int[]>());
graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
}
dist = new HashMap();
for (int node = 1; node <= N; ++node)
dist.put(node, Integer.MAX_VALUE);
dist.put(K, 0);
boolean[] seen = new boolean[N+1];
while (true) {
int candNode = -1;
int candDist = Integer.MAX_VALUE;
for (int i = 1; i <= N; ++i) {
if (!seen[i] && dist.get(i) < candDist) {
candDist = dist.get(i);
candNode = i;
}
}
if (candNode < 0) break;
seen[candNode] = true;
if (graph.containsKey(candNode))
for (int[] info: graph.get(candNode))
dist.put(info[0],
Math.min(dist.get(info[0]), dist.get(candNode) + info[1]));
}
int ans = 0;
for (int cand: dist.values()) {
if (cand == Integer.MAX_VALUE) return -1;
ans = Math.max(ans, cand);
}
return ans;
}
}Runtime: 12 ms, faster than 77.92% of Java online submissions for Network Delay Time.
Memory Usage: 42.8 MB, less than 52.29% of Java online submissions for Network Delay Time.
Dijkstra w/ Heap
class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, List<int[]>> graph = new HashMap();
for (int[] edge: times) {
if (!graph.containsKey(edge[0]))
graph.put(edge[0], new ArrayList<int[]>());
graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
}
PriorityQueue<int[]> heap = new PriorityQueue<int[]>(
(info1, info2) -> info1[0] - info2[0]);
heap.offer(new int[]{0, K});
Map<Integer, Integer> dist = new HashMap();
while (!heap.isEmpty()) {
int[] info = heap.poll();
int d = info[0], node = info[1];
if (dist.containsKey(node)) continue;
dist.put(node, d);
if (graph.containsKey(node))
for (int[] edge: graph.get(node)) {
int nei = edge[0], d2 = edge[1];
if (!dist.containsKey(nei))
heap.offer(new int[]{d+d2, nei});
}
}
if (dist.size() != N) return -1;
int ans = 0;
for (int cand: dist.values())
ans = Math.max(ans, cand);
return ans;
}
}Runtime: 17 ms, faster than 60.02% of Java online submissions for Network Delay Time.
그냥 ㅎㅏㅇㅕㅁ 없ㅇㅣ ㅅㅓ글ㅍㅓ ㅈㅕㅇㅓㅇ
그냥 ㅎㅏㅇㅕㅁ없ㅇㅣ ㄴㅜㄴ물ㅇㅣ ㄴㅏㅇㅏㅇ
y