📌 Problem 일렬로 진열된 보석들이 String 배열로 주어진다. 보석 진열대에서 최소한의 연속된 보석들을 구매하여 모든 종류의 보석들을 최소 1개씩을 구매하고자 한다. 최소한의 길이를 가진 경우에서 시작 번호와 끝 번호를 배열로 반환해라. 보석은 주어진 배열의 index 0부터 1번이라고 생각한다. 또한 최소 길이가 동일한 경우에는 시작 번호가 작은 경우를 선택한다. 📌 Solution 2 Pointer으로 해결할 수 있는 문제이다. 첫 번째 보석부터 차례대로 탐색하며 다음의 과적을 진행한다. 📌 Example 📌 [Code](https://github.com/codesver/problem-solving-hub/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%

📌 Problem 사용자의 ID는 알파벳 소문자와 숫자로만 이루어져 있으며 중복되는 ID는 없다. 이벤트에 응모한 전체 사용자 ID 배열과 비정상적인 방법으로 이벤트에 응모하여 제한된 사용자 ID 배열이 주어진다. 이 때 비정상적인 방법으로 이벤트에 응모한 사용자 ID들은 최소 1개 이상의 문자가 으로 가려져 있다. 예를 들어, codesver이라는 사용자 ID는 co\es\*er과 같이 아이디가 가려져 있다. 제한된 사용자 ID 배열으로 유추할 수 있는 제한 서로 다른 사용자 집합의 수를 구하여 반환한다. 📌 Solution 다음의 예시를 바탕으로 설명한다. 제한된 사용자 ID와 매칭이 되는 모든 사용자 ID 번호(Index) 리스트를 구한다. 백트래킹으로 조합할 수 있는 모든 경우의 수를 구하고 각 경우를 bit mask

📌 Problem 일렬로 이루어진 아파트들의 옥상에 기지국을 설치하려고 한다. 기지국은 w 만큼의 전파력을 가지고 있는데 설치한 곳으로 부터 +w, -w인 아파트까지 전파가 도달하는 것이다. 예를 들어 5번 아파트에 2의 전파력을 가진 기지국을 설치하면 3 ~ 7까지의 아파트에 전파가 도달한다. 아파트는 1번부터 n번까지로 이루어져 있다. 아파트의 수 n과 전파력 w 그리고 현재 기지국이 설치되어 있는 아파트 번호 배열이 주어진다고 하였을 때 최소한의 기지국을 추가 설치하여 아파트 전체에 전파가 도달하도록 하려고한다. 설치해야하는 최소한의 기지국 수를 구하여라. 📌 Solution 전파가 도달하지 않은 구간이 M만큼 있다고 가정해보자. 전파력이 W일 때 여기에 설치해야 하는 기지국의 수는 우선 $$\frac{M}{2W + 1}$$ 이다. 예를 들

📌 Problem 📌 Solution A팀에서 자연수가 가장 높은 사원부터 나온다고 가정한다. B팀 또한 가장 높은 자연수를 가진 선수부터 출전을 하기로 하지만 만약 출전한 A팀 선수를 이길 수 없다면 점수가 가장 낮은 선수를 대신 내보내서 손해를 최소로 한다. 이 과정에서 B팀이 이긴 횟수를 구한다. 📌 [Code](https://github.com/codesver/problem-solving-hub/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv3/12987.%E2%80%85%EC%8

📌 Problem 2차원 배열 형태의 도시가 있다. (0, 0)에 집이 있으며 (m - 1, n - 1)에 학교가 있다. m방향과 n방향으로만 움직일 수 있다. 또한 중간에 있는 웅덩이는 지나갈 수 없다. 집에서 학교까지 갈 수 있는 경우의 수를 1,000,000,007으로 나눈 나머지를 반환한다. 📌 Solution 동적 프로그래밍으로 간단하게 해결할 수 있다. Step 1. 웅덩이 위치 구하기 도시의 전체 도록 크기와 같은 크기의 통과 금기 배열을 만들고 입력값에 따라 접근이 가능한지 아닌지를 판단한다. Step 2. 1가지 방법 뿐인 곳들을 초기화 (0, 0)에서 우측 혹은 하단으로만 움직여서 갈 수 있는 도로들은 도착 방법이 한 가지이기 때문에 1로 초기화한다. 다만, 중간에 웅덩이가 있으면 이후의 도로들에는 갈 수 없기

📌 Problem 배열에는 작업별 양이 정수 형태로 주어진다. 작업들을 퇴근 시간 전에 끝내지 못하면 야근을 해야한다. 야근으로 인한 피로도는 야근이 시작한 시점에서 각 작업별 작업량 제곱의 합이다. 1시간마다 1의 작업을 수행할 수 있고 퇴근 시간까지 N시간이 남았을 때 야근으로 인한 최소 피로도를 반환한다. 예를 들어서 [4, 3, 3]의 작업 목록이 있고 퇴근까지 2시간이 남았으면 [2, 3, 3]으로 작업하면 야근 피로도가 22으로 최소가 된다. 📌 Solution 매 시간마다 어떤 작업을 처리할지를 결정해야 한다. 생각해보면 가장 많이 남은 작업을 처리하는 것이 수학적으로 맞다. 작업량 K와 K-1이 있을 때를 생각해보자. K 작업량에서 1을 빼면 최종적으로 감소하는 야근 피로도는 $K^2 - (K-1)^2$이 된다. 이를 풀어서 계

📌 Problem 중복이 가능한 자연수의 개수 N과 모든 자연수의 합 S가 주어진다. N개의 자연수 합이 S가 되는 것 중에 N개의 자연수 곱이 최대인 자연수 배열을 오름차순으로 정렬하여 반환하면 된다. 가능한 경우가 없으면 -1을 포함하는 배열을 반환한다. 📌 Solution 처음에는 백트래킹 방식으로 문제를 해결하였다. 솔루션 자체는 맞았지만 시간 복잡도 측면에서 굉장히 오래 걸리면서 통과를 하지 못했다. 그래서 좀 더 빠르게 해결할 수 있는 방법을 찾았는데 사실 비슷한 문제를 알고 있다. 둘레가 일정한 직사각형에서 최대 넓이를 만들고 싶으면 정사각형이 되어야 한다. 이 문제도 마찬가지이다. 모든 자연수가 최대한 동일할 때 최대곱이 완성된다. 이를 구현하는 것은 매우 간단하다. 모든 숫자를 S / N으로 초기화하고 S % N개의 숫자에 1씩

📌 Problem 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 한다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 정수 삼각형 정보가 주어질 때 거쳐간 숫자의 최대합을 구하면 된다. 📌 Solution 대표적인 DP 문제 중에 하나이다. 이중 반복문으로 정수들을 탐색한다. 위에서부터 row = 0, 왼쪽부터 col = 0이라고 할 때 (row, col)의 최대합은 (row, col) + max((row -

📌 Problem 재생된 음악의 대한 정보가 순서대로 제공된다. 각 음악의 대한 정보는 문자열 형태로 들어오는 데 시작시간, 종료시간, 제목, 멜로디가 문자 ,를 기준으로 구분되어 주어진다. (03:00,03:08,TITLE,MELODY) Melody는 총 12개의 음으로 이루어지는 데 각각 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 이다. 각각의 음정을 재생하는 데에는 1분이 걸리며 재생시간 동안 멜로디는 반복재생된다. 즉, 멜로디가 DGG#이고 7분 동안 재생되었으면 재생된 음악은 DGG#DGG#D이다. 내가 듣고 기억한 멜로디가 주어졌을 때 해당 멜로디를 포함된 음악을 찾으면 된다. 예를 들어 직전의 예시에서 G#DGG#을 들었으면 해당 음악은 내가 들은 멜로디를 포함한 것이다. 이 때 만족하는 음악이 여러개 있을 경우 지

📌 Problem 주어지는 정수 배열에서 인덱스는 시간을 원소는 주식의 가격을 의미한다. 각 시간별로 주식 가격이 떨어지지 않는 시간을 구하면 된다. 📌 Code Stack Queue

📌 Problem 두 개의 문자열이 주어졌을 때 자카드 유사도를 구한 값에 65536를 곱한 정수 부분을 반환하면 된다. 이때 자카드 유사도로 사용할 원소는 문자열을 2개의 문자씩 끊은 것이다. 알파벳 이외의 문자가 있는 원소는 제외하며 대소문자는 구별하지 않는다. 자카드 유사도는 교집합 개수 / 합집합 개수이며 합집합이 없을 경우 1이 된다. 📌 Solution Map 자료구조를 사용하여 간단하게 구할 수 있다. String은 문자열의 2 길의 부분 문자열이면 Integer은 해당 부분 문자열의 개수이다. 각 문자열에 대한 map을 생성할 후 교집합의 개수와 합집합의 개수를 구한다. 교집합 두 문자열 집합에 모두 포함된 원소 중에서 더 적은 값을 더한다. 예를 들어 두 문자열 집합에 문자열 "AB"가 있는데

📌 Problem 경기에는 총 N명의 참가자가 있으며 토너먼트 방식으로 경기가 진행된다. 1, 2번 선수, 3, 4번 선수 ... n-1, n번 선수가 짝을 이루어 경기를 치루고 이긴 사람이 다음 라운드로 나간다. 다음 라운드에서는 1, 2번 중 이긴 선수와 3, 4번 중 이긴 선수가 짝을 이루어 경기를 치룬다. 이런 방식으로 경기가 진행될 때 a번 선수와 b번 선수가 몇 번째 라운드에서 짝을 이루어 경기를 치룰 수 있는지 구하면 된다. 이때 a와 b는 둘이 경기를 치루기 전까지 무조건 이긴다고 가정한다. 📌 Solution N번째 선수가 경기에서 이기면 다음으로는 (N + 1) / 2 번째 선수가 되어 다음 라운드를 진행한다. 이를 이용하여 a와 b 선수의 다음 라운드 번호를 계산한다. 또한 한 라운드에서 두 선수가 붙기 위해서는 두 선수의 번

📌 Problem 문자열이 주어졌을 때 같은 문자가 붙어 있는 경우에는 제거한다. 예를 들어 baab인 경우는 aa가 짝지어지기 때문에 제거되어 bb가 된다. bb 또한 다시 짝지어지기 때문에 제거된다. 이렇게 모든 문자열이 짝지어져서 제거되면 1을 출력되고 아니면 0이 된다. 📌 Solution 문자열의 앞 문자부터 차례대로 탐색하면서 Stack에 삽입된다. 만약 Stack의 top과 현재 문자가 같다면 stack을 pop한다. 만약 stack이 비어있거나 top과 다른 문자이면 push한다. 마지막에 stack의 크기를 통해 문자열을 모두 제거하였는지 확인한다. 📌 [Code](https://github.com/codesver/problem-solving-hub/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%E

📌 Problem Excel에서 주어진 명령어 UPDATE, MERGE, UNMERGE, PRINT 작업을 수행하고 PRINT를 통해 출력되는 값들을 String 배열로 반환하면 된다. Update A - 주어진 R, C 위치의 cell value를 VALUE로 수정하면 된다. Update B - 주어진 VALUEA를 가진 cell들의 value를 VALUEB로 수정하면 된다. Merge - 두 cell을 병합하면 된다. 이 때 첫 번째 cell이 값을 가지고 있으면 해당 값으로 아니면 두 번째 cell 값으로 한다. Unmerge - 주어진 cell에 병합된 모든 cell을 해제한다. 주어진 cell 위치는 값을 유지하고 나머지 cell은 값을 초기화한다. Print - 주어진 cell의 값을 출력한다. 만약 값을 가지고 있지 않다면 EMPTY를 출

📌 Problem 주어진 배열에 있는 long 타입 정수들을 포화 이진 트리로 나타낼 수 있는지를 확인하면 된다. 정수를 이진수로 나타냈을 때 1은 node가 있는 위치이며 0은 포화 이진 트리를 만들기 위해 기존 트리에 0이라는 더미 node를 붙인 곳이다. 또한 이진수는 트리를 왼쪽부터 읽은 값이다. 📌 Solution 우선 주어진 정수를 이진수로 변환해야 한다. 이때 이진 트리의 높이에 따라 이진수의 왼쪽에 0을 붙여야 한다. 예를 들어 63이라는 정수를 이진수로 바꾸면 111111이다. 이진수의 길이에 맞는 트리의 최소 높이는 3이다. 높이가 3인 포화 이진 트리의 노드 수는 7이지만 이진수 111111은 길이가 6이기 때문에 그 차이인 1만큼 0을 왼쪽에 붙여서 0111111을 만든다. 이 때부터는 포화 이진 트리인지를 확인하면 된

📌 Problem 공원은 O와 X으로 이루어진 R x C 크기의 2차원 배열 형태이다. O는 지나다닐 수 있는 공간이고 X는 장애물이어서 지나다닐 수 없다. 특정 위치 S에 로복 개를 두고 명령을 입력하여 이동한다. 공원과 로봇 개의 정보, 그리고 명령들이 주어졌을 때 로봇 개의 최종적인 위치를 출력하면된다. 각각의 명령은 방향(N E S W)과 거리(1 ~ 9)으로 이루어져 있다. 명령을 실행했을 때 공원 밖으로 나가거나 중간에 장애물(X)를 만나면 해당 명령은 실행하지 않는다. 📌 [Code](https://github.com/codesver/problem-solving-hub/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/unrated/172928.%E2%80%85%

Link | 프로그래머스 86052번 문제 : 빛의 경로 사이클 📌 About 그래프 탐색 문제이다. 모든 격자를 탐색하며 방향을 잡고 사이클의 길이를 측정하면 된다. 이동 방향은 다음과 같다. 이를 배열로 나타나면 다음과 같다. 각각의 사이클 탐색에 있어서 이동 방향 D를 TILT 방향에 따라 바꾼다. 바뀐 이동 방향 D에 맞게 다음 격자의 R과 C를 바꾼다. 이미 이동한 통로(격자와 격자 사이)가 나오면 이는 사이클이 생성된 것이다. 이를 바탕으로 해결하면 된다. 📌 Solution Step 1. 필요한 자료구조를 정의한다. Step

Link 프로그래머스 87946번 문제 : 피로도 📌 About Dungeons의 길이가 8 이하이기 때문에 brute force으로 해결할 수 있다. 또한 던전의 탐험 여부를 백트래킹으로 변경해야 한다. 📌 Code

Link | 프로그래머스 92342번 문제 : 양궁대회 📌 About 점수의 개수의 11개이기 때문에 brute force으로 풀 수 있다. 백트래킹으로 10점부터 차례대로 탐색하면 된다. 📌 Solution 탐색을 할 때 이전 탐색 이후의 점수부터 탐색하면 된다. 만약 7번까지 탐색을 했다면 다음 탐색은 6번부터하면 된다. 만약 남은 화살이 peach가 맞춘 화살의 수보다 많으면 lion은 해당 점수에 한 개 더 명중한다. 백트래킹이기 때문에 재귀이후에는 다시 화살을 해당 점수에서 회수한다. 만약 화살의 개수가 0개라면 더 쏠 수 없기 때문에 최종 연산을 한다. (compare) 만약 화살이 남아있다면 다음 점수를 탐색한다. 최종 연산은 다음과 같다. 지금까지 계산한 최대 점수 차이보다 현재 점수 차이가 작다면

Link | 프로그래머스 140107번 문제 : 점 찍기 📌 About Brute force으로 각각의 점의 좌표를 구하는 방법도 있다. 하지만 k = 1, d = 1,000,000이면 최대 $1,000,000^2$ 의 연산을 해야 한다. 때문에 최대 1,000,000의 연산으로 끝낼 수 있어야 한다. 📌 Solution X 좌표만을 보면 0, k, 2k, 3k, 4k... (x ≦ d) 가 되는 것을 알 수 있다. 각각의 X 좌표에 대해 $x^2 + y^2 ≦ d^2$ 인 최대 y값을 구하면 된다. 이를 code으로 표현하면 다음과 같다. 이 때 Y값 또한 k씩 늘어나므로 Y / k + 1 을 하면 X에 대한 점의 개수를 구할 수 있다. 위의 식을 바탕으로 X 값 마다의 Y 개수를 구하여 전체합을 반환해주면 된다