엄지월드

문제 해석 - 주어진 숫자들을 그래프로 연결했을 때에, 각 숫자마다 부모가 누구인지를 구하는 문제이다. 처음에는 설명만 읽고나서 뭔소리인가 문제 해석에 시간이 좀 걸렸다. - 루트는 무조건 1부터 시작한다. 헷갈렸던 점 - 그래프를 어떻게 구성해야 하는가가 헷갈렸다. 배열로 풀려고 했으나, 인덱스가 늘어나면서 처리해주기 까다로워 리스트가 적당했다. 이 문제를 통해서 다시 한번 복습할 수 있는 계기가 되었다. - dfs를 어떻게 구성해야 할지 쉬울듯 안쉬울듯 자꾸 머리가 안굴러가서 애먹었다. 직접 메모장에 단계 별로 변수를 적어보면서 구성했다. - 다음 노드에서 이전 parent 노드로 다시 돌아가면 무한루프에 빠지게 되는데, 이 부분을 어떻게 처리해야 할지 고민을 좀 했다. 그래서 num != paren..

문제 접근 - 같은 알파벳을 만나지 않을 최대 경우의 수를 구하는 문제 - 탐색을 시작할 때에 hash.add를 해주고, 탐색을 완료했을 때에 hash.remove를 해주어 계속해서 누적되지 않도록 한다. (만약 누적되면 다른 방향으로 진행할 때에 이전에 탐색한 값 때문에 중복되어 탐색할 수가 없다) 헷갈렸던 부분 - visited 배열을 운영할 필요가 없었다. 왜냐하면 HashSet에서 같은 문자인지를 체크해주기 때문이다. - 탐색을 시작할때 add, 완료했을 때에 remove 해주는 부분을 for문 안에서 구현했었는데 오히려 복잡해져서 for문 밖으로 빼주었다. import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

문제 접근 - 8가지 방향으로 이동하는 문제이다. - DFS로 분류하고 문제를 선택한 것으로 인지 했었어서 어떻게 풀어야 하나 고민했다. 아무리 고민해 봐도 BFS 문제로 보여서 문제의 분류를 보니 BFS였다. 헷갈렸던 부분 - for문 안에서 이동 횟수를 1을 더해주니 여러번 움직였을 때에 cnt 출력 값은 맞았지만, 1번만 이동 했을 때에 cnt 출력 값은 0으로 나오는 문제가 있었다. 문제를 파악해보니, for문을 돌 때마다 People의 cnt 값을 더해주기 때문에 올바르지 못한 방법이었다. 그래서 고민한 결과 for문 위로 cnt 값을 빼주어서 해결하였다. - 오랫만에 BFS 풀었던 문제이다. 잊지 않도록 한번씩 리마인드 겸으로 풀어주면 좋을듯하다. import java.io.BufferedRe..

