n개의 좌석에 대한 예약 상태를 관리하는 시스템을 설계해야 한다고 가정해 봅시다. 좌석은 1번부터 n번까지 번호가 매겨져 있으며, 우리는 다음과 같은 기능을 제공하는 SeatReserveManager 클래스를 구현해야 합니다.생성자(__init__) : n을 입력으로 받아 1부터 n까지 번호가 매겨진 n개의 좌석을 관리하는 객체를 초기화합니다. 초기 상태에서는 모든 좌석이 비어 있어 예약 가능합니다.reserve() : 아직 예약되지 않은 좌석 중 가장 번호가 작은 좌석을 찾아 예약하고, 그 좌석 번호를 반환합니다.unreserve

문제 설명 배열 arr가 주어졌다고 가정해 봅시다. 우리는 arr에 몇 가지 연산을 수행하여 아래 조건들을 만족하도록 만들어야 합니다. arr의 첫 번째 요소는 반드시 1이어야 합니다. 인접한 두 요소 간의 절댓값 차이는 최대 1 이하여야 합니다. 이를 위해 사용할 수 있는 두 가지 연산이 있으며, 각 연산은 원하는 만큼 여러 번 수행할 수 있습니다. arr의 임의의 값을 더 작은 양수로 감소시킵니다. arr의 요소들을 임의의 순서로 재배열합니다. 목표는 위 조건들을 만족하도록 연산을 수행한 뒤, 배열에서 가능한 최댓값을 구

문제 개요숫자로만 구성된 문자열 s가 주어졌다고 가정해 보겠습니다. 이때 s를 두 개 이상의 비어 있지 않은 부분 문자열로 분할하되, 각 부분 문자열의 숫자 값이 내림차순을 이루고 인접한 두 값의 차이가 정확히 1이 되도록 할 수 있는지 확인해야 합니다.예를 들어 문자열이 s = 0080079라면 [0080, 079]로 분할할 수 있으며, 각 부분의 숫자 값은 [80, 79]가 됩니다. 값이 내림차순으로 배치되어 있고 인접한 값의 차이가 1이므로 이 분할은 유효합니다. 우리가 확인해야 할 것은 s를 위와 같은 조건에 맞게 분할하는

문제 설명두 개의 비증가(내림차순) 배열 nums1과 nums2가 주어졌다고 가정해 봅시다. 인덱스 쌍 (i, j)은 다음 조건을 모두 만족할 때 유효한(valid) 쌍이라고 정의됩니다.0 ≤ i < nums1의 길이0 ≤ j < nums2의 길이i ≤ jnums1[i] ≤ nums2[j]유효한 쌍의 거리는 (j − i)로 계산하며, 우리는 모든 유효한 쌍 중에서 최대 거리를 찾아야 합니다. 만약 유효한 쌍이 하나도 존재하지 않는다면 0을 반환합니다.예를 들어 입력이 nums1 = [60, 40, 15, 10, 5], n

문제 이해하기배열 nums가 주어졌을 때, 비어 있지 않은 모든 부분 배열(subarray) 중에서 최소 곱(min-product)이 가장 큰 값을 찾아야 합니다. 결과값이 매우 커질 수 있으므로 10^9+7로 나눈 나머지를 반환합니다.여기서 최소 곱이란 배열 안의 최솟값 × 배열 전체의 합을 의미합니다. 예를 들어 배열이 [4, 3, 6]이라면 최솟값은 3이고, 최소 곱은 다음과 같이 계산됩니다.3 × (4 + 3 + 6) = 3 × 13 = 39입력 예시nums = [2, 3, 4, 3]이 주어진 경우 출력은 30입니다. 부분

문제 이해하기n개의 사탕과 k개의 가방이 있다고 가정해 보겠습니다. 우리가 구해야 할 값은 모든 가방에 최소 한 개 이상의 사탕이 들어가도록 사탕을 분배할 수 있는 방법의 총 개수입니다. 여기서 중요한 전제는 모든 사탕이 서로 다르다는 점입니다. 따라서 어떤 사탕이 어느 가방에 들어가느냐에 따라 달라지는 모든 조합을 빠짐없이 세어야 합니다.예를 들어 입력이 n = 3, k = 2라고 하면, 출력은 3이 됩니다.사탕을 나눌 수 있는 방법은 다음과 같습니다.(1, 2), (3)(1), (2, 3)(2), (1, 3)해결 접근 방식이 문

