문제번역2차원 정수 배열 intervals가 주어진다. intervals의 각 원소는 \( [ left_i, right_i ] \) 로 구성된다.이 intervals를 하나 이상의 그룹으로 나눠서 각 그룹마다 교집합이 없게 만들어야 한다.이때 우리가 만들 수 있는 최소한의 그룹의 수를 반환해라[1, 5] , [5, 8] 과 같이 하나의 수라도 겹치면 겹친다고 판단한다.접근 방법과 소스코드특정 시점에 동시에 겹치는 구간의 최대 개수를 구하면 된다.어떤 interval의 시작시간이 다른 interval의 끝나는 시간보다 크면 어떤 구간이 끝난 것이므로 그룹을 재사용할 수 있다.그게 아니라면 새로운 그룹이 필요한 경우이다. 이를 해결하기 위해 시작 시간과 끝나는 시간을 각각 정렬한 뒤 투포인터를 통해서 문제를..

문제번역events 배열이 주어지고 events 배열의 각 원소는 [startDay_i, endDay_i]로 이루어져 있다.각 이벤트 i 는 startDay_i 날에 시작해서 endDay_i 날에 끝난다.우리는 이벤트가 열리는 날 중 하루만 참석할 수 있다. 이벤트는 하루에 한번만 참여할 수 있다.우리가 참석 가능한 이벤트의 최대 개수를 반환해라. 접근 방법과 소스코드그리디와 MinHeap을 써서 오늘 참석 가능한 이벤트 중 가장 빨리 끝나는 이벤트에 참석하면 된다.늦게 끝나는 이벤트는 나중에 참석할 수 있기에 빨리 끝나는 이벤트를 우선해서 고른다. 오늘 시작하는 이벤트를 MinHeap에 전부 넣는다. 그리고 오늘 이전에 끝난, 즉 내가 더이상 참석하지 못하는 이벤트는 전부 날린다.그 중 가장 빨리 끝나..

문제번역정수 배열 nums와 정수 k가 주어질때, array에서 k번째로 가장 큰 원소를 반환해라.k번째 수는 정렬된 순서에서 k번째로 큰 수를 말하며, k번째의 구별되는 원소가 아니다. 정렬없이 구현해라.접근 방법과 소스코드대표적인 maxheap을 사용하는 문제이다.입력받은 수로 maxheap을 구성한다. 그러면 heap의 root는 첫번째로 가장 큰 수가 있을 것이다.이걸 k-1번 만큼 heap에서 pop을 하면 maxheap의 root는 k번째로 가장 큰 수가 담겨 있을 것이다.우린 이걸 pop 해서 반환해주면 된다. int heap[100001];int rsp = 0;void swap(int* a, int* b) { int t = *a; *a= *b; *b = t;}void pus..

