[알고리즘] JAVA 코테 정리 - 자료구조 편
급하게 정리해보자 기본이라도
급하게 공부하면서 쓴거라 가독성 좋지 못함 주의,,,
- import java.util.*;
문자열 정렬 - 로그파일 재정렬
https://leetcode.com/problems/reorder-data-in-log-files/
기억할 포인트
- arrayList를 array로 반환할때
-> letterList.toArray(new String[0]);
- 정렬할때 람다 (추가 로직이 필요해서)
-> letterList.sort((o1, o2) -> {
<여기서 정렬하기>;
});
- Compare 로직
스플릿 하고
int compare = split1[1].compareTo(split2[1]);
여기서 같으면 0
크면 1
작으면 -1
그냥 return compare 하면 정렬이 되는데
s1, s2로 받은 인자를
s1.compareTo(s2)-> 이렇게 하면 오름차순
s2.compareTo(s1) -> 이렇게 하면 내림차순
class Solution {
public String[] reorderLogFiles(String[] logs) {
List<String> letterList = new ArrayList<>();
List<String> digitList = new ArrayList<>();
for(String log: logs){
String splitted = log.split(" ", 2)[1];
if(Character.isDigit(splitted.charAt(0))){
digitList.add(log);
} else {
letterList.add(log);
}
}
letterList.sort((s1, s2) -> {
String[] s1Split = s1.split(" ", 2);
String[] s2Split = s2.split(" ", 2);
int compare = s1Split[1].compareTo(s2Split[1]);
if(compare == 0){
return s1Split[0].compareTo(s2Split[0]);
}
return compare;
});
letterList.addAll(digitList);
return letterList.toArray(new String[0]);
}
}
배열 - 두수의 합 찾기
https://leetcode.com/problems/two-sum/
기억해야할 포인트
- HashMap<Integer, Integer> numMap = new HashMap<>();
- numMap.containsKey();
-> contains아니고 containsKey()
import java.util.*;
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> numMap = new HashMap<>();
for(int i=0; i<nums.length; i++){
if (numMap.containsKey(target - nums[i])) {
return new int[]{numMap.get(target-nums[i]), i};
}
numMap.put(nums[i], i);
}
return null;
}
}
- numMap.put(nums[i], i);
- numMap.get(target - nums[i])
- return new int[] {x, y};
배열 + 투포인터/스택 - 빗물 모으기
https://leetcode.com/problems/trapping-rain-water/description/
기억할 포인트
- 투포인터 풀이 : 낮은 쪽에서 높은 쪽으로 나아가며 높이차를 더해나가는 아이디어
- Math.max( x, y );
class Solution {
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int leftMax = height[left];
int rightMax = height[right];
int answer = 0;
while(left < right){
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if(leftMax <= rightMax){
answer += leftMax - height[left];
left++;
} else {
answer += rightMax - height[right];
right--;
}
}
return answer;
}
}
기억할 포인트
스택 풀이
- 높이를 push하는 것이 아니라, 현재 위치를 push
투포인터 - 0이 되는 세개의 합 찾기
https://leetcode.com/problems/3sum/
기억할 포인트
- 중복 계산을 없애기 위해 while문으로 넘기는 아이디어
- sum==0 으로 만족 후 while로 넘긴 담긴 다음
left, right 모두 움직이는 부분 -> 처음에 빼먹고 메모리 아웃남
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if(nums == null || nums.length<3){
return result;
}
Arrays.sort(nums);
for(int i=0; i<nums.length-2; i++){
if(i > 0 && nums[i] == nums[i-1] ) continue;
int left = i+1;
int right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0){
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
} else if(sum > 0) {
right --;
} else {
left++;
}
}
}
return result;
}
}
스택 - 일치 판별 : ArrayDeque
https://leetcode.com/problems/valid-parentheses/description/
기억할 포인트
- key value 순서가 다름
- String.length는 괄호가 있음 s.length()
class Solution {
public boolean isValid(String s) {
HashMap<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
ArrayDeque<Character> stack = new ArrayDeque();
for(int i=0; i<s.length(); i++){
// 닫힘이 아닐때 스택에 푸쉬 (열릴때)
if(!map.containsKey(s.charAt(i))){
stack.push(s.charAt(i));
} else if(stack.isEmpty() || map.get(s.charAt(i)) != stack.pop() ){
return false;
}
}
return stack.isEmpty();
}
}
재귀, 문자열 - 중복된 문자열 제거
중복 제거하되 입력된 순서는 지켜줘야하는 문제
https://leetcode.com/problems/remove-duplicate-letters/submissions/1676952541/
기억해야할 포인트
- TreeSet은 set중에서도 정렬을 지원함
- TreeSet compare 메서드 오버라이드 하는 부분
class Solution {
public String removeDuplicateLetters(String s) {
for (char c : toSortedSet(s)) {
String suffix = s.substring(s.indexOf(c));
if (toSortedSet(s).equals(toSortedSet(suffix))) {
return c+ removeDuplicateLetters(suffix.replace(String.valueOf(c), ""));
}
}
return "";
}
public Set<Character> toSortedSet(String s) {
Set<Character> set = new TreeSet<>(new Comparator<Character>() {
@Override
public int compare(Character o1, Character o2) {
if (o1 == o2) {
return 0;
}
else if (o1 > o2) {
return 1;
} else {
return -1;
}
}
});
for (int i = 0; i < s.length(); i++) {
set.add(s.charAt(i));
}
return set;
}
}
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
솔직히 시험때 ide 없이 이렇게 못풀것 같다..
class Solution {
public String removeDuplicateLetters(String s) {
for (char c : toSortedSet(s)) {
String suffix = s.substring(s.indexOf(c));
if (toSortedSet(s).equals(toSortedSet(suffix))) {
return c+ removeDuplicateLetters(suffix.replace(String.valueOf(c), ""));
}
}
return "";
}
public Set<Character> toSortedSet(String s) {
Set<Character> set = new TreeSet<>();
for (int i = 0; i < s.length(); i++) {
set.add(s.charAt(i));
}
return set;
}
}
책처럼 Comparator 주입하고 compare 메서드를 오버라이드 해봤는데
기본 구현이랑 똑같아서 없이도 작동한다
스택 - 숫자가 올라가는 최단 인덱스
https://leetcode.com/problems/daily-temperatures/submissions/1677036643/
배열을 순회하면서 stack에 push
while문으로 스택이 비어있지 않고 peek한것보다 높다면 stack.pop()
pop에는 인덱스가 적혀있으니 현재 인덱스 - pop된 인덱스를 배열[pop index]에 넣어준다
기억할 포인트
- Deque<Integer> stack = new ArrayDeque<>();
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
ArrayDeque<Integer> stack = new ArrayDeque<>();
for(int i=0; i<temperatures.length; i++) {
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
int last = stack.pop();
result[last] = i - last;
}
stack.push(i);
}
return result;
}
}
우선순위 큐 - merge k sorted lists
https://leetcode.com/problems/merge-k-sorted-lists/description/
기억할 포인트
- PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.val, o2.val));
- 여기서는 ListNode를 포함하는 우선순위 큐이기 때문에 compare 로직을 구현
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2)->Integer.compare(o1.val, o2.val));
ListNode root = new ListNode(0);
ListNode tail = root;
for(ListNode node : lists){
if(node!=null) {
pq.add(node);
}
}
while(!pq.isEmpty()){
tail.next = pq.poll();
tail = tail.next;
if(tail.next != null) pq.add(tail.next);
}
return root.next;
}
}
우선순위 큐 - 가까운 좌표 찾기
https://leetcode.com/problems/k-closest-points-to-origin/
처음으로 중첩클래스를 시도한 문제
맨날 생성자는 롬복 쓰다가 직접 치니까 어색하다
기억할 포인트
- PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingDouble(p -> p.distance));
- 이번엔 우선순위 큐에 커스텀 클래스를 집어 넣었음
- 커스텀 클래스에서 비교할 기준을 알려주기 위해 dsitance를 지정해줘야함
- 전에는 커스텀 로직을 바로 람다를 사용했는데, (o1, o2) -> Integer.compare(o1, o2)
- 이번에는 하나를 넣어주기 때문에 Comparator를 넣어주고 메서드를 호출함, 그리고 그 메서드 안에서 로직을 작성 (여기서 람다)
- Comparator.comparingDouble(p -> p.distance)
- priority queue에서 꺼내기 -> pq.poll();
자바 큐에서는 poll로 꺼내기
와 이걸 기억할 수 있나? 큰일났다 진짜
class Solution {
static class Point{
double distance;
int[] point;
public Point(double distance, int[] point){
this.distance = distance;
this.point = point;
}
}
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingDouble(p -> p.distance));
for (int[]point : points){
double distance = Math.sqrt(point[0]*point[0] + point[1]*point[1]);
pq.add(new Point(distance, point));
}
int [][] result = new int[k][];
for(int i=0; i<k; i++){
Point element = pq.poll();
result[i] = element.point;
}
return result;
}
}
우선순위 큐 - 더 맵게 최소 반복으로 섞기
기억해야할 포인트
- PriorityQueue<Integer> pq = new PriorityQueue<>();
-> 이건 그냥 큐에 Integer하나 넣어주는 거여서 Comparator나 람다로 로직을 작성할 필요가 없다.
https://school.programmers.co.kr/learn/courses/30/lessons/42626
테케 통과 못함
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int sc : scoville){
pq.add(sc);
}
while(pq.size() >= 2){
if(pq.peek() >= K){
return answer;
}
int mixed = pq.poll() + (2*pq.poll());
pq.add(mixed);
answer++;
}
return -1;
}
}
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int sc : scoville){
pq.add(sc);
}
while(pq.size() >= 2){
if(pq.peek() >= K){
return answer;
}
int mixed = pq.poll() + (2*pq.poll());
pq.add(mixed);
answer++;
}
if(!pq.isEmpty() && pq.peek() >= K) return answer;
return -1;
}
}
마지막에 1개가 남아도 K 이상이 된 경우를 생각하지 못해서 일부 테케를 통과 못했다. 주의!!
HashSet - 보석찾기
https://leetcode.com/problems/jewels-and-stones/
기억할 포인트
- HashSet<Character> jwelSet = new HashSet<>();
- String을 한글자씩 array로 넘길때
- stones.toCharArray()
class Solution {
public int numJewelsInStones(String jewels, String stones) {
HashSet<Character> jewelSet = new HashSet<>();
for(Character jewel : jewels.toCharArray()){
jewelSet.add(jewel);
}
int count = 0;
for(Character stone: stones.toCharArray()){
if(jewelSet.contains(stone)){
count++;
}
}
return count;
}
}
HashMap + 투포인터 - 중복없이 가장 긴 문자열 substring
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
기억할 포인트
- 키가 있는지 확인하는 HashMap 메서드
- used.containsKey()
- 투포인터를 움직일때 중복된 문자가 있을 때는 왼쪽을 옮긴다.
-> 그런데! HashMap을 초기화하면서 움직인게 아니므로 왼쪽을 옮기기 전에 현재 슬라이딩 윈도우 내부에 있는지를 확인해야함
- 중복된 문자가 없으면 오른쪽을 ++
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> used = new HashMap<>();
int left = 0;
int right = 0;
int answer = 0;
for(Character el : s.toCharArray()){
if(used.containsKey(el) && left <= used.get(el)){
left = used.get(el)+1;
} else{
answer = Math.max(answer, right-left+1);
}
used.put(el, right);
right++;
}
return answer;
}
}
DFS 그래프 - 섬의 개수
https://leetcode.com/problems/number-of-islands/
가장 기본적인 DFS
1로 이어져 있는 개수를 구하면 된다
파이썬만큼은 아니지만 자바 코테가 이제 약간 익숙해 진 것 같다
가보자!
기억할 포인트
- 파이썬처럼 0< i < grid.length 하면 안되고 하나 하나 || -> 이걸로 OR 처리 해줘야함
class Solution {
public int numIslands(char[][] grid) {
int answer = 0;
for(int i=0; i<grid.length; i++){
for(int j=0; j<grid[i].length; j++){
if(grid[i][j] == '1'){
dfs(i, j, grid);
answer++;
}
}
}
return answer;
}
public void dfs(int i, int j, char[][] grid) {
// 벗어나거나 육지->0이면 return
if(i<0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j] == '0') return;
grid[i][j] = '0';
dfs(i, j+1, grid);
dfs(i, j-1, grid);
dfs(i-1, j, grid);
dfs(i+1, j, grid);
}
}
DFS - 전화번호 문자 조합
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
dfs 조금 더 응용 버전
기억할 포인트
- StringBuilder 사용 -> String은 불변 객체니까 append로 path를 업데이트 할 수 있도록 사용
- 재귀할때마다 백트래킹으로 path에 쌓인 문자열을 다시 지워주기 귀찮으니까 new StringBuilder로 넘겨주기
- 만약 new 안하면 path.deleteCharAt(path.length() - 1); 이거 추가해야함
class Solution {
public List<String> letterCombinations(String digits) {
List<String> answer = new ArrayList<>();
StringBuilder path = new StringBuilder();
int currentIndex = 0;
if(digits.length() == 0) return answer;
HashMap<Character, List<Character>> map = new HashMap<>();
map.put('0', List.of());
map.put('1', List.of());
map.put('2', List.of('a', 'b', 'c'));
map.put('3', List.of('d', 'e', 'f'));
map.put('4', List.of('g', 'h', 'i'));
map.put('5', List.of('j', 'k', 'l'));
map.put('6', List.of('m', 'n', 'o'));
map.put('7', List.of('p', 'q', 'r', 's'));
map.put('8', List.of('t', 'u', 'v'));
map.put('9', List.of('w', 'x', 'y', 'z'));
dfs(answer, path, map, currentIndex, digits);
return answer;
}
public void dfs(
List<String> answer,
StringBuilder path,
HashMap<Character, List<Character>> map,
int index,
String digits
){
if(digits.length() == path.length()) {
answer.add(String.valueOf(path));
return;
}
for(Character letter : map.get(digits.charAt(index))){
dfs(answer, new StringBuilder(path).append(letter), map, index+1, digits);
}
}
}
DFS - 기본 순열
https://leetcode.com/problems/permutations/
기억할 포인트
- DFS 빠르게 풀기 위해 트리로 그리면서 생각해보기
- DFS 첫 부분에 탈출 조건 먼저 생각하기
- List는 length가 아니라 size
-> path.size()
- !!!answer에 추가할때 복사하기!!!!!!!
그냥 answer.add(path) 하면 딥카피가 되어서 백트래킹하면서 같이 사라짐
answer.add(new ArrayList<>(path));
- 백트래킹 하며 used랑 path 삭제해주기
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> answer = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] used = new int[nums.length];
dfs(nums, path, used, answer);
return answer;
}
public void dfs(
int[] nums,
List<Integer> path,
int[] used,
List<List<Integer>> answer
){
if(nums.length == path.size()){
answer.add(new ArrayList<>(path));
return;
}
for(int i=0; i<nums.length; i++){
System.out.println(Arrays.toString(used));
if(used[i] == 0){
path.add(nums[i]);
used[i] = 1;
dfs(nums, path, used, answer);
path.remove(path.size()-1);
used[i] = 0;
}
}
}
}
DFS - 기본 조합
https://leetcode.com/problems/combinations/description/
순열과 다르게 순서까지 신경써야하는 조합 별 다른건 없다
파이썬은 다 해주는데 ㅜ
기억할 포인트
- 배열을 로깅용을 출력할때 Arrays.toString() 메서드 사용
- System.out.println(Arrays.toString(nums));
- 이 문제에서는 오름차순 + 요소들 유니크가 보장 되어서 다른 used 같은 추적 로직이 필요 없음 (뒤에 있는 인덱스만 사용하도록 하면 됨)
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> answer = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] nums = new int[n];
for(int i=0; i<n; i++){
nums[i] = i+1;
}
dfs(path, answer, k, nums, 0);
return answer;
}
public void dfs(
List<Integer> path,
List<List<Integer>> answer,
int k,
int[] nums,
int startIndex
){
if(k == path.size()){
answer.add(new ArrayList<>(path));
return;
}
for(int i=startIndex; i<nums.length; i++){
path.add(nums[i]);
dfs(path, answer, k, nums, i+1);
path.remove(path.size()-1);
}
}
}
DFS - 응용 조합의 합
https://leetcode.com/problems/combination-sum/
아주 살짝 응용 문제
간단하다.
조합해서 합이 target 되는 요소들을 반환하면 된다
기억할 포인트
- 마찬가지로 탈출 조건 먼저 생각
- 여기서는 조합이긴 하지만 중복이 가능해서 index를 넘겨줄때 자기 자신을 넘겨주기 (i+1)
- 계속 추가하면 안되니까 currentSum이 target을 넘어가면 return
- 틀이 어느정도 잡혔는데, 메인 메서드를 먼저 작성하고 -> 필요한 dfs 메서드 인자를 생각하면서 추가하기
- 로깅하면서 계속 돌려보고 오타나 컴파일 에러 잡기
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> answer = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(answer, path, candidates, target, 0, 0);
return answer;
}
public void dfs(
List<List<Integer>> answer,
List<Integer> path,
int[] candidates,
int target,
int startIndex,
int currentSum
){
if(currentSum == target){
answer.add(new ArrayList<>(path));
return;
}
if(currentSum > target){
return;
}
for(int i=startIndex; i<candidates.length; i++){
path.add(candidates[i]);
dfs(answer, path, candidates, target, i, currentSum + candidates[i]);
path.remove(path.size()-1);
}
}
}
DFS 응용 - 부분집합
https://leetcode.com/problems/subsets/description/
부분집합 찾기 문제
마지막 부분에 정렬은 안해도 되지만 람다 연습할 겸 해봤다
기억할 포인트
- Set으로 중복되는거 그냥 다 추가했다가, 마지막 반환에서 List로 바꿔주는 아이디어
- Set<List<Integer>> answer = new HashSet<>();
- List<List<Integer>> submit = new ArrayList<>(answer);
- 정렬하는 문법 꼭 기억하자 -> List 내부에 List 하나가 더 있어서 람다로 따로 작성해야함
- submit.sort((o1, o2) -> {
여기다가 쓰기
})
- 지금 o1 o2로 들어가는게 List<Integer> 이거니깐 일단 size로 비교
- 그리고 size가 같다면 첫번째 원소로 비교
- 좀더 엄격하게 하려면 Math.min(o1.size(), o2.size()) 이걸루 순회하면서 Integer.compare(o1.get(i), o2.get(i)) 작은게 나올때까지 돌리는게 맞을 것 같다
class Solution {
public List<List<Integer>> subsets(int[] nums) {
Set<List<Integer>> answer = new HashSet<>();
List<Integer> path = new ArrayList<>();
dfs(answer, path, nums, 0);
List<List<Integer>> submit = new ArrayList<>(answer);
submit.sort((o1, o2)->{
if(Integer.compare(o1.size(), o2.size()) == 0){
return Integer.compare(o1.get(0), o2.get(0));
}
return Integer.compare(o1.size(), o2.size());
});
return submit;
}
public void dfs(
Set<List<Integer>> answer,
List<Integer> path,
int[] nums,
int startIndex
){
if(startIndex >= nums.length){
answer.add(new ArrayList<>(path));
return;
}
for(int i=startIndex; i<nums.length; i++){
// set에 다 담기
answer.add(new ArrayList<>(path));
path.add(nums[i]);
dfs(answer, path, nums, i+1);
path.remove(path.size()-1);
}
}
}
(DFS 응용) 우선순위 큐 + DFS - 일정 짜기
https://leetcode.com/problems/reconstruct-itinerary/
코드는 짧은데
이거 좀 어려웠다 시간도 오래걸리고
그래도 문제에서 대놓고 우선순위 큐 쓰라고 말해줘서 조금 쉬운 편인 것 같다.
기억할 포인트
- 우선순위 큐 + map 사용
파이썬 default dict처럼 초기화시켜주지 않는다 put if absent 사용하기
-> map.putIfAbsent(key, new PriorityQueue);
-> map.get(key).add(value)
- 큐에서 뽑기전에 확인하는 로직이 2개다
키가 있는지, 키로 뽑아서 value가 비어있는지
-> map.containsKey(key)
-> ! map.get(key).isEmpty()
import java.util.*;
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
List<String> answer = new ArrayList<>();
HashMap<String, PriorityQueue<String>> map = new HashMap<>();
for(List<String> ticket : tickets){
map.putIfAbsent(ticket.get(0), new PriorityQueue<>());
map.get(ticket.get(0)).add(ticket.get(1));
}
dfs(answer, map, tickets, "JFK");
return answer;
}
public void dfs(
List<String> answer,
HashMap<String, PriorityQueue<String>> map,
List<List<String>> tickets,
String current
){
while( map.containsKey(current) && !map.get(current).isEmpty()){
dfs(answer, map, tickets, map.get(current).poll());
}
answer.add(0, current);
}
}
스택 풀이
import java.util.*;
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
List<String> answer = new ArrayList<>();
HashMap<String, PriorityQueue<String>> map = new HashMap<>();
for(List<String> ticket : tickets){
map.putIfAbsent(ticket.get(0), new PriorityQueue<>());
map.get(ticket.get(0)).add(ticket.get(1));
}
iterWithStack(answer, map, tickets, "JFK");
return answer;
}
public void iterWithStack(
List<String> answer,
HashMap<String, PriorityQueue<String>> map,
List<List<String>> tickets,
String current
){
Deque<String> stack = new ArrayDeque<>();
stack.push(current);
while(! stack.isEmpty() ){
while(map.containsKey(stack.getFirst()) && !map.get(stack.getFirst()).isEmpty()){
stack.push(map.get(stack.getFirst()).poll());
}
answer.add(0, stack.pop());
}
}
}
DFS가 익숙해져서 그런지 더 편한듯
(DFS 응용) - 여행경로
https://school.programmers.co.kr/learn/courses/30/lessons/43164
위에 문제랑 완전 똑같은 프로그래머스 문제
기억할 포인트
- List -> 배열로 바꾸기 위해
- location.toArray(new String[0]);
-> 이거 때문에 조금 시간이 걸렸다
!!new String[0] 까먹지 말기!!
import java.util.*;
class Solution {
public String[] solution(String[][] tickets) {
String[] answer = {};
List<String> location = new ArrayList<>();
HashMap<String, PriorityQueue<String>> map = new HashMap<>();
for(String[] ticket : tickets){
map.putIfAbsent(ticket[0], new PriorityQueue<>());
map.get(ticket[0]).add(ticket[1]);
}
dfs(tickets, location, map, "ICN");
answer = location.toArray(new String[0]);
return answer;
}
public void dfs(
String[][] tickets,
List<String> location,
HashMap<String, PriorityQueue<String>> map,
String current
){
while(map.containsKey(current) && !map.get(current).isEmpty()){
dfs(tickets, location, map, map.get(current).poll());
}
location.add(0, current);
}
}
DFS 응용 - 순환 구조 확인
https://leetcode.com/problems/course-schedule/
이게 제일 어려운 것 같은데 나와있는 난이도는 medium이다.. 왜지
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
HashMap<Integer, List<Integer>> map = new HashMap<>();
for(int[] pre : prerequisites){
map.putIfAbsent(pre[0], new ArrayList<>());
map.get(pre[0]).add(pre[1]);
}
List<Integer> shouldDo = new ArrayList<>();
List<Integer> finished = new ArrayList<>();
for(Integer finish : map.keySet()){
if(! dfs(map, finish, shouldDo, finished)){
return false;
}
}
return true;
}
public boolean dfs(
HashMap<Integer, List<Integer>> map,
Integer finish,
List<Integer> shouldDo,
List<Integer> finished
){
if(shouldDo.contains(finish)) return false;
if(finished.contains(finish)) return true;
if(map.containsKey(finish)){
shouldDo.add(finish);
for(Integer should: map.get(finish)){
if(! dfs(map, should, shouldDo, finished)){
return false;
}
}
shouldDo.remove(finish);
finished.add(finish);
}
return true;
}
}
다익스트라 - delay time
**!!!이거 내일 시험전에 다시 풀어보기!!!**
https://leetcode.com/problems/network-delay-time/
파이썬 다익스트라는 쉽게 했던 것 같은데 자료형때문에 너무 헷갈린다
기억할 포인트
- 크게 3부분으로 나누어짐
-> times를 해쉬맵에 집어 넣기
-> 우선순위 큐에 넣으며 while문으로 돌리기
-> 마지막에 size로 검증, 가장 큰 값을 return size가 n보다 작다면 모두 순회하지 못한거니까 -1 return
해쉬 맵을 for문으로 돌리기 위해서는
for(Map.Entry<Integer, Integer> r: map.get(current).entrySet())
이렇게 해야한다
근데 헷갈리니까 그냥
Map<Integer, Integer> r = map.get(current);
for(Integer nextVertex : r.keySet()) 이렇게 돌렸다
!! 그냥 우선순위 큐에 List<Integer> 넣는게 베스트인듯 !!
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
HashMap<Integer, Map<Integer, Integer>> map = new HashMap<>();
for(int[] time : times){
map.putIfAbsent(time[0], new HashMap<>());
// 경로를 저장 vertex : (next_vertex:weight)
map.get(time[0]).put(time[1], time[2]);
}
// vertex, weight로 삽입
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
Map<Integer, Integer> distance = new HashMap<>();
pq.add(new int[] {k, 0});
while(!pq.isEmpty()){
int[] element = pq.poll();
int current = element[0];
int weight = element[1];
// 결과값이 없으면 put
if(!distance.containsKey(current)){
distance.put(current, weight);
// 다음 경로가 있으면 queue에 추가
if(map.containsKey(current)){
Map<Integer, Integer> next = map.get(current);
for(Integer nextVertex : next.keySet()){
int updatedWeight = weight + next.get(nextVertex);
pq.add(new int[] {nextVertex, updatedWeight});
}
}
}
}
if(distance.size() == n){
return Collections.max(distance.values());
}
return -1;
}
}
다익스트라 - 가장 싼 경로, K 이내로 움직이기
https://leetcode.com/problems/cheapest-flights-within-k-stops/
아. 힘들다.
최적화를 조금 더 해야 풀 수 있는 문제
이런게 나오려나.. ㅋㅋㅋㅋㅋ
기억할 포인트
- visited를 추가했다
- 그냥 visited가 있으면 안가는 로직은 안통한다 -> k번 이내때문에
import java.util.*;
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// 출발 : (도착 : 비용) 저장
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
for(int[] flight : flights){
map.putIfAbsent(flight[0], new HashMap<>());
map.get(flight[0]).put(flight[1], flight[2]);
}
PriorityQueue<List<Integer>> pq = new PriorityQueue<>(
(o1, o2) -> Integer.compare(o1.get(1), o2.get(1)));
// pq에 vertex, 거리(weight), 움직인 횟수 저장
pq.add(Arrays.asList(src, 0, 0));
Map<Integer, Integer> visited = new HashMap<>();
while(! pq.isEmpty()){
List<Integer> polled = pq.poll();
Integer current = polled.get(0);
Integer weight = polled.get(1);
Integer moved = polled.get(2);
visited.put(current, moved);
if(current == dst) return weight;
if(moved <= k){
if(map.containsKey(current)){
for(Map.Entry<Integer, Integer> v: map.get(current).entrySet()){
Integer nextVertex = v.getKey();
Integer addWeight = v.getValue();
Integer nextWeight = weight + addWeight;
if(!visited.containsKey(nextVertex) || moved < visited.get(nextVertex)){
pq.add(Arrays.asList(nextVertex, nextWeight, moved+1));
}
}
}
}
}
return -1;
}
}
우선순위 큐 - k 번째 큰 값
https://leetcode.com/problems/kth-largest-element-in-an-array/
간만에 쉬운 문제
정렬 쓰지 않고는 우선순위 큐
기억할 포인트
- new PriorityQueue<>(Comparator.reverseOrder());
리버스 오더는 처음인데 뭔가 때려 맞췄다 다행
진짜 조금 적응 된것 같은데? 가보자 가보자 가보자 가보자고 가보자고 가보자고 아자
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
for(Integer num : nums){
pq.add(num);
}
int answer = nums[0];
for(int i=0; i<k; i++){
answer = pq.poll();
}
return answer;
}
}
이진탐색 - Arrays.binarySearch(array, target)
https://leetcode.com/problems/binary-search/
기본 이진탐색
기억할 포인트
- 존재한다면 0이상의 값을 준다 (존재하는 값의 인덱스)
- 없다면 들어가야할 (index*(-1) - 1) 반환
class Solution {
public int search(int[] nums, int target) {
int result = Arrays.binarySearch(nums, target);
if(result>=0){
return result;
}
return -1;
}
}
분할정복 - 연산 경우의 수
https://leetcode.com/problems/different-ways-to-add-parentheses/description/
기억할 포인트
- 분할정복! 믿고 맡기기 느낌
- substring
- Integer.parseInt(expression);
class Solution {
public List<Integer> diffWaysToCompute(String expression) {
List<Integer> answer = new ArrayList<>();
for(int i=0; i<expression.length(); i++){
Character c = expression.charAt(i);
if(c == '-' || c == '+' || c == '*'){
List<Integer> left = diffWaysToCompute(expression.substring(0,i));
List<Integer> right = diffWaysToCompute(expression.substring(i+1));
for(int call : left){
for(int calr : right){
if(c == '-'){
answer.add(call - calr);
}
else if(c == '+'){
answer.add(call + calr);
}
else if(c == '*'){
answer.add(call*calr);
}
}
}
}
}
if(answer.isEmpty()){
answer.add(Integer.parseInt(expression));
}
return answer;
}
}