접근 방법 public static boolean dfs(int[][] map, int x, int y, int depth){ - DFS 진행 public static int simulation(int[][] map, int depth, int max) - depth 이하의 숫자들 침수 시키기 - depth max값까지 침수 되지 않은 영역들 모두 탐색 헷갈렸던 케이스 - if(!visited[j][k] && map[j][k] > i){ ... } 부분이 헷갈렸었다. 즉, 숫자 1개만 독립적으로 있는 경우를 잘못 count 해주고 있었다. 3 9 1 1 1 1 9 9 9 9 소스 import java.io.BufferedReader; import java.io.IOException; import java..

문제 설명 k개의 정수가 주어질 때에, 그 중 중앙 값을 찾는 문제이다. 만약 1, 3, -1이 있다면 1이 중앙 값이다. Input으로 nums 배열이 주어지고, Output으로 중앙 값을 출력해준다. 문제 접근 우선 순위 Queue를 2개 운영한다. - PriorityQueue lowerQueue = new PriorityQueue(Comparator.reverseOrder()); - PriorityQueue upperQueue = new PriorityQueue(); 단, 계속해서 중앙 값을 갱신해주기 위해서는 lowerQueue는 높은 숫자들을 빼주어야 하기 때문에 Comparator.reverseOrder()로 설정해준다. 그리고 나서 제거, 추가, 정렬 3단계로 진행되게 된다. 먼저 for문을..

기본 Trie 문제에서 약간 변형이 된 문제이다. 아이디어를 이해하면 풀 수 있을 것이다. 접근 방법 HashMap lengthMap 을 운영하여 각 단계 마다 뒤에 length가 몇개 있는지 확인 진행한다. lengthMap을 운영하면 fro??, fro???인 경우를 구분할 수 있다. 그렇기 때문에 Trie에 insert 시 아래와 같이 작성해주어 length의 갯수가 몇개 있는지 확인하고 1씩 더해준다. int len = str.length(); cur.lengthMap.put(len, cur.lengthMap.getOrDefault(len, 0) +1); search로 찾을 때에는 현재 찾고 있는 str의 length로 HashMap을 접근해준다. 만약, "??" 처럼 queries[]에 동일한 ..

접근 방법 BFS로 풀었던 것처럼, 각 영역마다 방문을 시작하지 않은 곳이 있으면 방문을 시작해준다. 이동 경로를 int[] dx, int[] dy로 선언하여 더해준다. 특이점 길찾기 문제를 DFS로 처음 풀어본 문제. 이동 방향이 4가지가 아닌 대각선까지 포함하여 8가지이다. while문 안에 while문을 통해서 방문하지 않은 곳들을 찾아주려 했었다. 하지만 다시 생각해 보면, DFS를 통해서 나오는 시점에는 모두 탐색을 했기 때문에 while문으로 다시 체크해 줄 필요가 없었다. 그리고 isAllVisited 탈출 코드도 추가해 주다 보니 더 복잡해지게 되었다. package Baekjoon; import java.io.BufferedReader; import java.io.IOException; ..

접근 방법 불과 사람을 1번씩 움직여주면서 탈출이 가능한지 찾아본다. 불과 사람이 만나면 실패이기 때문에, while문에서 사람보다 불을 먼저 이동해준다. 특이점 visited 배열을 사람과 불을 각각 운영해주려고 했으나, 함께 운영해주어도 문제가 없다. 왜냐하면 어차피 불이 이동한 곳은 사람이 이동하지 못하고, 사람이 이동했던 경로를 불이 이동할 필요는 없기 때문이다. 로직은 맞는 것 같은데 시간초과가 나서 계속 분석해 보니.. for(int k = 0; k < qSize; k++) { 부분에서 for 문안에 Man now = q.poll(); 을 포함했어야 했는데, for 문 위에 Man now = q.poll();이 있어서 계속해서 시간초과가 발생했었다. 이유는 사람의 개수대로 for 문이 돌아야 ..

접근 방법 dx 배열에 이동 경로를 입력 int[] dx = new int[]{-1, 1, 2} BFS 문제와 동일하게 Queue에 값을 넣어서 계속해서 알까기 진행 People class를 운영하여 걸린 시간을 계속해서 더해주었다. -> People class 선언 시, static으로 하지 않으면 에러가 나서 static으로 선언해 주었다. 특이점 기존에 BFS 문제들과 비교했을 때에 좌표가 아닌점이 신선했다. visited를 운영하지 않았더니 시간초과가 발생했다. visited 배열의 크기를 x,y 중에 큰 값으로 했더니, 10 19와 같이 x2후에 -1을 하는 케이스에서 오류가 발생해서 입력 범위의 전체로 늘려주었다. visited = new boolean[1000001]; 원래 continue를..

접근 방법 전체 배열을 탐색하여 BFS 시작 전에, 1이 포함된 위치를 Queue에 모두 넣어준다. (ArrayList arr = new ArrayList();) BFS 탐색 시, 범위를 벗어나지 않거나, 방문하지 않았거나, 0인 부분을 계속해서 탐색해준다. 특이점 기본 BFS는 0(벽)일때 continue를 해주지만, 해당 문제는 num이 여러개 일 수 있기 때문에 다른 num을 침범하지 않기 위해 if(map[nextX][nextY] != 0) continue; 처리해준다. 이동한 부분에서 max 값을 찾기 위해 계속해서 갱신해준다. max = Math.max(max, map[nextX][nextY]); package Baekjoon; import java.io.BufferedReader; impor..