Meluu_의 코딩 공부 일지

K진수에서 소수개수 구하기

🧫 문제 분석✔️ 출처K진수에서 소수 개수 구하기 level 2📖 문제 간단한 문제인데 소수 판별 문제를 오랜만에 만나서 리마인드 겸 포스팅한다. 조건이 뭔가 4가지 경우를 다 체크해야할 것 같지만 그렇지 않다111011101110을 기준으로 진수를 나누면1가지의 조건식만 적용된다첫번째와 마지막은 각각 P0, 0P가운데는 무조건 0P0이 적용된다.이들을 하나하나 다 소수검증해준다. 문제에서 k진법으로가 아닌 10진법으로봤을때 소수여야한다고 되어있는데 이는211 일 경우 10진수 그대로 211이 소수이냐는 것이다.. 4번 조건 P의 경우 0을 기준으로 진수를 나눴을떄각 자릿수에 0이 하나도 없어야하므로 그대로 나온다.따라서 똑같이 적용하면된다. 🔅 문제 풀이import java.util.*;cla..

양국대회 [자바]

🧫 문제 분석✔️ 출처양국대회 level 2📖 문제 최대 점수이면서 가장 낮은 점수를 가장 많이 맞춘 스코어 배열을 만들어야하는 문제 최대 점수를 만들되 어피치가 가진 점수를 빼앗기 위해서는어피치가 맞춘 화살 개수보다 더 많이 맞춰야 해당 점수를 획득할 수 있다. 라이언이 각 점수를 화살로 맞추는 경우와 맞추지 않는 경우 2가지를 dfs로 탐색하여 풀었다.(최대 점수가 10점이기에 시간복잡도는 길어야 O(2^11)이다) 그리고 최대 점수를 갱신하고, 해당 점수를 얻은 화살 맞춘 스코어 배열을 list에 저장하면서 진행한다. 같은 점수라도 다 저장한다. 탐색이 끝나면 정답 후보를 탐색한다. 같은 점수인 정답 후보 중 가장 낮은 점수를 더 많이 획득한 경우를 구한다. 구한 정답 후보에서 안쏜 화살 개..

🧫 문제 분석✔️ 출처외벽 점검 level 3📖 문제 DFS로 풀려다가 for문으로 그리디하게 풀 수 있을것 같아 바꿔풀었다. 각 취약지점을 기준으로 시계방향으로 출발했을 때 걸리는 시간의 누적합을 구한다. 예시로 들자면1561004598015711043780 그 다음 for문으로 각 weak을 순회하면서 각 지점을 순차적으로 출발지점으로 정한다. 최소한의 인원으로 처리해야하므로 가장 많이 처리할 수 있는 친구부터 출발지점에서 처리할 수 있는 취약지점을 탐색한다.가장 많이 처리할 수 있는 친구는 문제에서 입력으로 dist에 오름차순으로 주어진다. 여기서 예시로는 마지막 친구가 4의 거리를 처리하고 현재 출발지점이 1 이므로, 5까지 처리가 가능하다. 구했다면 이제 해당 취약지점을 더 적은 이동거리를..

