전형적인 DFS / BFS 문제였다. 구현은 쉬웠는데 계속 통과가 안돼서 30분을 넘게 봐도 이상한 점을 못 찾았는데 전역 변수 사용 시 메서드 내에서 초기화를 해야 통과한다. 최종 코드 class Solution { static int numberOfArea; static int maxSizeOfOneArea; static int cnt = 0; static int[] dx = {1,-1,0,0}; static int[] dy = {0,0,1,-1}; public int[] solution(int m, int n, int[][] picture) { numberOfArea =0; maxSizeOfOneArea=0; int[] answer = new int[2]; answer[0] = numberOfAre..

2020 카카오 인턴쉽 문제로 근래에 풀어본 문제 중 가장 어려웠다. 첫 구현까지는 1시간 30분 정도 걸렸고.... 모든 케이스를 맞추기까지는 3시간이 걸렸다... 한 번에 로직을 짜기도 쉽지 않고 List값을 삭제하면 List의 사이즈가 계속 달라지는데 이를 어떻게 처리할지 대부분의 시간을 쏟았다. 또, 아무 생각 없이 변수들을 int로 만들어서 테스트 케이스에서 계속 70점을 받았는데 이를 long으로 고치니 결국 모두 통과되었다. 시작부터 long answer = 0이라는 힌트도 있었고 문제에 중간 계산 값이 2^63이라는 것도 쓰여있었는데 계속 실수하는 것 같다. 모든 연산자 배열을 나는 직접 입력했지만, 다른분들은 순열을 이용해서 배열을 생성했다. 확장성을 고려한다면 이 방법이 맞다고 생각이 ..

문제 설명이 좀.. .길다... 그냥 위에는 읽지않고 입출력 부분만 보고 풀었다. Map을 사용하면 간단하게 풀수 있는 문제이다. 다만 이 문제도 n과 m이 100,000까지 들어올 수 있어서 시간초과가 날수있다. 처음에는 HashMap을 하나만 생성해서 숫자가 입력되면 key값으로 value를 찾고 문자면 keySet을 반환해서 value로 key를 찾았다. 다만 keySet으로 반환해서 탐색하는 시간이 걸려서 시간 초과가 났다. 그래서 그냥 HashMap을 2개 생성해서 풀었다. 실패 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringToken..

간단한 문제라고 생각했는데 의외로 20분이 넘게 걸렸다. 처음에 아무 생각 없이 ArrayList를 사용해서 각 list에 입력값을 넣어주고 2중 for문을 돌리며 비교했다가 4%에서 바로 시간 초과가 나왔다. 시간제한이 2초인데 왜 시간 초과가 나지? 하고 문제를 다시 보니 N과 M이 각각 500,000 이하의 자연수였다.... 그래서 이중 for문을 없애고 retainAll을 사용해서 교집합을 구했지만 또 시간 초과... 생각해보니 List는 탐색 시간이 오래 걸린다는 단점이 생각이 났고 그때가 되어서야 set이 생각났다. 또 문제에 입력값이 중복이 없다 라는 힌트가 있었는데 눈치채지 못했었다. 정렬이 되는 TreeSet을 이용해서 문제를 풀어 맞았다. 그런데 다른 분들의 답을 보니 입력을 n만큼 H..

가장 빠른 시간이라는 문장에서 BFS를 사용해야겠다는 생각을 했다. 다만 어떤 식으로 BFS를 사용해야 하는지 모르겠어서 검색을 통해 다른 분들 답안을 참고했다. visited 배열을 사용해서 방문처리와 이동 횟수를 카운팅 하는 방법을 사용해서 풀었다. 어려운 문제라는 생각은 안들었지만 BFS에 아직도 익숙하지 않은 것 같아 계속 연습해야 할 것 같다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int n, m, cnt;..

7576 문제에서 높이인 H값이 추가된 문제이다. x,y 값에 z값까지 더해 탐색하면 된다. 3차원 배열을 생성해 입력값을 배열에 넣어주었고 dz 배열을 생성해 상하좌우앞뒤를 모두 탐색할수 있게 했다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int m, n, h; static int arr[][][]; static int[] dx = {1,-1,0,0,0,0}; static int[] dy = {0,0,1,-1,0,0..

전형적인 BFS 문제라고 생각했다. 그러나 푸는데 정말 시간이 오래 걸렸다. 처음에는 입력값을 배열에 넣고 1을 발견할 때마다 bfs를 실행시키려고 했다. 그런데 밑에 테스트 케이스를 만나면 6이 아닌 9를 반환하게 된다. 6 4 1 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 1 문제에서 요구하는 방향은 모든 익은 토마토에서 하루가 지날 때마다 주변에 토마토가 익는 방식인데 나는 첫번째 익은 토마토를 발견하면 bfs를 실행시키고 또 다른 익은 토마토를 발견하면 또 bfs를 실행시켜 결국 똑같은 값이 두 번 출력되는 것이었다. 그래서 bfs에 넘기는 입력값을 List로 설정해 모든 익은 토마토 인덱스를 한 번에 bfs 메서드에 넘겨주었다. 큐에 모든 익은 토마토의..

처음에는 이 문제를 어떻게 풀어야 할지 전혀 감을 못 잡았다. 한참을 생각해도 답이 안 나와서 다른 분들 풀이를 참조했다. DP를 이용하는 문제였는데, 점화식도 생각보다 복잡해서 이해하는데 한참 걸렸다. 코드 자체는 어렵지 않으나 dp[i] = min(dp[i - j * j]) + 1 이라는 점화식을 생각하는 부분이 가장 어려웠던 것 같다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamRea..

우선순위 큐를 만들고 내림차순으로 정렬해주면 된다. 저번에 풀었던 최소 힙이랑 비슷한 문제였다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); // 우선순위 큐 내림차순 정렬 ..