그리 어렵지 않은 문제라고 느껴져서 금방 풀 줄 알았는데 wires로 인접 행렬을 만드는 부분에서 조금 시간이 걸렸다. 1. 인접 행렬 만들기 2. 선 하나씩 끊으면서 bfs 탐색 으로 로직이 간단하다. 최종 코드 import java.util.LinkedList; import java.util.Queue; class Solution { static int[][] arr; public int solution(int n, int[][] wires) { int answer = Integer.MAX_VALUE; // 인접 행렬 만들기 arr = new int[n + 1][n + 1]; for (int i = 0; i < wires.length; i++) { arr[wires[i][0]][wires[i][1]]..

카카오 문제 치고 문제 설명이 짧아서 쉽게 풀 수 있을 줄 알았는데 꽤나 오래 걸렸다. 데이터 베이스를 공부한 지 오래되어서 후보키의 개념이 생각나지 않았지만 문제 설명을 보고 빠르게 이해했다. 처음에는 먼저 컬럼을 탐색해서 중복이 없다면 조합을 만드는 로직으로 생각했으나 그게 더 복잡한 것 같아서 모든 조합을 만들고 유일성과 최소성을 검사하는 로직으로 구현했다. 매끄럽게 풀었던 문제가 아니라서 조금 찝찝한 느낌이 있다. 기억이 나지 않을 때쯤 다시 풀어봐야겠다. 최종 코드 import java.util.*; class Solution { static int answer; static int n,m; static List candidateKey; static String[][] relationCopy; ..

문제는 L2에 맞지 않게 너무 쉬웠다. 재귀를 사용할수만 있다면 바로 풀리는 문제다. 원래는 str이 word와 같다면 메서드를 바로 종료하고 싶어서 밑과 같이 작성했지만 모든 사이클을 무조껀 돌아야 했다. if(word.equals(str)) { answer = cnt; return; } if(depth == 5) { return; } 그래서 그냥 모든 조합을 list에 넣고 선형 탐색으로 답을 구했다. 모든 조합을 다 해봐야 3600개쯤 밖에 안되니 시간 초과가 나진 않을 것 같았다. 최종 코드 import java.util.ArrayList; import java.util.List; class Solution { static String[] arr; static List list; public in..

골드 4 문제인데 정답률이 높아서 도전한 문제이다. DFS와 BFS 문제 심화 버전? 같은 느낌이었고 2시간 정도 걸렸다. 처음에는 벽을 세우는 로직에 대해서 고민을 했었다. 2를 기준으로 세우는 알고리즘과 1을 기준으로 세우는 알고리즘을 한참을 생각해봤지만 떠오르지 않았다. 시간제한이 2초이고 M이 8이하로 입력되니 그냥 모든 벽을 세우는 완전 탐색으로 진행했다. 1. 완전 탐색으로 모든 벽을 세워본다. 2. BFS로 바이러스를 퍼트린다. 3. 남아있는 0을 센다. 이렇게 로직을 작성했고 코드로 구현하는데 한시간정도 걸렸던 것 같다. 나머지 한시간은 연속적으로 메서드를 호출하는 과정에서 배열의 값이 꼬이는 걸 해결하는데 썼다. 3개의 메서드가 연속적으로 호출되는데 이렇게 구현한적은 처음이라서 시간이 오..

문제가 꽤 쉬운 편이었다. 특정 알고리즘을 사용하는 것도 아니라서 그냥 문제에 나온대로 코드로 구현했다. 처음에는 HashMap을 이용해서 한번 대진을 돌고나면 새로 번호를 부여하려고 했는데 다시 생각해보니 불필요할 것 같아서 메서드를 수정했다. 최종 코드 class Solution { public int solution(int n, int a, int b) { int answer = search(n, a, b); return answer; } // 대진 진행 메서드 static int search(int n, int a, int b) { int first = 0; int second = 0; // while문 탈출을 위한 a, b 대소 빅교 if (a > b) { first = b; second = a..

슬라이딩 윈도우를 사용하는 문제이다. 기본 개념만 알고 있다면 쉽게 풀 수 있는 문제라서 슬라이딩 윈도우 개념 복습 차원에서 풀어보았다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n =..

문제가 재밌어 보여서 선택했는데 하나도 재밌지 않았다. 규칙도 쉽게 보이고 재귀 호출로 n이 1일때 탈출하는것은 생각하기 쉬웠지만 막상 구현하려니 쉽지 않았다. 시간 제한이 1초라서 매번 println을 사용하면 100% 시간 초과가 난다고 생각해서 StringBuilder를 사용해서 찍어보려고 했는데 개행 문자 \n을 사용하면 별이 이상하게 찍혔다. 될듯 말듯 하다가 결국 검색을 해서 풀었는데 가장 이해하기 어려웠던 부분은 아래 부분이었다. if (!(i == 1 && j == 1)) { rec(x + i * (num / 3), y + j * (num / 3), num / 3); } x와 y의 좌표를 재귀때마다 수정해서 별을 찍는 로직인데 이해하는데 한참 걸렸다. 혼자서는 이렇게 생각하지는 못했을것 같..

카카오 문제답게 어려운 문제였다. 정확성은 통과하기 쉬웠으나 효율성을 통과하긴 어려웠다. 점수 배점이 정확성에 40점 효율성에 60점이니 효율성을 통과하지 못하면 0.5솔도 못하는 것이다. 처음에는 info와 query 배열로 들어온 정보들을 인스턴스로 만들어 하나씩 비교하려고 했다. info값이 50,000 이하, query값이 100,000 이하니 선형 탐색으로 둘을 비교할 시 시간 초과가 날것을 예상했지만 다른 방법이 떠오르지 않아 선형 탐색으로 풀었다. 인스턴스를 150,000개나 만들어 중첩 if문으로 탐색하는 코드를 만드니 메모리가 초과될 수도 있고... 애당초 비교를 위해서 인스턴스를 만드는게 아닌 것 같다는 생각을 했다. 메모리 초과는 일어나지 않았지만 효율성에서 통과하지 못했고 다른 방법..

예전에 풀었던 프로그래머스 거리두기 확인하기와 비슷하다고 느낀 문제였다. 이번 문제는 탐색보다 구현에 더 초점이 맞춰져 있던 것 같다. 요즘 코테를 보면서 느낀 코테 트렌트는 구현인 것 같다. 특정한 알고리즘을 알아야 풀 수 있는 문제도 몇 문제 있었지만 대부분이 구현 문제였다. 그래서 구현 문제를 중심으로 연습해야 할 것 같다. 문제를 읽고 이렇게 나누어 로직을 짰다. 1. 치킨 집중에서 m개를 선택해 조합 구하기 2. 구한 조합으로 각 집마다 치킨 거리 구하여 최솟값을 선택 3. 각 집에 최솟값을 더하여 도시의 치킨 거리 구하기 4. 모든 조합을 돌면서 도시의 치킨 거리의 최솟값을 반환 다만 이 로직이 맞는지 확신이 들지 않았지만 떠오르는 게 이 방법밖에 없어 코드로 구현했다. 구현하며 몇 번 막혔던..