Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처길 찾기 게임 level 3📖 문제생각보다 재밌는 문제였다. 입력으로 노드의 좌표값만 주어지고 해당 조건에 맞게 이진트리를 만들어야하는데 최상위 루트 부터 시작해서 자식노드를 추가하는 식으로 생각했다. 따라서 y값을 기준으로 내림차순 정렬하고, 같다면 x값을 기준으로 오름차순 정렬한다. 좀 복잡한데 코드를 보면 그나마 이해가 된다. 자식을 추가할때 주의할 점은다른 노드가 자식으로 가져야할 노드를 자식노드로 설정하게 될 때도 있다.이를 방지하기 위해서는 추가가능한 범위를 지정해줘야한다. 즉, 각 서브트리의 범위 x의 범위를 지정해서 해당 범위 안에 든 노드라면 자식으로 추가하는 것이다.범위는 트리 구성 조건 5,6번을 참고하면 된다. 예시) 위와 같은 케이스가 발생할 수 있다..

🧫 문제 분석✔️ 출처[1차] 셔틀버스 level 3📖 문제 시간 문제콘이 셔틀을 타되 최대한 늦게 탈 수 있도록 하면된다. 같은 시각대에 타면 해당 시각대의 맨 마지막에 타게되는 점을 조심하면 된다. 각 회차별 시간대에 따라 탈 수 있는 인원들을 태우고현재 셔틀에 탄 인원이 다 같은 시각이면 (해당 시각 - 1분) 에 타고시각이 다 다르면 (제일 늦은 시각의 -1분)에 타면 된다. 🔅 문제 풀이import java.util.*;class Solution { // 도착 시간중 제일 늦은 시각 //같은 시각에 도착한 크루 중 대기열에서 제일 뒤 // 23:59분 전까지 public String solution(int n, int t, int m, String[] t..

🧫 문제 분석✔️ 출처보석 쇼핑 level 3📖 문제 투 포인터 문제로 모든 종류의 보석을 포함하는 가장 짧은 연속된구간을 찾는 문제다. 먼저 문제에서 보석의 종류의 개수를 알려주지 않으므로 따로 카운트한다.map 자료구조를 사용해서 현재 까지 구간에 어떤 보석이 몇개씩 있는지 저장하면서 체크한다. 현재 구간의 보석 종류 개수가 모든 보석의 종류 개수와 같다면구간 줄이기를 시도한다. 현재 앞쪽 포인터 (start)에 있는 보석이 map에서 개수가 1개면 오히려 구간을 늘려서 다음 탐색때 더 줄 일 가능성을 늘린다. 1개가 아니라면 s를 한칸 더 땡겨서 구간을 줄이는 식으로 풀어나간다. 테스트 케이스A B B C D As e처음에는 여기까지 탐색하고 map.size() == 모든 보석 종류 ..

🧫 문제 분석✔️ 출처다단계 칫솔 판매 level 3📖 문제seller가 판 이익의 10%을 계산자신이 90%을 먹고 자신의 추천인 즉, 부모에게 10%을 준다. 간단하게 자신의 부모를 가지는 배열을 생성하고판매금에 대한 이익 90%을 가지고 부모에게 10%을 줘서 처리하면된다. 여기서 간과한게 있는데 처음에는 그냥 판매자의 최종 판매액을 합산해서 한 번에 계산하는게 빠르지 않을까 싶었는데틀렸다. 생각해보니 문제에서 원단위 즉, 1원 미만은 절삭한다하였다. 홀수 금액의 경우 합산시 짝수가 될 수 있다. 즉 A, B 금액 둘다 홀수라서 1원 미만은 절삭될 수 있고 A+B를 합쳐서 계산시 짝수가 될 경우 위의 1원 미만 절삭이 사라져 오히려 더 큰 값이 분배될 가능성이 있다. 즉, 홀수 금액이 합..

🧫 문제 분석✔️ 출처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번 테스트 케이스가 계속..