🧫 문제 분석✔️ 출처n+1 카드게임 level 3📖 문제 n/3 개의 카드를 뽑는다. (코인 소비 X) 종료 조건남은 카드 X, 카드 2장을 낼 수 없는 경우 일단 2장을 뽑고 뽑은 카드중 n+1을 만족하는 게 있다면 해당 카드가 처음에 뽑은 n/3개의 기본 카드 인지 확인한다. 기본 카드가 아니라면 현재 가지는 코인 - 뽑은 카드 개수 >= 0 인지 확인후 가능하다면 카드를 2내고 다음 라운드로 진행하면 된다. 🔅 문제 풀이import java.util.*;class Solution { public int solution(int coin, int[] cards) { int n = cards.length; int target = n + 1; int ..

🧫 문제 분석✔️ 출처 표현 가능한 이진트리 level 3 📖 문제 포화 이진트리를 만들고 중앙이 항상 해당 서브트리의 루트인 것을 이용한다.루트가 0일때 자식 노드가 1이면 불가능판정을 내리면 된다. 이진트리의 높이 공식은 2^h - 1 = Nh = Math.ceil(Log2(N + 1)); 이진트리 오랜만에 풀다보니 잘생각이 안나서 좀 고생했다. 🔅 문제 풀이import java.util.Arrays;class Solution { public int[] solution(long[] numbers) { int[] answer = new int[numbers.length]; for (int i = 0; i = e) return true; ..

🧫 문제 분석✔️ 출처주사위 고르기 level 3📖 문제 많은 공부가 된 문제다.. 문제 풀이 방법까지는 잘 도출했는데 정작 최대 5개를 뽑았을때주사위의 눈의 합을 구하는 법에서 막혔다. 문제는 너무 많은 생각이라고 생각한다. 나오는 모든 합에 대하여 카운트를 해주려다가 이건 또 너무 복잡하고머리가 잘 안돌아갔다. 이번에 알게된 것 N개의 조합의 모든 합 구하기dfs로 짜는 것 까진 했는데 정작 어떻게 더해야할지 감이 안잡혔다. 근데 그냥 하나하나씩 주사위를 건드리면 됐다.1번 주사위의 i번째 + 2번 주사위의 i번째.. 이런식으로 잘 기억해두자.. 이분 탐색최대 개수를 구할때는 size() 까지 해줘해한다는 것 처음에 탐색 범위를 0 ~size()-1 까지로 했는데12번 테스트 케이스가 계속..

🧫 문제 분석✔️ 출처부대 복귀 level 3📖 문제 최단경로인데 길이가 1이라해서 그냥 BFS로 풀었다.  몰랐던 사실인데 n이 10만이고, roads에서 모든 노드를 주지 않으므로, 메모리 낭비라고 생각해서 HashMap을 사용하는것이 좋아보인다고 생각해서 사용했다.  목적지 (destination)부터 끝노드까지 (탐색이 종료될때까지 ) 돌게 하되방문한 곳이 source[i] 면 거리값을 저장한다.   물론 다익스트라 알고리즘을 쓰는게 맞는것 같다. 내 로직보다 속도는 약 5배 정도 더 빠르다. 문제에서 최단 경로 라고 주어졌는데 비용이 1이라는 말에 BFS로 밀고 가려해서 저렇게 짠 것이다.   참고 HashMap은 해시 충돌을 대비한 내부 구조 (엔트리 배열, 체이닝 등)로 인해 메모리 오버..

🧫 문제 분석✔️ 출처연속 펄스 부분 수열의 합  level 3📖 문제 문제를 잘못 이해해서 삽질했다. 펄스 수열을 연속 수열에 패턴대로 곱했을때 최댓값이 나오는 연속 펄수 부분수열을 구하는 것이였다. 나는 잘못 이해해서 펄스 수열 처럼 수열의 연속 부분수열이 3,-6,1,-4 이런식으로 1,-1 이런 패턴이 유지되는 연속 부분 수열에만 펄스 부분 수열 1,-1을 곱해서 양수가 되는 것만 합쳐서 최댓값을 구했다. 당연히 틀렸고 이 문제는 사실 펄스 수열은 페이크고 누적합 문제이다.   주어진 수열에 펄스 수열 패턴을 곱해서 2개의 수열로 만든다.1,-1 패턴을 곱한 수열-1, 1 패턴을 곱한 수열 이제 누적합으로 풀면 된다.  나는 누적합 하면서 최댓값과 최솟값을 구하고  최댓값 - 최솟값을 하되 최..

🧫 문제 분석✔️ 출처섬 연결하기 level 3📖 문제 다익스트라로 했다가 생각해보니 이건 최단경로가 아닌 최소비용으로 연결하는 거였다.알고리즘 시간때 배웠던 걸로 기억하는데 최소신장트리 였던걸로 기억한다.  서로소 집합, 유니온, find 등 같은 걸 배웠었는데 기억이 안나서 결국 찾아봤다. https://sskl660.tistory.com/72 자세한 이론은 위 블로그 참조 핵심은 최소 비용으로 정렬하고 연결하는 두 노드(섬)의 부모가 서로 달라야한다. (사이클 방지, 최소 신장 '트리' 이기에 사이클은 없어야한다. )이때 find 메서드를 사용해서 각각 부모를 찾는다. 두 노드의 부모가 서로 다르다면 union 메서드를 사용해서 두 노드 중 부모가 더 작은 곳으로 편입된다. 이때 실제 원소가 편..

🧫 문제 분석✔️ 출처기지국 설치 level 3📖 문제 간단하면서도 생각할게 좀 있는 문제였다.N은 2억이므로 배열을 만들 생각은 하면 안된다.  stations가 최대 10만이므로 stations을 이용해서 푸는 문제이다.  나는 우선 처음 기지국의 전파범위와 처음 아파트 사이의 거리를 구하고 그 거리가 0이하가 아니라면 그 거리를 새로운 기지국을 설치했을때 전파범위로 나눈 값을 더했다.  그리고 기지국 사이에도 위와같이 연산을 해주고 마지막아파트와 마지막 기지국 사이의 거리도 동일하게 계산해주었다.   이번에 하면서 Math.ceil 과 직접 나누기와 나머지연산을 더하는 식으로 2가지로 해봤는데좋은 경험을 한 것 같다. - 664 / 667 을 연산했을 때 -0.9955 정도의 값이 된다.  Ma..