mondegreen

앞쪽과 뒤쪽으로 방향으로 순회하면서 각 인덱스 별로 몇개의 종류를 가지는지 set에 담고 set의 크기를 새로운 배열에 각각 넣어줬다. 그리고 경계가 되는 연속되는 두 인덱스의 값이 같을 경우 answer에 더해주는 방식으로 구현했다. 처음에는 앞쪽으로만 토핑의 수를 세고 매번 남은 토핑 종류를 세려고 했지만 인덱스 옮길 때마다 반복문을 최악의 경우 백만번의 인덱스를 매번 돌아줘야 하기 때문에 시간 초과가 발생한다. 따라서 아래 코드 처럼 미리 양방향으로 토핑 수를 세어주자. import java.util.*; class Solution { public int solution(int[] topping) { int answer = 0; int len = topping.length; int [] order ..

동일한 숫자는 카운트하지 않기 때문에 set을 활용해야겠다고 판단했다. 숫자를 고르는 방법은 특정 인덱스를 기준으로 뒤의 숫자만 고르게 하려고 했었다. 그런데 이렇게 처리하게되면 뽑은 숫자마다 순서를 직접 달리 배치해봐야 하는 번거로움이 발생한다. 따라서 방문 배열을 생성하고 해당 숫자를 뽑았는지를 체크하며 고르고 모든 인덱스를 순회하도록 처리했다. 이렇게 처리하면 모든 숫자를 순회하는 대신 뽑은 숫자 간의 숫자를 바꿔서 배치할 필요가 없다. k개의 카드만 뽑아야 하므로 cnt 변수로 뽑은 숫자를 관리했다. package BaekJoon.backtracking; import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; pub..

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