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

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

🧫 문제 분석 ✔️ 출처내리막 길 골드 3 📖 문제 나의 가장 약한 부분인 DP 연습 기간을 잡아 DP문제를 풀어보려한다. DFS + DP로 풀었다.중복 탐색 방지를 위해 static으로 방문처리 배열을 만들어서 처리했다.약간 백트래킹 느낌으로 BFS + 우선순위 큐 풀이도 있다고 한다.생각해보면 탐색은 점점 높이가 낮은 곳으로 이동하므로 높이가 낮은 순으로 큐에 넣으면중복없이 풀어낼 수 있다는 것이다. 탐색 조건에 뭔가 우선순위를 매길 수 있다면 우선순위 큐를 떠올려 보자 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int N, M; static int[][] dp; static int[][] ..

🧫 문제 분석 ✔️ 출처사회망 서비스 (SNS) 골드 3 📖 문제 DP 문제트리를 이용한 DP 문제는 처음이라 좀 어려웠다 처음에는 엣지가 많은 노드 순으로 연결 해제 여부를 따지며 선정하면 되지않나 싶었는데불가능한 케이스가 있어서 바꿨다. 현재 노드를 얼리 아답터로 선정할지 안할지에 대해서 탐색하면된다.DFS+DP 식으로 풀어서 별로일 수 있다. 또한 입력을 받을 때 주의해야한다.방향성을 가지면 안되며 양방향으로 트리를 만들어야한다.그 이유는 단방향시 루트를 가지는 트리가 되는데 이러면 방향에 따라 값이 달라진다. 51 52 12 32 4이런 입력이 들어오면 1을 루트로 설정시2를 탐색할 수 없다. 때문에 양방향으로 설정해야한다. 루트를 1 기준으로 입력이 들어온다는 생각때문에이런 실수를 했다...

🧫 문제 분석 ✔️ 출처텀 프로젝트 골드 3 📖 문제 그래프 탐색을 하되 Stack + Set 조합으로 풀었다. 근데 DFS로 푸는게 정석인가보다. test case142 1 2 3answer : 2wrong : 무한루프 DFS로 다시 풀었을때 시간 초과가 났던 문제의 코드 private static void dfs(int current) { visited[current] = true; int next = students[current]; if (!visited[next]) { dfs(next); } else { if (finished[next]) return; // 이미 팀 구성을 한 학생이면 더이상 탐..

🧫 문제 분석✔️ 출처단어 변환 level 3📖 문제 begin 알파벳 중 하나를 words 단어중 하나의 알파벳으로 바꿀 수 있다.순서는 상관없고, 변경을 최소한으로 해서 target을 만들면 된다.   백트래킹하면서 words를 탐색한다.  words 각 단어의 알파벳을 begin의 각 알파벳과 비교해서 2개이상 다르면 바꾸지 않고 넘어가도록 한다.  만약 알파벳이 1개만 다르다면 그 단어를 begin으로 하고백트래킹 탐색을 한다. 🔅 문제 풀이class Solution { // 완전탐색 // 백트래킹 boolean[] visited; int min = Integer.MAX_VALUE; public int solution(String begin, Str..

🧫 문제 분석✔️ 출처소수 찾기 level 2📖 문제 numbers의 각 자릿수를 조합하여 숫자를 만들고 그 수가 소수인지 카운트  소수 판별 + 완전탐색 문제 핵심0으로 시작하지 않음2는 소수짝수는 소수가 아님조합된 수 중복 체크🔅 문제 풀이class Solution { boolean[] visited; boolean[] check = new boolean[10000000]; int answer = 0; public int solution(String numbers) { char[] num = numbers.toCharArray(); visited = new boolean[num.length]; dfs(..

🧫 문제 분석✔️ 출처모음사전 level 2📖 문제 정말 어려워했던 문제이다.결국에는 풀었다.  A : 1E : 2I : 3O : 4U : 5로 바꾸고  이에 맞춰서 완전탐색을 해서 매개변수로 넘어온 word 와 equals로 비교한 후 같다면 깊이 탐색을 멈추고 count를 반환한다. 🔅 문제 풀이class Solution { int count = 0; boolean flag = false; StringBuilder sb = new StringBuilder(); public int solution(String word) { dfs(trans(word), 0); return count; } private void dfs(Stri..

🧫 문제 분석 ✔️ 출처적록색약 골드 5 📖 문제 BFS 혹은 DFS 그래프 탐색 문제이다.나는 BFS를 좋아해서 BFS로 풀었다.  적록색약은 적록색(R) 과 초록색(G)의 차이를 거의 못느낀다.따라서 둘중 하나로 통일하면 된다.   나는 문제를 잘못 이해해서적록색과 초록색의 상화좌우로 인접해 있는 부분만 차이를 못느끼는 줄 알고 문제의 난이도를 더 높여서 풀다가 자꾸 틀리고 이상해서 문제를 다시봤더니 초록색과 적록색 차이가 없다고 보는게 맞았다...(이때문에 시간을 많이 소요함) 이 풀이법도 밑에 올리겠다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static boolean[][] visited; static i..