끄적끄적

[lv3] 카운트 다운

https://school.programmers.co.kr/learn/courses/30/lessons/131129# 조금 어려웠던 DP문제다. 접근법 [싱글 & 불]에 대해 :- 더 적은 시행 횟수(dp[i][0])나, 시행 횟수를 늘리지 않고 더 높은 점수(dp[i][1])인 경우를 기록한다. [더블 & 트리플]에 대해 :- 더 적은 시행횟수(dp[i][0])인 경우를 기록한다. [더블 & 트리플] 탐색은 점수를 늘리지 않으므로, 점수를 비교할 필요는 없다. - i번째 dp를 탐색 중이라면, 이전의 점수(자연수 n에 대해, dp[i-n][1])는 항상 최적임이 보장된다.=> i-n번째 [싱글 & 불]의 탐색에서 이미 갱신했음 생각해본 다른 풀이- 시간초과 요인은 target(10만)이며, 다트를 던지..

https://school.programmers.co.kr/learn/courses/30/lessons/17686 구현(문자열 처리) or 정규 표현식 문제다. 정규 표현식 문법을 몰라서 전자로 풀이했다.일반적인 구현 외에, 비교는 A'으로 하고 출력은 A로 해야하는 점이 좀 까다로웠다.   안해도 되는 것같은 정렬 기준을 가진 원소는 정렬 이후에도 순서가 유지된다. list에 file을 순차적으로 넣었으면 고려할 필요가 없다.  시간 소요 요인 (docs 뒤져서 찾았다.)1. isDigit를 isNumeric으로 잘못 알고있었다. (해당 메서드는 Character 클래스에 없다.) 2. isLetter에 숫자 또한 포함인걸 몰랐다. (head 판별식에 숫자가 아닌 부분을 찾는 용도로 사용했었다.) 때문..

https://school.programmers.co.kr/learn/courses/30/lessons/60062 구현 + 순열 문제다.풀이법은 [모든 weak 경우]에 [모든 dist 경우]를 비교해서, 각 탐색이 weak point를 다 덮을 수 있는지 판단하면 된다.  실수한 부분 맨 처음에 그리디 문제인가 고민하다 아니라고 생각했다. (확정은 못지었다.)이후 완전탐색 하기로 했지만, 코드에 사용한 로직의 복잡도를 O(15! * 8!)로 착각해서 적용하기까지 오래걸렸다. => dist를 뽑는 경우의 수는 순열이므로 8!인데 반해,=> weak는 순서가 변하지 않으므로 15!이 아닌 15였다. + 15!는 약 1조3천억 이었다.   풀이법  1. weak 경우의 수 구하기 각 취약지점 배정 순서를 달..

https://school.programmers.co.kr/learn/courses/30/lessons/169199 기본 bfs 문제에 델타를 1칸 이동 -> 갈 수 있는 데까지 이동으로 바꾼 형식이었다. import java.util.*;class Solution { public int solution(String[] board) { int answer = 0; int R = board.length; int C = board[0].length(); int gr=0, gc=0, rr=0, rc=0; int[] dr = {0,0,1,-1}; int[] dc = {1,-1,0,0}; char[][] map = new..

https://school.programmers.co.kr/learn/courses/30/lessons/17683 파싱 + 구현 문제다. 1. 음 전처리하기 (편의상 사용)- 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다. #이 붙은 음들은 문자열 길이 판단 및 비교에 번거로우므로, 전처리한다.여러 방법이 있겠지만, 나는 소문자로 변환하였다. 2. 재생한 곡 정보 파싱하기(종료 시각 - 시작 시각)으로 총 시간을 구한다.(문제 조건에서, 음악이 00:00을 넘어가는 경우는 없으므로 식을 단순하게 놓아도 된다.) 이후 전처리한 악보를 기반으로, idx를 mod 연산하며 풀 악보를 만든다. 3. 정답 해 추가하기문제에서 해가 여..

https://school.programmers.co.kr/learn/courses/30/lessons/12936 수학 문제다. 개인적으로 풀이 이후 설명하기 참 난해한 문제라고 느꼈다.  문제에서 가능한 k의 범위는 1  다만, k 값이 long으로 주어지므로 20!이 long 범위를 넘는지는 판단하지 않아도 된다.  1. 첫번째 원소 판단 (n = 3, k = 5 일 때) n=3 일 때 가능한 수열을 나열하면,[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 찾고자 하는 5번 째 수열 (k = 5)의  첫번 째 수는 3이어야 한다. 이는,n = 3 일 때 전체 경우의 수 (3 * 2 * 1) 에서, (k / 2 * 1) + ( k % 2 * 1..

https://school.programmers.co.kr/learn/courses/30/lessons/12978 1번(코드에선 0번) 노드를 기준으로, 다익스트라를 통해 도달하는 비용이 k 이하인 노드의 개수를 출력한다. 노드 간 간선이 여러 개일 수 있는데, 이는 비용이 최소인 간선 하나만 사용한다.또한, 1번 노드에서 1번 노드로 가는 경우도 cnt해야 함에 주의한다. import java.util.*;class Solution { public int solution(int N, int[][] road, int K) { int MAX = Integer.MAX_VALUE / 2; int[][] graph = new int[N][N]; int[] cost = ..

https://school.programmers.co.kr/learn/courses/30/lessons/152996 수학 문제다. 완탐시 최대 O( 3^2 * 10만 * 10만)로 불가능하다. 풀이 1. 모든 탐색 대신, 모든 원소를 map으로 기록한다. 2. 원소의 개수 별로 "가능한 쌍의 수" 값이 담긴 누적 합 배열을 구한다.e.g.)원소가 2개 => 쌍의 수 : 1원소가 3개 => 쌍의 수 : 1 + 2 = 3원소가 4개 => 쌍의 수 : 1 + 2 + 3 = 6 3. 누적 합 배열을 바탕으로 map을 순회하며 answer에 값을 누적한다. 4. 중복된 만큼 answer에서 값을 빼준다. e.g.)[100, 100, 100] // answer : 3, wrong answer : 9위의 경우, 3번..

https://school.programmers.co.kr/learn/courses/30/lessons/155651 파싱 + 정렬 + 우선순위 큐(스케쥴링) 문제다.웰노운 문제에 파싱(시간활용)을 섞은 느낌이었다.import java.util.*;class Solution { public int solution(String[][] book_time) { int R = book_time.length; int loom = 1; int[][] times = new int[R][2]; PriorityQueue pq = new PriorityQueue(); for(int i=0; i a1[0] - a2[0]); for(int i=0;..

https://school.programmers.co.kr/learn/courses/30/lessons/131127 map을 이용한 슬라이딩 윈도우 / 투 포인터 문제 map 탐색간 널포인터 처리만 유의하면 특별한건 없었다.import java.util.*;class Solution { public int solution(String[] want, int[] number, String[] discount) { int w = want.length; int d = discount.length; int answer = 0; int SIZE = 10; Map window = new HashMap(); // window init ..