SH

https://school.programmers.co.kr/learn/courses/30/lessons/43238# 이분 탐색 문제다. mid랑 midVal 이랑 변수명 착각해서 죙일 디버깅했다.문제에서 최악의 경우 10억*10억의 시간이 소요되므로, 이를 end 포인터로 놓는게 핵심이다. (Long.MAX_VALUE 등으로 놓으면 midVal에 오버플로가 발생함, 더 작으면 최악의 경우 케이스 틀림) + 문제엔 명시되지 않았지만, 아마 내림차순 정렬된 형태로 times가 주어지는 듯 하다.때문에 long ed = (long) times[times.length -1] * n도 가능class Solution { public long solution(int n, int[] times) { ..

https://school.programmers.co.kr/learn/courses/30/lessons/86971트리 형태의 전력망이 존재할 때, 무작위 전선(간선)을 하나 끊어서 분리된 A,B 송전탑(노드)집합의 개수 차이를 최소화 하는 문제다. 핵심 로직은 차이를 구하기 위해 A, B의 개수를 각각 구할 필요가 없다는 것이었다. 다음 식과 같다.B = 전체 - A차이 = | A - B |  즉, 차이 = | A - (전체 - A) |이후 bfs로 전력망을 하나씩 끊어가며 최소인 경우를 찾았다.다른 풀이를 찾아보았는데, A의 인접 간선을 하나씩 끊고, 다 끊었으면 인접 노드 B를 추가하여 또 다시 B의 인접 간선을 끊는 방식(dfs)이었다. import java.util.*;class Solution ..

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=java A, E, I, O, U 5개의 모음으로 (각 모음을 사용하지 않거나, 1번 이상 사용하여) 길이 5이하의 단어를 만드는 문제다.이후 정렬하여 몇 번째 단어인지 출력하면 된다. 1번째 는 A고 3095번째 단어는 UUUU였다. 코드에선 빈 문자열 ""가 0번째 인덱스를 채우면서 A가 1번째가 됐다.xxEIO와 xEIOx같은 경우는 문제에서 동일한 단어로 취급되므로 정확한 경우의 수를 구하긴 어려웠다. 그래서 set으로 검산하고 제출했다. import java.util.*;class Solution { public int solution(String word) {..

https://school.programmers.co.kr/learn/courses/30/lessons/42898처음엔 0열과 0행은 모두 한가지 최단 경로밖에 없으므로다음과 같은 꼴이라고 생각했다. 0열이나 0행에 웅덩이가 있는 경우가 반례였다.S 1 1 1 1 11 0 0 0 0 01 0 0 0 0 01 0 0 0 0 01 0 0 0 0 E이후 padding을 준 dp로 바꿨다.import java.util.*;class Solution { public int solution(int m, int n, int[][] puddles) { int mod = 1000000007; int[][] dp = new int[n+1][m+1]; dp[1][1] = 1; ..

https://school.programmers.co.kr/learn/courses/30/lessons/49189  백만년만의 그래프탐색 풀이노드에 비해 간선이 적어서 인접리스트로 구현했다.어떤 노드에 도달하는 경우의 수는 구할 필요가 없으므로 bfs를 썼다.iterator 문법이 가물해서 리마인드할 필요를 느꼈다. import java.util.*;import java.lang.*;class Solution { public int solution(int n, int[][] edge) { int answer = 0; int cnt = 0; int N = n; int eLen = edge.length; List..