끄적끄적

https://school.programmers.co.kr/learn/courses/30/lessons/77886  1. 모든 "110" 제거주어진 문자열에서 "110"을 모두 추출한다. 111100 과 같이 하나의 "110"을 추출했을 때 나머지가 다시 "110"을 이룰 수 있으므로,StringBuilder을 Stack처럼 활용한다.(괄호 유효성 검사 문제로 빗대면, "11"을 "{"로, 0을 "}"로 놓는다.) 2. 사전 순으로 앞서게 배치?경우의 수를 생각해보면, "110"은 "111"인 부분을 replace할 때만 사전 순으로 앞선다.000 ~ 101인 부분을 대체한다면 사전 순을 늦추기만 한다. 3. 반례2번 논리로만 접근하면 반례가 있다.입력 : 111000오답 : 110100정답 : 1001..

https://school.programmers.co.kr/learn/courses/30/lessons/68646  생전 처음보는 유형이었다. 그리디하게 풀 수 있다. 인접한 풍선을 계속 터트렸을 때, n번째 풍선이 남을 수 있는 경우의 수를 출력하는 문제다.단, 항상 인접한 풍선 중 숫자가 큰 것을 터트려야 하며, [딱 한번 숫자가 작은 것을 터트릴 수 있다.] 배열 사이즈는 최대 100만이므로 완전 탐색은 할 수 없다.그러므로 약간 dp적 사고?를 하려했고 dp[i][2]로 놓아 각각 예외를 사용했을 경우와 안했을 경우의 최적 값으로 놓으려했다. 적용하려 하니 쉽지 않았다.  그래서 사고를 바꿨다. 1. 왼쪽/오른쪽 부터 탐색했을 때 최솟값을 담은 2개의 배열을 초기화한다.e.g. l[3] = (id..

https://school.programmers.co.kr/learn/courses/30/lessons/77486 특별한 알고리즘은 없는 단순 구현문제였다. 각 판매원을 Node로 치환하고 map으로 관리하면 쉬웠다.문제 설명이 엄청 길어서 center라는 루트 노드가 존재함을 놓치지 말아야 한다. import java.util.*;class Node { Node parent; int money = 0; Node(Node parent) { this.parent = parent; }}class Solution { public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount..

https://school.programmers.co.kr/learn/courses/30/lessons/132266 일단 희소그래프 이므로 인접리스트로 구현했다. 풀이 1 - BFS + cost 배열(dp) BFS를 사용하므로, destination에 도착하면 항상 최단 거리임이 보장된다.큐가 비어있는데도 destination에 도착하지 못한다면 -1을 넣는다. 단, BFS만 사용하면 시간초과가 발생하므로노드 at에서 destination까지 가는 비용을 적은 cost[at]이 이미 존재한다면 사용하고 탐색을 마친다. import java.util.*;class Solution { public int[] solution(int n, int[][] roads, int[] sources, int des..

https://school.programmers.co.kr/learn/courses/30/lessons/1619881. DP 점화식 세우기 어떤 수를 사용했는가는 관심사가 아니므로, i번째에 이룰 수 있는 최댓값만 기록 dp[i][0] = i번째가 1 *  sequence[i]일 때 이룰 수 있는 최댓 값dp[i][1] = i번째가 -1 * sequence[i]일 때 이룰 수 있는 최댓 값 2. 최댓 값 산정 방식 dp[i][0] = Math.max(dp[i-1][1], 0) + sequence[i]; dp[i][1] = Math.max(dp[i-1][0], 0) - sequence[i]; i-1 이 음수라면 i번 째 값을 낮추기만 하므로 최댓 값 해에 포함하지 않는다. 3. 출력 dp[dp.length..

