Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처광물 캐기 level 2📖 문제 백트래킹 문제로 곡괭이의 내구도 :  5한 번 선택한 곡괭이는 터질때까지 사용광물은 주어진 순서대로 채광 종료 조건은 모든 곡괭이 내구도 0 이거나 모든 광물을 채광했을 경우 이다.이때 최소 필요도를 구하는 것이 이 문제의 답이다.  곡괭이 하나 선택하고, 최대 5개 캐고 하면서 백트래킹 하면 된다. 🔅 문제 풀이class Solution { // 0 : 다이아, 1 : 철 , 2: 돌 int[][] fatigue = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}}; int minFatigue = Integer.MAX_VALUE; public int solution(int[] picks, String[]..

🧫 문제 분석✔️ 출처연속된 부분 수열의 합 level 2📖 문제 비 내림차순 정렬 : 오름차순 정렬 흔한 투 포인터 문제이다. 투 포인터로 값을 합산하고 k와 비교하여 크다면 앞 포인터를 움직이고 그만큼 빼고,작다면 뒤 포인터를 움직이고 그만큼 더한다. 짧은 길이의 수열 인덱스만 갖는 배열을 준비한다. 배열의 길이가 100만까지니까 1000001 까지 해서 최댓값으로 초기에 설정한다.  투 포인터의 합계가 k와 같다면 앞 포인터 인덱스 - 뒤 포인터 인덱스 한 값이 짧은 길이의 수열 인덱스 배열과 비교하여 가장 짧은지 확인하는데 같다면 넘어가고, 더 짧다면 갱신해주면된다. 자세한건 코드를 참조    🔅 문제 풀이class Solution { // 투 포인터 문제 예상 // 연속된 부분 ..

🧫 문제 분석✔️ 출처두 원 사이의 정수 쌍 level 2📖 문제 많이 틀렸고, 질문도 보면서 참고하면서 풀었다.  처음에는 규칙이 있나 해서 규칙을 찾아서 해봤는데 그건 작은 값이였을때만이여서 의미 없었고,임의의 좌표를 생성하고 그 좌표까지의 거리가 r1보다 크면서 r2 보다 작은 것을 찾는 방식을 했는데 당연히 O(n^2) 라서 안된다.   핵심은 두원의 특정 x값일 때 두 원의 y값 사이를 구하는 것이다. (혹은 특정 y값일 대 두원 사이의 x값)  중요한 것은 r2의 경우 r2의 y값을 내림처리하고r1의 y값을 올림 처리해야한다.  x =1 일때 뿐만 아니라 그외에도 원의 방정식에서 x값을 넣어 구한 해당 원의 y값은 x = 0, y = 0 일때를 제외하고는 해당 원의 반지름보다 작다. r2를..

🧫 문제 분석✔️ 출처요격시스템 level 2📖 문제 핵심은 A 나라의 폭격 미사일을 모두 요격하면서, 요격 미사일 개수가 최소가 되게하는 것이다.최소한의 비용으로 최대한의 효율 즉, 탐욕법이라고 볼 수 있다. 또한 요격 미사일은 개구간 (s, e)에서 s, e위치에서 요격 미사일로 요격 불가능하다. 제한사항을 보면 0부터 1억까지 s와 e가 분포되어있기에 단순히 미사일이 지나간 좌표를 배열로 만들어서 카운트하는 것은 불가능하다는 것을 알 것이다.  그렇다면 참고해볼 것은 targets의 길이가 50만이라는 점이다. 뭔가 배열 정렬, 혹은 탐색 등으로 문제 풀이를 생각해보는 것이다.  필자는 고민해보다가 A나라의 폭격 미사일들을 s(시작 좌표)로 정렬그리고 하나의 폭격 미사일의 범위에 대해서 다른 미..

🧫 문제 분석✔️ 출처스킬트리 level 2📖 문제 skill 매개변수에는 스킬 순서가 담겨있고 skill_trees는 각 스킬트리들이 담겨있다.  여기서 핵심은 스킬순서에 있는 모든 스킬이 다 스킬트리에 있을 필요 없고 스킬 순서만 맞으면 가능한 스킬트리라는 것이다. 🔅 문제 풀이import java.util.*;class Solution { public int solution(String skill, String[] skill_trees) { HashMap map = new HashMap(); int answer = 0, rightSequence = 0; // 맵 초기화 for (int i = 0; i    처음에는 스킬순서에..

🧫 문제 분석✔️ 출처행렬의 곱셈 level 2📖 문제arr1 x arr2 = arr3axn * nxb = axb인 행렬이 생긴다.🔅 문제 풀이class Solution { public int[][] solution(int[][] arr1, int[][] arr2) { int[][] answer = new int[arr1.length][arr2[0].length]; for (int i = 0; i arr1 = [[1,2],[7,8]] arr2 =[[3,5],[4,6]]answer[i][j] = Carr1[i][k] = [1,2]arr2[k][j] = [3][4]i는 answer와 arr1의 행을 가리킨다.j는 arr2의 열을 가리킨다. [1,2] 가 1열..

🧫 문제 분석✔️ 출처n^2 배열 자르기 level 2📖 문제nxn크기의 2차원 배열을 i행 i열에 i 값을 넣는다.123223333이런식으로그다음 각 행을 모두 이어붙이고 left~right까지만 배열로 반환🔅 문제 풀이class Solution { public int[] solution(int n, long left, long right) { int[] answer = new int[(int)(right-left+1)]; for (int i = 0; i 1차시도때 2차원 배열 만들고 값을 하나씩 넣은다음 그 중에서 left~right 배열을 반환하려 했으나 보면 알겠지만 n의 값이 최대 10^7이고 right - left 는 10^5 미만이다. 2차원..

🧫 문제 분석✔️ 출처H-Index level 2📖 문제 문제를 잘 못 이해해서 삽질했다.n편 중 h 번 이상 인용된 논문이 h편 이상이고,나머지 논문은 개수에 상관없이 h 번 이하 인용되었다면 h의 최댓값이 H-Index이다. 🔅 문제 풀이import java.util.Arrays;class Solution { public int solution(int[] citations) { Arrays.sort(citations); int max = 0; // i = 논문 인용 횟수 for (int i = 0; i 흠.. 느리다.프로그래머스 좋아요 1등 풀이import java.util.*;class Solution { public ..

🧫 문제 분석✔️ 출처영어 끝말잇기 level 2📖 문제 핵심말 그대로 끝말잇기이며 앞 뒤 문자가 이어지는 지 확인중복 단어 불가🔅 문제 풀이import java.util.*;class Solution { // 1번 부터 순서대로 한사람씩 단어 // 마지막 다음 1번부터 다시시작 // 마지막 문자로 시작하는 단어 // 중복 단어 불가 // 한 글자 불가 public int[] solution(int n, String[] words) { Map map = new HashMap(); char lastWord = words[0].charAt(0); for (int i = 0; i 다른사람풀이를 보며난 왜 M..

🧫 문제 분석✔️ 출처카펫 level 2📖 문제핵심가로 길이 >= 세로길이가로 세로 길이를 구하되 갈색과 노란색의 개수가 맞아야함🔅 문제 풀이좀 이상하게 풀었는데우선 가로 세로를 찾기위해 약수를 구한다. 약수가 가로 세로가 된다.약수를 check 메서드에 넘긴다.check 메서드는가로가 위아래로 2개 있으므로 가로 길이 x 2를 해준 다음 전체 갈색개수에서 빼준다.이를 2로 나누면 사각형에서 양 옆의 개수가 된다.위 예시와 같이 4 / 2 = 2 세로 옆구리가 2다.이 값이 매개변수로 넘어온 약수로 찾은 가로세로중 세로 길이 - 2 한 값보다 작거나 같으면정상적으로 사각형이 성립된다.만약 옆구리가 2 고 약수로 찾은 세로가 1이면 갈색이 1 남는다.. 이러면 아닌 것이다.class Solution ..