본문 바로가기

전체 글

 (239)
DFS 참고한 영상 DFS 위키백과 깊이 우선 탐색(Depth-First Search) 최대한 깊은 단계까지 우선 검색하는 방법. 구현방법으론 스택과 재귀식 구현이 있음. 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다. 영상 보면서 직접 ..
01 Matrix 각 블록에서 가장 가까운 0을 찾는 문제. 자신이 0이면 그 블록에 값은 0이고, 옆에 있으면 1이 됨. 블록은 상하좌우로만 움직임. 처음 문제를 봤을 때 구현 문제가 생각났음. 처음 블록에서 주변 상하좌우를 확인한 후, 없으면 상,하,좌,우 이동한다. 그 다음에 다시 상,하,좌,우에 0이 있나 확인. 접근 방법은 생각났는데 코드 구현을 못해서 계속 헤메다가 BFS가 떠올라서 BFS 검색해서 어설프게 구현했음. 제일 헤멨던 게 x,y좌표 구분에서 엄청 헤멨음. x,y를 명확하게 뭐라고 확실히 정하고 하지 않아서 굉장히 고생함. 다음에 좌표 문제가 나오면 x,y 확실히 정하고 풀어야겠음. 다음엔 밑에 2가지를 신경 써서 풀어야겠음. 1. BFS 제대로 구현 2.x,y 좌표 명확하게 잡기. 푼 거. impo..
Minimum Number of Operations to Move All Balls to Each Box 처음 생각한 답. import java.util.HashSet; import java.util.Set; class Solution { public int[] minOperations(String boxes) { int[] answer = new int[boxes.length()]; Set set = new HashSet(); int boxLength = boxes.length(); for (int i = 0; i < boxLength; i++) { if (boxes.charAt(i) == '1') { set.add(i); } } for (int i = 0; i < boxLength; i++) { int count = 0; for (int j : set) { count += Math.abs(i-j); } ..
Find the Winner of the Circular Game 시계 방향으로 원에 n만큼 사람이 있음. 처음 인덱스에서 시작해서 k번째 인덱스를 삭제함. 삭제한 인덱스에서 k번째 사람을 또 삭제함. 1명 남을 때까지 반복. 답지 보기 전에 짠 코드 import java.util.ArrayList; import java.util.List; class Solution { public int findTheWinner(int n, int k) { List list = new ArrayList(); //요소들을 담을 리스트. for (int i = 1; i 1) { //인덱스에 증가값을 더해줌. (자기 자신부터 세므로 -1함) index += cycle-1; //인덱스가 list보다 크면 리스트를 한 바퀴 이상 돈 것임. if (index >= list.size()) { /..
Minimum Subsequence in Non-Increasing Order 배열에서 숫자를 뽑아서 리스트를 만들었을 때 뽑은 숫자는 배열에서 사라진다. 리스트의 총합이 배열의 총합보다 커지는 경우를 구하시오. 단, 답이 여러개면 최소 값을 구하시오. 답지 보기 전에 푼 거. import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public List minSubsequence(int[] nums) { //주어진 배열 int[] array = nums; //배열의 원소들을 크기 순서대로 정렬 Arrays.sort(array); //배열의 총합을 arraySum의 대입 int arraySum = Arrays.stream(array).sum(); //숫자를 뽑아서 저장할 리..
Number Of Rectangles That Can Form The Largest Square 문제 링크 주어진 사각형을 자를 수만 있을 때 최대 넓이인 정사각형의 갯수를 구하라. 접근법 : 사각형의 길이를 늘릴 순 없고 자를 수만 있으므로 최소 길이인 변의 길이로 자른 게 해당 사각형의 최대 넓이임. 즉, 사각형이 있으면 최소 변의 길이를 구합니다. 그 변의 길이가 사각형 중에서 제일 큰 사각형이 우리가 구하고자하는 사각형입니다. 해당하는 정사각형과 넓이가 같은 사각형의 갯수를 구합니다. 내가 푼 방법 class Solution { public int countGoodRectangles(int[][] rectangles) { int answer = 0; //최대 넓이를 가진 도형의 갯수. int max = 0; //최대 넓이 도형 길이. for (int i = 0; i < rectangles.l..
Split a String in Balanced Strings 문제 링크 리트코드에서 본 모법답안 public int balancedStringSplit(String s) { int res = 0, cnt = 0; //res는 나눠질 수 있는 갯수, cnt는 L이 있으면 ++, R이면 --. for (int i = 0; i < s.length(); ++i) { cnt += s.charAt(i) == 'L' ? 1 : -1; if (cnt == 0) ++res; //cnt가 0인 경우는 R과 L의 갯수가 같은 경우, 즉 나줘질 수 있을 때 밖에 없음. } return res; } 위 코드의 경우, 갯수를 초기화 할 필요도 없고 변수를 두개나 할 필요도 없음. 답지 보기 전에 푼 거. class Solution { public int balancedStringSplit..

티스토리툴바