mondegreen

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

연결되어 있는 좌표의 수를 모두 더하는 문제였고 BFS를 구현했으며 연결되어 있는 여부를 Queue를 활용해서 해결했다. 그 외에는 경계를 벗어나거나 char 를 int로 변환해서 더해주는 것 정도 고려하면 될 것 같다. import java.util.*; class Solution { public static char[][] map; public static boolean[][] visited; public int[] solution(String[] maps) { int rLen = maps.length; // 행 int cLen = maps[0].length(); // 열 map = new char[rLen][cLen]; for(int i = 0; i

지문에서 보조 컨테이너 벨트는 스택으로 구현해야 함을 파악할 수 있었다. 앞에 위치한 상자와 보조 컨테이너 벨트를 모두 체크해야 했고 두 곳에서 찾을 수 없는데 앞에 위치한 상자보다 실어야 할 상자 수가 더 작다면 더 실을 수 있는 가능성이 없기 때문에 바로 return 처리 했다. import java.util.*; class Solution { public int solution(int[] order) { int answer = 0; Deque stk = new ArrayDeque(); // index는 1부터 시작하는데 int index = 1; // order 반복문을 돌면서 for(int i = 0; i

기본적으로 재귀의 방식으로 구현하면 된다. 다섯가지의 문자로 길이 5의 문자열을 만드는 경우의 수가 5000가지 이하이므로 시간을 고려하지는 않았다. 그래도 글자에 + 하는 건 비효율이라고 생각해서 스트링빌더를 사용했다. 그리고 오래 가지 않도록 답을 찾으면 return 하도록 구현했다. import java.util.*; class Solution { public static char [] arr = {'A', 'E', 'I', 'O', 'U'}; public static String target; public static int tmp, answer; public int solution(String word) { tmp = 0; answer = -1; target = word; StringBuilde..

10진법의 수를 3진법으로 바꾸며 나머지는 진법의 수로 몫은 0이 될 때까지 다시 나누는 몫으로 처리하여 구한다. 기존 3진법의 0,1,2 대신 1,2,4를 쓰는 방식의 풀이이다. import java.util.*; class Solution { public String solution(int n) { StringBuilder sb = new StringBuilder(); while(n > 0){ int remainder = n % 3; if(remainder == 0) sb.insert(0, "4"); else if(remainder == 1) sb.insert(0, "1"); else if(remainder == 2) sb.insert(0, "2"); n = (n - 1) / 3; } return s..

[정답코드] 인접리스트에 매몰되었음... 해시 맵을 우선순위 큐와 조합해서 유사하게 구현 가능하며 정렬까지도 한 번에 해결해 줌. 재귀가 끝나는 순서대로 답에 담기기 때문에 역순처리 해주기 import java.util.*; class Solution { public static ArrayList answer; public static HashMap tks; public String[] solution(String[][] tickets) { answer = new ArrayList(); tks = new HashMap(); for(String[] ticket : tickets){ tks.putIfAbsent(ticket[0], new PriorityQueue()); tks.get(ticket[0]).ad..

커서가 이동하기 위해서는 스택을 두개 사용하는 것이 필요할 것 같았다. 커서를 기준으로 왼쪽과 오른쪽 스택을 별도로 구현하고 커서를 기준으로 양쪽으로 이동시켜주면 된다. 커서 이동과 삭제 시마다 스택이 비어있는지 확인하는 것은 필수이고 커서가 중간에 위치한채로 입력이 끝날 수 있기 때문에 오른쪽 스택에 존재하는 값을 왼쪽으로 모두 옮겨준 후에 stringbuilder로 문자열화해주고 역순으로 처리해주면 된다. package BaekJoon.stack; import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class BJ5397 { public static void main(String[] args) { S..

[Part2-Chapter02-Clip04] -백준 2504 괄호의 값 짝이 되는 괄호를 if 문으로 복잡하게 쓰지 않기 위해 map에 담아서 짝을 맞추도록 했고 소괄호와 대괄호를 2와 3으로 매칭시키는 것도 map을 활용했다. 값을 넣을 때마다 최근 넣은 값을 저장한다. 괄호가 열릴 때마다 곱을 해주고 닫힐 때마다 다시 해당하는 수로 나누어서 결과값을 갱신시키는 방식으로 풀이했다. 가장 먼저 예외처리할 부분은 괄호가 짝이 맞도록 닫히지 않는다면 0을 반환해야 한다. 따라서 일단 입력값의 길이가 홀수라면 바로 0을 반환하고, stack을 활용해 괄호가 잘 닫히고 있는지도 확인하여 스택에 남은 값이 있다면 0을 반환하도록 구현했다. 여는괄호인 경우 스택에 담아주고 해당하는 숫자를 곱해준다. 닫는 괄호인 경..

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

재귀..재귀..진짜 왜 재귀적 머리가 안 돌아가는지.. 한참 고민하고 푼 문제이다. 일단 타겟을 찾는 것보다 어쨋든 답이 나오는 문제라면 빼주어야 하는 값을 찾기로 한다. 오래 걸린 부분은 현재 이 숫자를 선택하느냐 마느냐라는 부분을 어떤 방식으로 구현하는 것인지였다. 아래와 같이 선택 여부에 따라 dfs를 나누어 실행해주고 만약 더한 값이 찾고자 하는 값보다 크면 바로 return해 버리는 방식으로 구현했다. class Solution { private static int find, answer; public int solution(int[] numbers, int target) { answer = 0; int total = 0; for(int i =0; i find) return; if(thisNum..