문제진열된 보석들 중 모든 종류의 보석을 적어도 하나 이상 포함하는 가장 짧은 구간을 찾아야 한다.조건은 다음과 같다:보석의 진열 순서가 담긴 문자열 배열 gems가 주어진다.진열된 보석들을 연속적으로 선택한 구간 중, 모든 보석 종류를 한 번 이상 포함하는 가장 짧은 구간의 시작과 끝 인덱스를 반환한다.정답이 여러 개인 경우, 시작 인덱스가 가장 작은 구간을 반환한다.풀이 방법풀이 시간 : 1시간풀이 방법 : 투포인터 + 해시맵 (슬라이딩 윈도우) 반환 타입을 보자마자 이건 투포인터구나! 라는 생각을 했다.그리고 문제에 나와있는대로 모든 종류를 포함해야 한다는 조건때문에 Set과 HashMap을 이용해 중복에 대한 처리를 진행하거나, 갯수에 대한 처리를 진행할 수 있을 것 같다는 생각을 하고 들어갔다...

문제트럭 여러 대가 순서대로 다리를 지나가야 한다. 단, 다리는 bridge_length 만큼의 길이를 가지며, 동시에 올라갈 수 있는 트럭의 무게 합은 weight를 넘지 않아야 한다. 트럭은 1초에 1만큼 이동, 다리에 올라간 순서대로 움직인다. 모든 트럭이 다리를 건너는 데 걸리는 최소 시간을 구해야한다.풀이방법풀이 시간 : 30분풀이 방법 : 시뮬레이션 + 큐(Queue) 처음에는 단순히 다리 길이나 무게 제한만 고려해서 트럭을 올릴 수 있는지 판단하면 된다고 생각했다.하지만 다리 위에서 트럭이 동시에 이동하고, 무게 제한도 유지하며 매 초마다 트럭이 한칸씩 이동한다는 점에서 단순 조건문으로는 해결할 수 없었따. 예를 들어,더보기bridge_length = 2 weight = 10 truc..

문제아래로 내려가면서 점수를 가장 많이 얻을 수 있는 경우를 찾는 것이다. 하지만 같은 열을 반복해서 밟을 수는 없다. 풀이방법풀이 시간 : 30분풀이 방법 : DP 맨 처음에는 0번째 행에서 제일 큰값을 찾아서 아래에서 같은 열이 아닌것 중 가장 큰걸 찾으면 되는 줄 알았다.근데 생각해보니 0번째 행에서 선택되는 값에 따라 달라진다는걸 알 수 있었다. 예를 들어,129108791154882344 라는 그래프가 있을때 내가 맨처음에 생각했던 방식은 위와 같다고 생각했는데, 129108791154882344위와같은 방식의 점수합이 더 크다는걸 알 수 있었다.그래서 DP를 생각했고, 그냥 1번째 행부터 현재 0,1,2,3열에서 바로 윗 행의 가장 큰값을 더해오면 된다. 1행 0열에서 자신과 열이같은 바로 윗..

문제미로의 출구를 찾아 최단 경로로 탈출하는데, 중간에 레버를 당기고 탈출해야하는 문제이다.풀이방법풀이 시간 : 20분풀이 방법 : BFS BFS를 이용해 최단 경로를 만들어주면 되는데 레버를 당기는게 이 문제의 핵심이다.쉽게는 그냥 시작점 -> 레버 + 레버 + 탈출구의 경로를 찾아 더해주면 된다.코드import java.io.*;import java.util.*;class Solution { static final int[] dx = {1, -1, 0, 0}; static final int[] dy = {0, 0, -1, 1}; static int n, m; static char[][] map; public int solution(String[] maps) { ..

백트래킹으로 조합과 순열 구하기프로그래밍 문제를 풀다 보면, 특정 수나 문자열을 이용해 모든 가능한 경우의 수를 만들어야 하는 경우가 많다.이럴 때 사용되는 대표적인 알고리즘이 바로 백트래킹(Backtracking)이다. 백트래킹이란?백트래킹은 가능한 모든 경우의 수를 시도하면서, 불필요한 가지는 미리 쳐내는 방식이다.특히 조합, 순열과 같이 특정 조건에 맞는 모든 조합을 만들어야 할 때 매우 유용하게 사용된다. 백트래킹으로 구현하는 각 경우1. 조합(Combination)void combination(int[] arr, int start, int depth, int r, List result) { if (depth == r) { System.out.println(result); ..

문제주어진 numbers들을 재조합해 소수의 갯수를 찾는 문제이다. 풀이방법풀이 시간 : 20분풀이 방법 : 완전탐색 크게보면 2가지로 나눌 수 있다. 주어진 numbers들을 이용해 새로운 조합 만들기만들어진 조합수들이 소수인지 확인하기1. 조합 만들기 - 백트래킹에서는 현재까지 만든 숫자 문자열(current)과 방문 여부 배열(visited)을 이용해 1자리부터 n자리까지 모든 숫자 조합을 생성했다. 이 과정에서 같은 숫자가 여러 번 조합될 수 있으므로, 중복을 방지하기 위해 Set을 사용해 생성된 숫자를 저장했다. 2. 소수 찾기- 이제 이렇게 만들어진 숫자들이 소수인지 확인해줘야 하는데, 여기서 중요한건 소수 판별의 효율성이다. 단순하게 2부터 number - 1 까지 나누는 방식은 너무 비효율..