Meluu_의 코딩 공부 일지

모두 0으로 만들기 [자바]

🧫 문제 분석✔️ 출처모두 0으로 만들기 level 3📖 문제 dfs로 푸니 메모리 제한사항이 빡빡해서 6,7번에서 런타임 예외 (stackoverflow)가 터졌다.변수를 static으로 선언, iterator를 사용하지 않는 일반for문 사용 우선 트리에서 가중치가 가장 작은 노드를 기준으로DFS 탐색해서 리프노드부터 값을 넘기면서 연산 횟수를 카운팅하면된다. 그리고 특정 상황 즉, 모두 0이거나, 불가능한 경우는 미리 처리한다. a의 모든 합이 0이 아니면 절대로 모든 정점의 가중치를 0으로 만들 수 없으므로 바로 -1 반환 a의 모든 요소가 0이면 0 반환 재귀를 통한 dfs 말고 stack으로 dfs를 구현하면 더 안정적일 것 같다. 🔅 문제 풀이import java.util.*;cla..

봉인된 주문 [자바]

🧫 문제 분석✔️ 출처봉인된 주문 level 3📖 문제 설계는 잘했는데 구현이 조금 어려웠다. 1. 일단 bans을 무시하고 전체 주문서를 규칙순서대로 뒀을때 n번째 주문서를 찾는다.2. n번째 주문서보다 사전 순서가 앞서는 bans 주문서가 있다면 개수를 카운트한다.3. 2번에서 카운트한 개수만큼 n = n + cnt로 갱신하고 다시 2번을 진행한다.4. 카운트가 0이라면 ban을 모두 적용한 n번째 주문서이므로 반환한다. 예시에서 30번째 주문서를 찾는데ban을 적용하지 않고 주문서를 규칙에 따라 정렬했을 때 30번째는 "ad" 이다.그런데 그 중에 ban 문자 d, e, aa, ae 가 있으므로 이 문자들은 건너뛰고 순서를 할당했을 것이다.ban을 적용하면 해당 4개의 문자만 넘어가면되니 n +..

조건에 맞는 사용자 정보 조회하기 [MYSQL]

🧫 문제 분석✔️ 출처조건에 맞는 사용자 정보 조회하기📖 문제 살짝 고민했던 SQL문제 매우 재밌고 흥미롭다.첫 번째로 중고 거래 게시물을 3건 이상 등록한 사용자를 필터링해야한다.서브 쿼리로 작성자 ID 를 그룹핑후 HAVING절에서 COUNT로 작성 글이 3개 이상인 WRITER_ID를 구한다. IN절로 서브쿼리에서 구한 WRITER_ID 중에서 중고 거래 이용자의 ID값이 있다면,해당 유저는 중고 거래 게시글을 3건 이상 등록한 사용자이다. 이부분만 잘 파악하면 쉽게 해결 가능하다. 🔅 문제 풀이-- UGB 와 UGU 테이블에서 중고 거래 게시물을 3건 이상 등록한 사용자의 사용자ID, 닉네임, 전체 주소, 전화번호를 조회-- 전체 주소는 시, 도로명 주소, 상세 주소가 함께 출력-- 전화번..

🧫 문제 분석✔️ 출처최적의 행렬 곱셈 level 3📖 문제 DP로 풀은 문제행렬의 곱을 복습하자면 A(3X5) 와 B(5X7)의 크기의 행렬이 있을때 구 행렬을 곱하면AB = 3X5X7 이된다. 행렬 A, B, C... 이렇게 있을 때ABCD를 만드는 조합은ABC DAB CDA BCD 이렇게 3가지 가 있고ABCDE는 A BCDEAB CDEABC DEABCD E4가지가 있다 여기서 규칙성을 찾을 수 있고 이를 점화식으로 나타낼 수 있다.시작과 끝을 지정하고, 중간을 지정해서 분할한 후 최소값을 찾는 것이다.// A: s,mid까지 곱한 행렬의 행 크기, B: mid+1,e 까지 곱한 행렬의 열 크기DP[s][e] = min(DP[s][mid] + DP[mid+1][e] + multiply(A..

🧫 문제 분석✔️ 출처2차원 동전 뒤집기 level 3📖 문제 DFS 로 풀었지만 정석은 bitmask인듯하다. 행 기준으로 현재 행을 뒤집는 경우와 뒤집지 않는 경우를 탐색하여 뒤집는 행을 갖는 조합을 만들고 열 기준으로도 조합을 만들어서 최종적으로 조합을 적용해 동전들을 뒤집고, target과 비교해서 맞다면 뒤집기 카운트와 비교해서 최솟값을 찾는다. 이문제를 풀면서행과 열을 왔다갔다하면서 뒤집어야 나올 수 있는 target이 있을 줄 알았는데 그게 아니였다. 궁금해서 gpt 에게 물어봤다.begin[i][j] ^ R[i] ^ C[j] == target[i][j] 🔅 문제 풀이import java.util.*;class Solution { static int[][] otarg..

🧫 문제 분석✔️ 출처길 찾기 게임 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📖 문제 우선순위 큐를 이용한 시간 관련 문제 입력이 요청 시간 순으로 들어오는게 아니라서 요청 시간별로 정렬해주고우선순위 큐는 문제에서 말한대로 정렬해준다. 현재 시간에 요청된 작업이 있다면 우선순위 큐에 넣고 작업을 꺼내서 처리한다. 만약 작업이 없다면, 즉, 현재 시간까지 요청된 작업이 없다면 현재 작업 인덱스의 작업 요청 시간으로 현재시간을 변경한다. 🔅 문제 풀이import java.util.*;class Solution { class Job { int num, req, cost; public Job(int num, int req, int cost) { this.num..

🧫 문제 분석✔️ 출처여행경로 level 3📖 문제 모든 경로를 탐색해서 사전순으로 앞서는지 확인하는 문제 간과한 것은 같은 경로가 여러개 있을 수 있다는 것이다. ICN -> SFO, ICN -> SFO 이렇게 같은 경로가 여러개로 입력될 경우가 있다. 문제에서 따로 중복에 대한 내용이 없으면 항상 중복 케이스가 있다고 생각하는게 좋다. 그렇다면 어떻게 문자열로 된 그래프에서 방문처리를 할까 나의 경우 (현재 공항 + 다음 공항의 idx )를 key값으로 사용하여Set에서 방문처리를 하였다. 이부분만 빼면 딱히 어려운 문제는 아니다. 🔅 문제 풀이import java.util.*;class Solution { static Map> graph; static int n; // 총 방..

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