stonesy

📌풀이1. 각 주문을 알파벳 순서로 정렬한 뒤, 조합을 생성한다.2. 생성된 조합이 나타나는 횟수를 기록한 뒤, 각 길이에 대해 가장 많이 주문된 조합을 찾는다.3. 최종적으로 모든 결과를 사전 순으로 정렬하여 반환한다.최악의 경우 10*20*2^10 📌코드import java.util.*;class Solution { public static void getCombination(Map ret, String str, int N, int depth, int start, char[] cur){ if(depth>=N){ if(!ret.containsKey(new String(cur))) ret.put(new String(cur), 0); ret.pu..

풀이: 누적합&투포인터특정 조건을 만족하는 연속된 부분 배열의 문제에서 누적합&투포인터의 개념이 많이 사용된다.1) right 포인터는 0~N-1까지 증가면서 오른쪽으로 이동한다.2) left 포인터는 s값이 주어진 조건보다 크다면 포인터를 오른쪽으로 계속 옮겨준다. 이는 주어진 조건이 자연수로 이루어진 길이 N의 수열이기 때문에 가능하다. 코드import java.io.*;import java.util.*;public class Main1806 { public static int N,S; public static int[] arr; public static void main(String[] args) throws Exception { // 1. 입력 및 초기화 ..

풀이 과정memo[n][m]에 저장할 값은 시간 n에 지침 정도 m일 때 가질 수 있는 최댓값이다. 쉬는 경우 (memo[n][0] = memo[n-1][0]): 이전 시간의 최대 거리를 그대로 유지.뛰는 경우 (memo[n][m] = memo[n-1][m-1] + D[n]): 이전 시간까지 뛴 거리에서 현재 거리를 더하여 최대 거리 갱신.마지막으로 최대 연속 시간 M 이내에서 쉬는 경우를 비교하여, 특정 시간에 쉬었을 때의 최대 거리를 갱신.  코드import java.io.*;import java.util.*;// dppublic class Main_1757_G4_달려달려 { public static int N,M; public static int[] D; public static i..

해결방법최단 경로를 구해야하므로 BFS를 사용한다.이때, visited를 3차원으로 만들어야 한다. 더러운 칸을 방문하는 순서를 고려해야 하기 때문이다. → visited배열을 3차원으로 관리해야한다. → 비트마스킹을 사용해야 한다.그래프를 모두 순회했음에도 답을 구하지 못한 경우는 방문할 수 없는 더러운 칸이 존재하는 것이므로 -1를 출력한다.모두 방문: curD==((1방문 처리: curD | (1 코드import java.util.*;import java.io.*;// 396ms// BFS + 비트마스킹 + dppublic class Main_4991_G1_로봇청소기_BFS비트마스킹 { static int h,w; // w: 방의 가로크기, h: 방의 세로 크기 static char[][..

해결방법3차원 visited 배열이 문제 풀이의 핵심이라고 생각한다.visited[r][c][i]는 (r, c) 위치에 도달했을 때, 방향 i(상, 하, 좌, 우 중 하나)로 이동한 경우에 사용된 거울의 수이다. 이때, visited가 3차원이어야 하는 이유는 같은 (r,c)라도 레이저가 상,하,좌,우 어느쪽에서 들어왔는지에 따라 다음 위치로 이동할 때 필요한 거울의 수가 달라질 수 있기 때문이다.따라서 BFS + 3차원 방문처리를 통해 풀었고, O(W*H)로 풀 수 있다. 코드import java.util.*;import java.io.*;public class Main_6087_G3_레이저통신 { static int H,W; static char[][] map; static List point; st..

해결 방법완전 탐색으로 접근하면 시간 초과가 발생한다. 한 지점에서 3방향으로 이동할 수 있고, 지점이 NM개 있으므로 O(3^(NM))의 시간복잡도가 소요되기 때문이다.첫 번째 행의 경우 오직 왼 → 오 방향만 가능하므로 따로 계산해주고 두 번째 행부터는 왼 → 오 / 오 → 왼을 비교해주어야 한다. 즉, 이전 단계의 최적 결과를 바탕으로 다음 단계에서의 최적 결과를 구해야하므로 DP로 접근한다고 볼 수 있다. 따라서 O(N*M)의 시간복잡도로 해결할 수 있다. 코드import java.util.*;import java.io.*;public class Main { static int MIN_VAL = -987654321; static int N,M; // (1≤N, M≤1,000) st..

해결방법서로소 집합을 통해 여행 계획인 도시들의 대표자가 모두 같으면 “YES”, 하나라도 다르다면 “NO”를 출력한다.서로소 집합시에 경로 압축 + 랭크 기반 유니온을 사용하면 find 및 union시 거의 상수시간이 소요되므로 O(N+M)의 시간복잡도로 해결할 수 있다. 코드import java.util.*;import java.io.*;// 160ms, Disjoint Setpublic class Main_1976_G4_여행가자_서로소집합 { static int N; // N: 도시의 수 static int M; // M: 여행 계획에 속한 도시들의 수 static int[][] graph; static int[] plan; static int[] parents; s..

해결방법스택을 이용하여 문제를 O(N)의 시간 복잡도로 해결할 수 있다.핵심은 스택에 자신보다 작은 높이만 유지해야 한다.현재 높이를 스택의 peek() 값과 비교하여, 만약 peek() 값이 현재 높이보다 크다면, 스택에서 해당 값을 pop() 한다. 이때 pop()할 때마다 정답을 증가시킨다.스택에 값을 넣을 때는 다음 조건을 확인한다.현재 높이가 0이 아닌 경우스택의 peek() 값이 현재 높이와 다른 경우 코드import java.util.*;import java.io.*;// 216ms, 스택, O(N)public class Main_1863_G4_스카이라인쉬운거_스택 { public static void main(String[] args) throws IOException{ ..

해결방법뽑힌 정수들의 idx들의 집합 = 뽑힌 정수들의 집합을 동일하게 만들어야 한다.감이 잘 안 잡혀서 풀이를 먼저 읽었는데 ^^ ..뽑힌 숫자들의 특징은 싸이클을 이루는 숫자들이라고 한다.문제에서 주어진 숫자들을 예시로 보면1 → 3 → 13 → 1 → 35 → 5따라서 dfs를 통해서 target(처음 시작 인덱스)를 만나면 정답배열에 넣어주도록 코드를 작성하면 되고, O(N^2)의 시간복잡도로 문제를 해결할 수 있게 된다. 코드import java.util.*;import java.io.*;// DFS, O(N^2)public class Main_2668_G5_숫자고르기_DFS { static int N; static boolean[] visited; static int[] num..

해결방법서로소 집합 / 랭크 기반 유니온(Rank Based Union)rank → 친구 네크워크의 크기를 나타내며, 친구 네트워크의 큰 쪽에 편입시킨다.rank 기반 union을 사용하므로 union시 O(1) → 상수시간에 가깝게 동작한다.따라서 O(N)=O(F)의 시간복잡도에 문제를 해결할 수 있다. 코드import java.util.*;import java.io.*;// 1668ms// union 연산에서 랭크 기반 union을 사용하므로 O(1)에 가깝게 동작한다,// 따라서 대략 O(N)=O(F)public class Main_4195_G2_친구네트워크_서로소집합 { static final int N = 200005; static int F; // F: 친구 관계의 수 stat..