문제 개요 크기가 n인 배열 nums에 양의 정수들이 들어 있다고 가정해 보겠습니다. 그리고 정수 쌍 (pi, qi)를 담고 있는 또 다른 배열 queries가 주어집니다. queries 배열의 각 쿼리에 대한 답은, pi <= j < n이면서 (j - pi)가 qi로 나누어 떨어지는 모든 nums[j] 값들의 합입니다. 모든 쿼리에 대한 답을 반환해야 하며, 계산 결과가 너무 커질 경우에는 10^9 + 7로 나눈 나머지를 반환합니다. 예를 들어, 입력이 다음과 같다고 해보겠습니다. nums = [2, 3, 4, 5, 6

시작점 (sx, sy)와 목표점 (tx, ty)가 주어졌을 때, 시작점에서 목표점까지 도달하는 일련의 이동이 존재하는지 확인해야 합니다. 여기서 각 이동은 점 (x, y)를 (x, x+y) 또는 (x+y, y)로 변형하는 것을 의미합니다.예를 들어 입력이 (sx, sy) = (1,1), (tx, ty) = (4,5)라면 출력은 True가 됩니다. 그 이유는 (1,1) → (2,1) → (3,1) → (4,1) → (4,5) 순서로 이동할 수 있기 때문입니다.문제 해결 접근 방식이 문제는 재귀적으로 해결할 수 있으며, 다음 단계를 따

문제 설명 두 개의 문자열 s와 t가 주어졌을 때, 다음과 같은 방식으로 새로운 문자열을 만들려고 합니다. s에서 비어 있지 않은(non-empty) 부분 수열 sub1을 선택합니다. t에서 비어 있지 않은 부분 수열 sub2를 선택합니다. sub1과 sub2를 이어 붙여 하나의 문자열을 완성합니다. 이때 만들 수 있는 가장 긴 회문(palindrome)의 길이를 구하는 것이 목표입니다. 어떤 회문도 만들 수 없다면 0을 반환합니다. 예를 들어 s = hillrace, t = cargame이라면 정답은 7입니다. s에서 race

문제 이해하기가중치가 부여된 무방향 그래프(undirected graph)가 주어졌다고 가정해 보겠습니다. 우리는 두 개의 정점과 비용 상한값 limit을 입력으로 받아, 해당 비용 이하의 비용으로 두 정점을 연결하는 경로가 존재하는지 확인하는 query() 함수를 구현해야 합니다. 경로가 존재하면 True를, 존재하지 않으면 False를 반환합니다.예제다음과 같은 그래프가 있다고 가정합니다.쿼리가 (0, 2, 10), (3, 1, 30), (4, 3, 30)일 때 출력 결과는 다음과 같습니다.False True True첫 번째 쿼

배열 nums가 주어졌을 때, 이 배열을 여러 개의 구간(파티션)으로 나누고 각 구간을 개별적으로 정렬한 뒤 다시 이어 붙였을 때 전체가 오름차순으로 정렬된 배열이 되도록 해야 합니다. 우리가 구해야 할 것은 바로 만들 수 있는 파티션의 최대 개수입니다.예를 들어 입력이 [3,2,4,5,5]라면 결과는 4가 됩니다. [3,2], [4], [5], [5]처럼 네 개의 구간으로 나누면, 각 구간을 정렬해 이어 붙였을 때 [2,3,4,5,5]라는 완전히 정렬된 배열을 얻을 수 있기 때문입니다.문제 풀이 접근 방법핵심 아이디어는 현재 잘라

문제 이해하기하나의 문자열 text가 주어졌을 때, 다음 조건을 모두 만족하는 가장 큰 정수 k를 찾는 것이 목표입니다.각 a[i]는 비어 있지 않은(non-blank) 문자열이어야 합니다.모든 조각을 이어 붙인 a[1] + a[2] + ... + a[k]가 원래 문자열 text와 정확히 일치해야 합니다.모든 i(1 ≤ i ≤ k)에 대해 a[i] = a[k+1-i], 즉 앞에서 i번째 조각과 뒤에서 i번째 조각이 서로 같아야 합니다.예를 들어 입력이 text = antaprezatepzapreanta라면 출력은 11입니다. 아래와

문제 소개배열 nums와 정수 k가 주어져 있다고 가정해 보겠습니다. 세그먼트 [left, right](단, left ≤ right)의 XOR이란 해당 범위에 포함된 인덱스의 모든 요소를 순서대로 XOR한 값을 의미합니다.목표는 크기가 k인 모든 세그먼트의 XOR이 0이 되도록 배열에서 변경해야 하는 요소의 최소 개수를 구하는 것입니다.예를 들어 입력이 nums = [3,4,5,2,1,7,3,4,7], k = 3이라면 정답은 3입니다. 인덱스 2, 3, 4의 요소를 수정해 배열을 [3,4,7,3,4,7,3,4,7] 형태로 만들면,

문제 설명배열 nums와 값 k가 주어집니다. 이때 하위 배열(subarray) (i, j)의 점수는 다음과 같이 정의됩니다.score(i, j) = min(nums[i..j]) × (j − i + 1)여기서 좋은(good) 하위 배열은 시작 인덱스와 끝 인덱스 사이에 k가 포함되는, 즉 i <= k <= j를 만족하는 하위 배열을 뜻합니다. 목표는 좋은 하위 배열 중에서 얻을 수 있는 최대 점수를 구하는 것입니다.예시입력이 nums = [2,5,4,8,5,6], k = 3인 경우를 살펴보겠습니다. 최적의 하위 배열은 (

문제 개요 n개의 정수로 이루어진 배열 nums가 있다고 가정해 보겠습니다. 배열의 각 값은 해당 요소 고유의 파워(power)를 나타냅니다. 이 배열은 아래 두 조건을 동시에 만족할 때 유효(valid)하다고 정의합니다. 배열의 길이가 2보다 커야 합니다. 배열의 첫 번째 값과 마지막 값이 서로 같아야 합니다. 우리는 배열에서 요소를 삭제하여 이 조건을 만족하는 유효한 배열을 만들어야 하며, 그 결과 남은 요소들의 파워 값을 모두 더했을 때 얻을 수 있는 최댓값을 반환해야 합니다. 예를 들어 입력이 nums = [3, 4,

문제 설명크기가 2×n인 배열 nums가 주어집니다. 우리는 이 배열에 대해 정확히 n번의 연산을 수행해야 하며, i번째 연산(1부터 시작하는 인덱스)에서는 다음과 같은 작업을 진행합니다.배열에서 두 개의 원소 x와 y를 선택합니다.i × gcd(x, y) 만큼의 점수를 획득합니다. 여기서 gcd는 최대공약수를 의미합니다.선택한 두 원소 x와 y를 배열에서 제거합니다.n번의 연산을 모두 수행한 후 얻을 수 있는 최대 점수를 구하는 것이 목표입니다.예를 들어, 입력이 nums = [6,2,1,5,4,3]이라면 출력은 14가 됩니다.

문제 설명배열 nums와 두 값 l, r이 주어졌을 때, 좋은 쌍(nice pair)의 개수를 구하는 프로그램을 만들어 보겠습니다. 여기서 좋은 쌍이란 인덱스 쌍 (i, j) 중에서 0 <= i < j < len(nums)이고, l <= (nums[i] XOR nums[j]) <= r 조건을 만족하는 쌍을 의미합니다.예를 들어 입력이 nums = [4, 1, 7, 2], l = 2, r = 6이라면 출력은 6이 됩니다. 조건을 만족하는 좋은 쌍은 다음과 같습니다.(0, 1): 4 XOR 1 = 5(0, 2

문제 설명소인수의 개수를 나타내는 값 pf가 주어질 때, 다음 조건을 만족하는 양의 정수 n을 만들어야 합니다.조건 1: n의 소인수 개수(중복 허용)는 pf 이하이어야 합니다.조건 2: n의 좋은 약수(nice divisor) 개수가 최대가 되어야 합니다. 여기서 좋은 약수란 n의 모든 소인수로 나누어떨어지는 약수를 의미합니다.목표는 n의 좋은 약수 개수를 구하는 것이며, 결과가 너무 클 경우에는 109 + 7로 나눈 나머지를 반환합니다.예제로 이해하기pf = 5인 경우를 생각해 보겠습니다. n = 200으로 두면 소인수는 [2,

문제 설명 batchSize 값과 배열 groups가 주어진다고 가정해 봅시다. 여기서 groups[i]는 groups[i]명의 손님으로 이루어진 그룹이 가게를 방문한다는 의미입니다. 어떤 도넛 가게는 지정된 batchSize만큼씩 도넛을 만들며, 한 가지 규칙이 있습니다. 바로 현재 배치의 도넛을 모두 판매하기 전에는 다음 배치의 도넛을 판매할 수 없다는 것입니다. 또한 각 손님은 정확히 도넛 하나씩을 받게 됩니다. 한 그룹이 가게에 들어오면 다음 그룹을 응대하기 전에 해당 그룹의 모든 손님에게 도넛을 제공해야 합니다. 그리고 그

문제 설명양수로만 이루어진 배열 nums가 주어졌다고 가정해 보겠습니다. 우리가 구해야 할 것은 nums의 모든 비어 있지 않은 부분 수열(subsequence)에서 만들어질 수 있는 서로 다른 GCD(최대공약수)의 개수입니다.여기서 수열의 GCD란, 해당 수열의 모든 숫자를 나머지 없이 나누어 떨어지게 하는 가장 큰 값을 의미합니다.입력 예시nums = [4, 6, 18]출력 결과4그 이유는 다음과 같습니다.gcd([4]) = 4gcd([6]) = 6gcd([18]) = 18gcd([4, 6]) = 2gcd([4, 18]) = 2