문제번역ugly number는 소인수를 2,3,5만 갖고 있는 양수를 말한다.정수 n이 주어졌을 때, n번째 ugly number를 반환해라.접근 방법 및 소스 코드처음엔 기존 ugly number를 구하는 코드를 그대로 활용하여 n번째 ugly number를 구했다. int dp[1691];bool isUgly(int n) { while(n%2==0) n/=2; while(n%3==0) n/=3; while(n%5==0) n/=5; return n==1;}int nthUglyNumber(int n) { dp[0] = 0; dp[1]=1; dp[2]=2; dp[3]=3; dp[4]=4; int i=5,j=5; while(i 이렇게 작성하고 제출하니 timeou..

문제번역게임에 참여하는 친구가 n명 있다. 이 친구들은 원형으로 앉아서 1번부터 n번까지 시계방향 순서로 번호를 부여받는다.좀 더 정확하게, i번째에서 시계 방향으로 이동하면 i+1 번째 친구에게 가게 되고, n번째 친구는 1번 친구에게 다시 가게 된다. 게임의 룰은 아래와 같다.1. 1번 친구부터 시작한다.2. 시작한 친구를 포함해서, 시계방향으로 다음 k명의 친구를 센다 원을 따라서 계속 세므로 한바퀴를 넘어가거나 두번 이상 셀 수 도 있다.3. 마지막으로 센 친구가 원에서 빠지고 게임에서 진다.4. 여전히 1명보다 많은 친구가 원에 있으면 2번부터 다시 수행한다.5. 그렇지 않으면 마지막으로 남은 친구가 게임에서 이긴다. n명의 친구가 주어지고, k 정수가 주어졌을 때 게임의 승자를 구해라.접근 방..

문제번역배열의 XOR Total 이라는 것은 배열의 모든 원소에 대해 XOR을 한 것을 말합니다. 만약 배열이 비어있다면 XOR Total은 0이 됩니다. nums라는 정수 배열이 주어졌을 때, nums의 모든 부분 배열의 XOR Total의 합을 반환해라.- 동일한 원소를 가진 부분배열은 동시에 카운트될 수 있습니다. 접근 방법 및 소스 코드입력의 길이를 \(n\)이라고 하자.그러면 subset은 총 \(2^n\) 개가 생긴다. 즉, 각 원소마다 선택지가 2개가 생긴다.해당 원소를 집어넣으면 기존 값과 xor을 하고, 해당 원소를 집어넣지 않으면 기존 값을 그대로 가져간다.이를 그냥 재귀로 돌려주고 더해주면 끝이다.물론 종료조건은 배열의 끝까지 가면 xor을 반환해주면 된다. int recursive(..

문제번역n개의 음이 아닌 정수 배열이 주어지고, 이 배열은 elevation map(지형 높이 배열, 고도 지도..)로 주어지고, 가로폭은 1이다.이때, 비가 오고 난 뒤 얼마나 많은 물을 가둘 수 있는지 계산해라.접근 방법 및 소스 코드일단 한 칸에 고일 수 있는 물의 양은 min ( leftMax, rightMax ) - height[i]이다.이를 각 칸에서부터 계산하면 \(O(n^2)\) 의 시간복잡도가 나온다. 조금 더 효율적인 방법은 없을까? 물론 있다 그러니 문제를 냈겠지 양 끝에서 시작하는 l 포인터와 r 포인터가 있다고 하자.그 포인터는 height 배열의 높이를 가리킨다. 두 값중 하나는 상대보다 낮을 것이다. ( 같을 수도 있겠지만 )아무튼, 낮은 쪽은 반대편에 나보다 높은 벽이 있으니..

문제번역높이 n을 갖는 정수 배열 height가 주어졌다. n개의 수직선이 그려져 있고, i번째 선은 (i, 0) 부터 (i, height[i]) 까지 그려져 있다.이 수직선들 중 2개를 골라서 x축과 함께 하나의 컨테이너를 만들때 가장 많은 물을 담을 수 있는 경우의 수를 구하여라.단 컨테이너를 기울일 수는 없다. 접근 방법 및 소스 코드그림을 보고 직관적으로 생각했다.양 끝 점에서 시작해서 막대를 움직여가며 가장 많은 물을 담을 수 있을 때의 물을 저장하면 될 것 같았다. 이를 위해 투포인터 기법을 사용했다.초기에 i = 0 , j = n-1로 세팅하고 \(min(height[i], height[j]) * (j-i)\) 로 현재 컨테이너의 용량을 재고 매번 갱신했다.그리고 포인터를 움직일때는 더 낮은..

문제번역nums 라는 정수 배열과 정수 k가 주어졌을때, 부분배열의 모든 원소의 곱이 k보다 작은 부분배열의 개수를 반환해라.접근 방법 및 소스 코드투 포인터를 사용하면 된다.i를 0부터 numsSize-1까지 반복하면서 i에 해당하는 인덱스를 곱셈의 시작점으로 쓴다.포인터 j를 한칸씩 뒤로 가면서 곱해본다. 이때, 곱한 값이 k보다 작은지 매번 검사하면서 곱한다.그래서 가능한 가장 큰 j를 구한 뒤, counter에 해당 부분배열 길이 만큼 다시 더해준다.그 다음 i를 한칸 밀고, 기존에 곱했던 값에서 배열의 i번째의 값만큼 다시 나눠준다.그리고 j를 또 한칸씩 뒤로 가면서 곱해본다... 이를 끝까지 반복한다. int numSubarrayProductLessThanK(int* nums, int nums..

문제 번역주어진 정수 배열 heights는 히스토그램 막대의 높이를 나타낸다.각 막대의 가로폭이 1일때, 히스토그램에서 가장 큰 직사각형을 구해라. 접근 방법 및 소스코드토픽을 보니 단조증가스택을 사용하면 된다고 한다.기존 막대보다 높거나 같은 길이의 막대가 들어오면 스택에 인덱스와 함께 쌓아둔다. 그러다가 스택에 있는 막대보다 작은 막대가 들어오면 스택에서 pop을 해서 가로 길이와 높이를 구하고, 기존 최대 넓이보다 넓은지 갱신한다.int max(int a, int b) { return (a = stk[rsp]) { stk[++rsp] = heights[i]; stk[rsp] = heights[i]; stk_idx[rsp] = i; ..