끄적끄적

https://school.programmers.co.kr/learn/courses/30/lessons/92335# 헤맨 이유 본문 : 예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.)=> 숫자를 10진수로 변환하라는 뜻으로 착각 (10진법으로 표시된 수로 여기라는 뜻이었다.) 놓친 것소수에는 1이 포함되지 않음 class Solution { public int solution(int n, int k) { return getCnt(Integer.to..

https://school.programmers.co.kr/learn/courses/30/lessons/148653 매번 탐색마다 첫번 째 자리수 (storey % 10 값)만 비교하면 되므로 그리디로 접근하려다가, 올라가는 경우 다음 층에 영향을 주기에 일단락 했다. 문제에서storey 올라간다/내려간다  이진 탐색으로 구현하면 O(2^9)로 끝낼 수 있다. class Solution { int answer = Integer.MAX_VALUE; void solve(int storey, int cnt) { if(storey

https://school.programmers.co.kr/learn/courses/30/lessons/160585 틱택토 게임판이 주어졌을 때, 가능한 경우인지 판단하는 단순 구현 문제다. 고려한 경우 중 코드에 쓰지 않은 경우가 있다.(이는 O와 X개수 비교 조건에서 자동으로 걸러지므로 제외해도 된다.) e.g.)OXOXOXOXO(중간의 O를 마지막으로 두었다고 가정하면 올바른 경우, 아니라면 틀린 경우이므로 => 가능한 경우이다.) e.g.)OOO. . .OOO(이어진 곳이 2쌍 이상이고 겹치지 않음 => 순서를 어떻게 배치하던 불가능한 경우 => 하지만, O와 X의 개수 비교에서 자동으로 걸러지므로 고려X) class Solution { public int solution(String[] b..

https://school.programmers.co.kr/learn/courses/30/lessons/131701 누적합으로 투 포인터에 쓰일 초기 값을 구해준다.이후 투포인터로 탐색한다. 원형 배열이므로, 엔드 포인터가 배열의 끝에 닿으면 0으로 다시 바꿔준다. (입력 값 범위가 작으므로, 일일히 더하는 단순 구현으로도 될 것 같다.)import java.util.*;class Solution { public int solution(int[] elements) { int answer = 0; int E = elements.length; Set set = new HashSet(); // 누적합 : 윈도우 초기 값 int[] d = ne..

https://school.programmers.co.kr/learn/courses/30/lessons/12973# stack을 활용한 알파벳 유효성 판단 문제(대표적인 stack 문제인 괄호 유효성 판단 문제와 유사하다.) import java.util.*;class Solution{ public int solution(String s) { Stack stack = new Stack(); int idx = 0; while(idx

https://school.programmers.co.kr/learn/courses/30/lessons/12900 dp 기본형class Solution { public int solution(int n) { int answer = 0; int mod = 1000000007; int[][] dp = new int[n][2]; dp[0][0] = 1; for(int i=1; i

https://school.programmers.co.kr/learn/courses/30/lessons/138476 그리디 : 개수가 많은 귤부터 제외하는 것이 최적유의 사항 : 남은 k가 현재 탐색중인 귤의 개수보다 작거나 같아도 카운트 import java.util.*;class Solution { public int solution(int k, int[] tangerine) { int answer = 0; Map map = new HashMap(); List list = new ArrayList(); for(int tan : tangerine) { map.merge(tan, 1, (ov, nv) -> ov + 1); ..

https://school.programmers.co.kr/learn/courses/30/lessons/17684 문자열 + 단순 구현 LZW 압축 알고리즘을 구현하는 문제import java.util.*;class Solution { Map dic = new HashMap(); List ans = new ArrayList(); String msg; int lastIdx = 27; void solve() { StringBuilder ns = new StringBuilder(); int lastNum = -1; for(int i=0; i

https://school.programmers.co.kr/learn/courses/30/lessons/17687 Integer 클래스의 toString()에 radix를 파라미터로 넣을 수 있는 것을 안다면, 2~16진수 변환 로직을 구현하지 않아도 된다. 러프하게 잡은 max만큼 n진수로 변환한 문자열을 저장한 뒤, 튜브의 차례 (등차수열)에 해당하는 문자만 뽑아 UpperCase로 출력한다. class Solution { public String solution(int n, int t, int m, int p) { StringBuilder sb = new StringBuilder(); int num = 0; int max = t * m; whi..

https://school.programmers.co.kr/learn/courses/30/lessons/133500# 트리 그래프에서의 최소 지배 집합(minimum vertex cover)을 구하는 문제라고 한다. dfs + dp를 통해 구현했다.  1. dp 점화식 세우기 dp[node][1] = 현재 node가 on인 경우 최솟값= sum(child node가 root고 off인 모든 서브트리의 최솟값)= sum(dp[child][0]) dp[node][0] = 현재 node가 off인 경우 최솟값= sum( min(child node가 root고 off인 서브트리의 최솟값 , child node가 root고 on인 서브트리의 최솟값 ) ) + 현재 node를 on하는 값= sum( min(dp[c..