Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처숫자 변환하기 level 2📖 문제 간단하지만 생각해볼게 좀 있는 문제최단경로 BFS로 풀어보자고 생각했다. 핵심x == y 일때,x로 y를 만들 수 없을때 bfs 탐색을 멈추는 조건중복 탐색 방지 (시간 초과 가능성)🔅 문제 풀이import java.util.Queue;import java.util.LinkedList;class Solution { // x -> y // x + n || x * 2 || x * 3 //bfs 최단 경로 boolean[] visited = new boolean[1000001]; public int solution(int x, int y, int n) { int answer = bfs(x,y,..

🧫 문제 분석✔️ 출처택배상자 level 2📖 문제 메인 컨테이너 벨트는 1부터 n까지 순서대로 한쪽 방향으로 내려옴보조 컨테이너 벨트는 stack구조, LIFO  주어진 입출력(order)의 요소들을 순서이면서 택배상자 번호라고 가정하고 풀이한다. 1. order[i]의 택배상자 번호 전까지 메인 벨트의 상자를 보조 컨테이너 벨트에 넣는다.2. order[i]의 택배상자 번호와 현재 메인 벨트 상자의 번호가 같은지 확인한다.3. order[i]의 택배상자 번호와 보조 벨트의 입구쪽 상자의 번호가 같은지 확인한다. 4. 2,3 번 둘다 아니라면 더이상 실을 수 없으므로 종료한다. 5. 이를 order의 모든 상자수만큼 반복한다.  🔅 문제 풀이import java.util.Stack;class So..

🧫 문제 분석✔️ 출처뒤에 있는 큰 수 찾기 level 2📖 문제 스택 구조를 써야될거같은 느낌이 든다.  스택이 비어있다면 숫자를 넣는다.  스택이 비어있지 않다면 1. 스택의 TOP 원소와 현재 숫자를 비교해서 더 크다면 그 수가 뒷 큰 수 이다.2. TOP원소를 꺼내서 numbers에 있었던 당시 인덱스를 answer 배열의 인덱스에서 뒷 큰 수를 넣어준다.이를  1번이 false일 때까지 반복한다. 마지막으로 스택에 남은 뒷 큰 수가 없는 숫자들은 -1로 처리해준다. 🔅 문제 풀이 import java.util.Stack;class Solution { // 스택을 이용 // idx를 함께 저장 // 스택 top 원소 뒷 큰수 넣고, pop() public int[] s..

🧫 문제 분석✔️ 출처혼자서 하는 틱택토 level 2📖 문제 단순 구현 문제인듯 하다. 간단하다. 머쓱이가 잘못 둔것과 별개로 그저 현재 주어진 게임판이 나올수 있는 게임 상황인지 아닌지만 판단하면 된다.  내가 생각했을 때 나올 수 없는 상황을 생각해봤다.  나올 수 없는 상황O의 개수 - 2 >= X 개수 O의 개수 O가 빙고했는데 X의 개수가 O와 같거나 클때X가 빙고했는데 O의 개수가 클때O 빙고가 우선권을 가짐 (O 빙고와 X빙고 둘다 있을 경우)  처음 O와 X의 개수를 구하고 위 2가지 경우에 대해서 체크한다음 이상이 없다면가로, 세로, 대각선 빙고를 체크해서 아래 2가지 경우에 대해서 체크한다.  🔅 문제 풀이class Solution { // 나올 수 없는 상황 // O..

🧫 문제 분석✔️ 출처연속된 부분 수열의 합 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차원..