문제번역0-index 를 사용하는 정수 배열 nums가 주어진다.부분 배열 \((i, j)\)의 score는 \(min(subarray) * (j-i+1)\) 로 정의된다.좋은 부분배열은 k가 i 이상 j 이하일때 이다.좋은 부분배열의 점수의 최대값을 반환해라.접근 방법 및 소스 코드일단 부분 배열에 k가 반드시 들어가야 하니 k부터 시작하는게 좋을 것이다.k를 기준으로 왼쪽과 오른쪽으로 한칸씩 늘려가면서 현재 최대 점수와 비교하면서 최대점수를 늘리는지 줄이는지 찾아야 한다.왼쪽으로 가는것과 오른쪽으로 가는것을 비교해서 더 큰 값을 갖는 쪽으로 일단 늘려본다.늘렸을때 점수가 지금 점수보다 높다면 업데이트를 한다. 이러한 방식으로 양쪽 끝까지 다 탐색해봐야 한다. int maximumScore(int* n..

문제번역arr 배열을 mountain array라고 부르려면 다음 조건을 만족해야 한다.1. 배열의 길이가 3 이상이어야 하고2. 어떤 인덱스 i에 대해서 0번 원소부터 i번 원소까지 단조 증가해야 하며3. i번 인덱스부터 배열의 끝까지 단조 감소해야 한다. 주어진 정수 배열 arr에서 가장 긴 mountain 부분 배열의 길이를 반환하고, 없다면 0을 반환해라.접근 방법과 소스코드처음에는 매 인덱스마다 검사하는 로직을 작성했다. 현재 인덱스 \(i\)에 도착했을때, 포인터 \(l\)은 왼쪽으로 내려가면서 \(l\)부터 \(i\)까지 단조 증가하는지 검사하고,포인터 \(r\)은 오른쪽으로 올라가면서 \(i\)부터 \(r\)까지 단조 감소하는지 검사한다.포인터가 최대한 단조 증가/감소하는 위치까지 내려가게..

문제(원문)문제(번역)정수 n이 주어질때, 정수 n보다 작은 소수의 개수를 구해라.접근 방법소수 구하는 문제는 거의 에라토스테네스의 체를 활용하면 된다.에라토스테네스의 체란 2부터 시작해서 각 소수의 배수를 차례대로 지워가면서 소수만 남기는 방식이다.어떤 수 i가 소수이면 i의 배수는 전부 합성수가 되기 때문이다. 보통 \(i^2\) 부터 지우면 이미 처리된 수를 건너 뛰게 되어 더 효율적이다. 해당 문제에서도 에라토스테네스의 체를 활용했다. 메모리 사용량을 더 줄이기 위해 동적할당을 사용해 체에 필요한 리스트를 할당했다. 소스 코드int countPrimes(int n) { if(n

문제(원문) 문제(번역)양수가 담긴 배열 nums와 양의 정수 target이 주어진다.이때 subarray의 합이 target보다 크거나 같은 subarray의 최소 길이를 반환해라.적절한 subarray가 존재하지 않는다면 대신 0을 반환해라. 접근 방법처음에는 감이 잡히지 않아 해당 문제의 주제를 보니 슬라이딩 윈도우가 있다.슬라이딩 윈도우란 배열이나 문자열에서 연속된 구간을 잡아두고, 그 구간을 한칸씩 밀면서 원하는 조건을 찾는 기법이라고 한다. 현재 구간의 합이 target보다 작으면 오른쪽으로 한칸을 늘린다.만약 현재 구간의 합이 target 보다 크거나 같다면 최소 길이인지 확인 후 갱신한다. 그리고 target보다 작아질때까지 구간을 왼쪽에서 한칸 당겨서 줄여본다. 그리고 다시 조건을 만족하..

문제(원문)문제(번역)주어진 Linked List head가 있을때, 뒤에서 부터 n번째 노드를 삭제해라.단 Linked List 는 단방향이다. 이 문제를 1번에 풀 수 있는가?접근 방법Two pointer 기법을 사용하면 된다.현재 노드를 가리키는 포인터와 n만큼 앞서가는 포인터를 두고 사용하면 된다.앞서가는 포인터가 마지막 노드라면, 현재 노드가 자연스레 삭제될 노드가 되기 때문이다.이와 함께 현재의 이전 노드를 저장할 포인터도 필요하다. 앞서가는 포인터가 마지막 노드에 도착했을때 현재 삭제할 노드가 중간에 있는 노드인지, head 원소인지 확인해야 한다.우리는 원본 리스트를 그대로 반환할 것이기 때문에, head 노드가 삭제 대상이라면 head 노드를 head->next로 바꾸어주어야 한다.삭제할..

문제(원문) 문제(번역)비어있지 않으면서 음수가 아닌 두 linked list가 주어진다. 이 수들은 역순으로 정렬되어 있고, 각 노드는 하나의 숫자만 갖고 있다.이둘을 더한 linked list를 반환해라.단, 이 linked list에는 0인 경우를 제외하고 앞에 0이 들어있지 않다. 접근 방법그냥 Linked List를 순회하면서 수를 더하되, 10을 넘어가면 그 수를 다음에 보내서 더해주는 로직만 잘 작성하면 된다.하지만 Linked List를 할당하는 것과 Null 처리하는 부분을 조심하지 않으면 쉽게 에러가 난다. 소스 코드int safeGet(struct ListNode* l) { if(l == NULL) return 0; return l->val;}struct ListNode* ..

문제(원문)문제(번역)정렬되지 않은 정수 배열 nums가 주어진다. 이때 nums에 없는 가장 작은 양의 정수를 반환해라.반드시 반드시 반드시 O(n)의 시간복잡도를 가지면서 O(1)의 공간복잡도를 갖는 알고리즘을 구현해라.접근 방법처음에 보자마자 떠오른 생각은 단순하게 배열을 만들어서 flag 형식으로 수가 나왔는지 확인하려 했다. 그러나 수의 범위가 매우 크고 무엇보다 위에 O(1) // 추가적인 선형 배열 없이 구현하라고 나와있었다. 비상이다.감이 잡히지 않아 AI에게 힌트를 달라고 했다.AI 왈 입력 배열 자체를 값의 존재 여부를 표현하는 구조로 쓰라고 한다. 즉 입력받은 배열을 순회하면서 계속해서 해당 원소를 해당 원소의 인덱스로 보내버리면 된다.배열 순회가 끝나면 다시 배열을 순회하면서 i자..

문제(원문) 문제(번역)음이 아닌 정수가 담긴 문자열 num과 숫자 k가 주어질 때, num에서 k개의 숫자를 지웠을 때 가능한 가장 작은 수가 나오게 해라.접근 방법주제를 보니 이 문제는 Monotonic Stack에 속해 있다. 이걸 보니 러프하게 솔루션이 생각났다.해당 스택을 증가하게끔 만들면 작은 수를 만들 수 있을 것 같았다.num 문자열을 순회하면서 스택에 있는 수보다 지금 수가 더 작으면 감소하고 있는 상황이므로 지금 수보다 큰 스택에 있는 수를 제거해낸다.그러고 지금 수를 넣으면 되지 않을까 싶었다. 일단 전체적인 방향성은 맞았는데 고려해야 하는 부분이 더 있었다. 수를 삭제하는 횟수는 k번이다.문자열을 순회하면서 수를 삭제할 때 k를 감소시켜야 하고, 순회 이후에 k가 남아있으면 뒤에서부..

문제 (원문)문제(번역)n개의 주유소가 원형 길을 따라 있다. i 번째 주요소에서의 가스 양은 gas[i]이다.무한대의 가스 탱크를 가진 차가 있고, i번째 주유소에서 i+1번째 주유소로 가는 가스 비용은 cost[i]이다. 아무 주유소에서부터 빈 탱크로 여정을 시작해야 한다.gas와 cost 두 정수 배열이 주어졌을 때 시계방향으로 여행을 갈 수 있는 주유소의 인덱스를 반환해라.해답이 있다면 그 해답이 유일하다는 것이 보장된다.접근 방법처음에는 단순하게 생각했다.gas[i]-cost[i]를 한 값이 0보다 크거나 같은 위치를 먼저 모은 다음,각 위치에서부터 시계방향으로 순회하여 자기 자신까지 도착할때까지 가스 탱크가 음수가 되지 않는지 검사했다.이렇게 풀이하는 경우 시간 초과가 발생한다. 내가 i번째 ..

문제(원문)문제(번역)문자열 s가 주어졌을 때 중복되는 문자가 없는 가장 긴 부분 문자열의 길이를 구해라.단, s는 영어문자, 숫자, 기호, 공백이 들어갈 수 있다.접근 방법알파벳이면 26 정도로 범위를 잡으면 되지만, 이는 숫자, 기호, 공백이 모두 들어가서 어떻게 해야할지 감이 안잡혔다. 외부 라이브러리나 직접 dict 같은걸 구현하기에는 코드가 너무 길어질 것 같아서 고민하다가,아스키코드의 범위가 0부터 127이라는 것을 깨달았다. 즉 아스키 코드 범위에 대해서만 flag를 지정하고 매번 겹치는 문자가 있는지 검사하는 방법으로 코드를 구현했다. 소스 코드char map[128] = {0};void initMap(){ for(int t=0;tC언어로 작성한 코드인데, 아래와 같은 실행결과가 나..