https://school.programmers.co.kr/learn/courses/30/lessons/67258 1. 전처리문자로 비교하면 비효율적이다. int gTotal = 존재하는 보석 가짓수int[] gemArr = 보석 이름(문자열) 대신 int key로 비교할 배열 2. 투포인터 + 슬라이딩 윈도우int total = 현재 윈도우에 포함되는 보석 가짓수 total gTotal  : 정답 조건을 만족하지 않으므로 ed++;total == gTotal : 정답과 비교 및 st++;(현재 윈도우에 st를 높혀도 정답인 경우가 존재할 수 있음) ed가 끝에 닿은 경우total == gTotal : 정답이 될 수 있는 경우의 수가 남았으므로 st++;total : st++을 계속 해도 total이 ..

https://school.programmers.co.kr/learn/courses/30/lessons/64064 인접리스트 + set + 비트마스킹으로 풀었다. 1. 조합 혹은 순열을 뽑고, 아이디를 매칭하면 매 순간 아이디를 비교해야 하므로 비효율적이다.(문제에서 주어지는 변수가 매우 작으므로 가능하긴 하다.)그래서, 처음부터 banned_id 아이디에 포함되는 user_id를 인접리스트에 key값으로 저장한다. 2. 경우의 수를 구하는 법 [1번] [2번] [3번] A       A       B B      B      D C 후보군의 선택지는 다음 형태와 같다.각 번호는 모두 하나의 알파벳이 할당되어야 하며, 알파벳을 중복하여 사용할 수 없다. 1번에 A,B를 선택하면 2번의 경우의 수에 영향을..

https://school.programmers.co.kr/learn/courses/30/lessons/12971 1. dp 배열의 설정dp[i][Y] - i번째 스티커를 떼어냈을 때 최댓값dp[i][N] - i번째 스티커를 떼지 않았 때 최댓값 2. 뽑는 경우의 수는 2가지 [o x o], [o x x o]후자의 경우를 위해, i-2번째 까지 고려  3. 점화식 세우기 3-1. dp[i][Y] = Math.max(dp[i-1][N], dp[i-2][Y]) + sticker[i];dp[i-1][Y] => 불가능 dp[i-2][N] => 항상 dp[i-2][Y] > dp[i-2][N] 이므로 고려할 필요 X 3-2. dp[i][N] = Math.max(dp[i-1][Y],  dp[i-2][Y]]);dp[i..

https://school.programmers.co.kr/learn/courses/30/lessons/12979 문제의 핵심은, 기지국 간의 전파 범위는 모두 같다는 것을 시작으로 접근하는 것이다. 이 때문에,A의 왼쪽에 B를 놓았을 때 B의 범위가 A의 오른쪽 범위를 넘는 경우는 없다.(전파 범위가 모두 다르다면, B를 놓은 곳이 다음 탐색이나 양쪽 끝단에까지 영향을 미칠 수 있다.) 따라서, 추가 기지국을 설치할 때 기존의 기지국과 겹치지 않는 곳 부터 차례대로 설치하면 된다. => 그리디  해결 방법 1. 가장 왼쪽의 기지국의 왼쪽 전파 범위에서 시작, 왼쪽 끝의 아파트에 닿을 때 까지 추가 기지국을 세운다. 2. 가장 오른쪽의 기지국의 오른쪽 전파 범위에서 시작, 오른쪽 끝의 아파트에 닿을 때 ..

https://school.programmers.co.kr/learn/courses/30/lessons/12987# B가 많이 이기는 방법 1. A와 B를 내림차순 정렬한다. 2. B의 top이 A의 top을이긴다면, B top과 A top을 매칭한다. => 점수 획득지거나 동점이라면, B tail과 A top을 매칭한다. => 점수 미획득(동점인 경우 그냥 매칭시켜서 최적보다 높은 점수인 경우는 없다.) 앞과 뒤의 원소를 모두 뺼 수 있어야 하므로 deque를 사용했다.내가 알기론, 기본형 배열을 내림차순 정리하는 메서드는 제공하지 않는다.따라서, tmp 컨테이너에 정렬한 후 다시 배열로 옮기거나 wrapper class 배열로 바꿔야한다. 때문에, 그냥 오름차순 정렬하고 0이 아닌 A.length -..