mondegreen

그래프 너무 어렵지만.. 가중치가 없는 그래프이니까 다익스트라 제외, 최단경로가 아니라 어디까지 이어져 있는지가 중요하니까 BFS가 아닌 DFS로 구현하기로 결정했다. 보통은 두개의 트리로 분리되어 있는 송전탑을 하나의 트리로 연결시키라고 하면 너무...정말... 유니온파인드 써서 쉽게 처리하겠지만 이건 반대로 한개를 두개로 나누라고 하니 풀이방법을 찾지 못했다. 아래는 책을 참고해서 푼 로직이다. 답인 answer는 최대값인 n-1로 설정한다. 그 이유는 다른 한쪽이 한 개의 송전탑으로 이루어진 경우에 가장 큰 차이를 가지는 때이므로 n-1로 초기화해준다. DFS부분이 문제인데 송전탑을 하나씩 연결해가면서 나머지 송전탑 무리들과의 차이를 최솟값으로 갱신해나간다. 그래서 현재 송전탑이 연결된 것으로 가정..

가중치가 있는 그래프 문제이다. 다익스트라 알고리즘을 활용해야 하므로 우선순위 큐로 구현해야 한다. 이 때 delivery라는 클래스는 정렬 기준을 선언해줘야 한다. 주의할 점은 무방향 그래프이기 때문에 인접리스트에 양방향으로 값을 넣어줘야 한다. 오랜만이다 다익스트라..!ㅎ import java.util.*; class Solution { public static class delivery{ int dest; int time; public delivery(int x, int y){ this.dest = x; this.time = y; } } public int solution(int N, int[][] road, int K) { int answer = 0; int [] dist = new int[N+1..

import java.util.*; class Solution { public static Deque dq; public static int dist[][]; public static int n, m; public static class Position{ int r; int c; public Position(int x, int y){ this.r = x; this.c = y; } } public int solution(int[][] maps) { int answer = -1; n = maps.length; m = maps[0].length; dist = new int[n][m]; dist[0][0] = 1; dq = new ArrayDeque(); dq.add(new Position(0, 0)); int..

최소 비용을 구하는 문제이다. 먼저 각 섬의 루트노드를 저장할 배열을 선언한다. 이 때 초기 값은 각자의 인덱스 값이다. 즉, 각자가 루트노드인 것이고 각자의 집합에 속해있는 것이다. 그 다음 건설 비용이 적은 순서대로 먼저 정렬해준 후 순서대로 연결을 해본다. 이 때 연결하기 전 두 섬의 연결되어 있는지는 루트 노드를 찾아서 비교한다. 만약 다르다면 다리 연결에 드는 비용을 정답 변수에 더해주고 유니언 메소드를 통해 한쪽 루트노드를 다른 한 쪽으로 변경해서 합쳐준다. 같을 때 다리를 놓는다면 사이클이 생겨 비효율적이고 최소 비용이 될 수 없다. 이 작업을 반복하며 다리의 갯수가 n-1개 일 때 작업을 완료하면 된다. n개를 연결하는 최소 갯수는 n-1개 이기 때문이다. import java.util.*..

import java.util.*; class Solution { public static int[] answer = {-1, -1}; public int[] solution(int n, String[] words) { HashSet set = new HashSet(); char lastLetter= '-'; for(int i = 0; i

import java.util.*; class Solution { public static int [] answer; public static HashMap chain; public static HashMap order; public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) { answer = new int[enroll.length]; chain = new HashMap(); order = new HashMap(); for(int i =0; i

class Solution{ public int solution(int n, int a, int b) { int answer = 0; // 트리로 구현했을 때 1라운드의 위치를 인덱스로 두고(리프노드) // /2를 해가며 부모노드가 같아졌을 때 만나는 것으로 판정 // /2한 횟수가 지나 온 라운드 수 a = a+n-1; b = b+n-1; while(a!=b){ a /=2; b /=2; answer++; } return answer; } }

동명이인이 있다는 지시문에 key 값으로 이름을 활용하지 못할 것이라고 생각했다. 그래서 각 배열을 정렬한 후 완주한 배열의 인덱스와 참가한 인덱스의 이름이 서로 맞지 않는다면 그 친구가 낙오한 것이기 때문에 완주한 친구들을 맵에서 지워가면서 확인했다. 정렬을 해야한다는 단점이 존재했다. import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { String answer = ""; Arrays.sort(participant); Arrays.sort(completion); HashMap completed = new HashMap(); for(int i = 0; i< complet..

구하고자 하는 것은 특정일자의 가격을 기준으로 가격이 떨어진 날까지의 기간이므로 그 날짜들을 구분할 수 있는 인덱스를 가지고 활용해야 한다. 따라서 스택에 들어갈 값은 배열의 인덱스이다. 여기서 스택을 활용할 수 있다고 생각하게 되는 지점은 앞으로의 주식 가격이 아닌 이전 주식가격들과 비교해서 기간을 구한다는 점이다. 따라서 현재 주식 가격보다 가장 최근 주식 가격이 더 높다면 해당 가격을 가진 날짜는 하루 동안 떨어지지 않은 것이고 해당 날짜를 스택에서 제거한다. 정답 배열에 값을 넣을 때는 제거될 스택의 값이 더 이상 고려되지 않아도 되는 값이고 구간이 정해지는 값이므로 제거될 스택의 값을 정답 배열의 인덱스로 잡고 현재 넣고자 하는 인덱스와의 차를 구해 기간을 담으면 된다. 그리고 또 다시 가장 최..

스택을 deque로 활용함으로써 자료구조를 양껏 활용한 풀이이다. 다만 값을 빼고 넣는 순서를 헷갈리기 쉽다. import java.util.*; class Solution { public int solution(String s) { char[] target = s.toCharArray(); // 기본 문자열 스택에 담아 놓기 Deque base = new ArrayDeque(); for(int i = 0; i