코딩

문제 설명 문제 링크 0과 1로 구성된 리스트 nums가 주어질 때, 0의 개수와 1의 개수가 동일한 subarray의 최대 길이를 구해야 한다. 만약 nums = [0, 0, 1, 1, 1, 0, 1, 1] 이면, 최대 길이는 6이다. 제약 조건: 1 <= nums.length <= 10^5 풀이 1. 브루트포스 풀기 전 아이디어가 딱히 떠오르지 않아서...

문제 설명 문제 링크 [시작, 끝] 구간이 담겨있는 intervals 배열이 주어진다. 구간은 서로 겹쳐있지 않고, 시작 값을 기준으로 오름차순 정렬되어 있다. 여기에 새로운 구간인 newInterval을 추가해야 한다. newInterval을 추가했을 때 겹쳐지는 부분이 생기면 병합(merge) 해야 한다. 제약 조건 0 <= intervals.len...

문제 설명 문제 링크 풍선들이 xy 좌표에 놓여있다. 모든 풍선의 x 구간을 나타내는 points가 주어진다. points[i] = [xstart, xend]로 나타낼 수 있다. 그리고 화살을 쏘게 되는데, 화살은 x 좌표 위에서 y 좌표가 증가하는 방향으로 수직 발사한다. 화살을 발사하여 특정 x 좌표에 속한 풍선들을 모두 터뜨릴 수 있다. points를...

문제 설명 문제 링크 singly linked list가 주어질 때, Palindrome 여부를 return 한다. linked list의 값을 앞으로 읽든 뒤로 읽든 같다면 Palindrome이라고 할 수 있다. 제약 조건 linked list 길이: [1, 10^5] linked list에 있는 값의 범위: 0 <= Node.val <= 9 ...

문제 링크 단일 연결 리스트(singly linked list)가 주어진다. 아래 형태로 바꿔야 한다. 기존: 1 -> 2 -> 3 -> ... -> n-1 -> n 변경: 1 -> n -> 2 -> n-1 -> 3 -> ... 제약 조건 연결 리스트 길이: [1, 5 * 10^4] 노드 값 범위: 1 <= Node.val <= 1000 ...

문제 링크 n+1개의 정수가 들어있는 nums 배열이 주어진다. 배열 안에 있는 값의 범위는 [1, n] 이다. 배열 안에는 중복으로 들어간 수가 하나 있는데, 이를 찾아야 한다. 제약 조건 1 <= n <= 10^5 nums.length == n + 1 1 <= nums[i] <= n 풀이 풀기 전 set 사용하면 간단히 풀릴 거 같다. 시간...

문제 링크 길이가 n인 nums 배열이 주어진다. 들어있는 값의 범위는 [1, n]이고, 각 값들은 nums 안에 한 번 또는 두 번 들어있다. 두 번 들어간 값들을 찾아야한다. 제약 조건 n == nums.length 1 <= n <= 10^5 1 <= nums[i] <= n 풀이 풀기 전 시간 복잡도가 O(n)이고 공간 복잡도가 O(1)이어...

문제 링크 단일 연결 리스트(singly linked list)의 head가 주어질 때, 거꾸로 뒤집는 문제다. 제약 조건 노드 개수 범위: [0, 5000] 노드 값 범위: -5000 <= Node.val <= 5000 풀이 1. stack 사용 풀기 전 거꾸로 뒤집는 거면 간단히 스택에 넣었다가 빼면 될 거라 생각했다. 코드 푼 후 답은 잘...

문제 링크 정렬되지 않은 nums 배열이 주어진다. 이 배열에 포함되지 않으면서 가장 작은 자연수를 구해야한다. 시간 복잡도는 O(n)이고 추가적인 공간 복잡도는 O(1)이어야 한다. 제약 조건 배열 길이: 1 <= nums.length <= 10^5 값 범위: -2^31 <= nums[i] <= 2^31 - 1 풀이 풀기 전 아이디어가 안 떠올라...

문제 링크 배열 nums와 정수 k가 주어진다. 모든 값의 곱이 k보다 작은 subarray 개수를 구해야한다. 제약 조건 배열 길이: 1 <= nums.length <= 3 * 10^4 배열 값 범위: 1 <= nums[i] <= 1000 k 범위: 0 <= k <= 10^6 풀이 풀기 전 처음에는 브루트포스로 모든 경우의 수를 계산해보려고 ...

문제 링크 배열 nums와 정수 k가 주어진다. 특정 값의 빈도수가 subarray 안에서 k를 넘지 않으면 good인 상태라고 한다. subarray에 속한 모든 값이 good인 subarray의 최대 길이를 구해야 한다. 제약 조건 배열 길이: 1 <= nums.length <= 10^5 값 범위: 1 <= nums[i] <= 10^9 k 범...

문제 링크 배열 nums와 자연수 k가 주어진다. nums에 있는 최대값을 M이라고 할 때, nums의 subarray 중에서 M이 k개 이상 포함되는 subarray 개수를 구해야 한다. 제약 조건 배열 길이: 1 <= nums.length <= 10^5 배열 값 범위: 1 <= nums[i] <= 10^6 k 범위: 1 <= k <= 10^5...

문제 링크 배열 nums와 정수 k가 주어진다. 서로 다른 값의 개수가 정확히 k인 subarray의 총 개수를 구해야 한다. 제약 조건 배열 길이: 1 <= nums.length <= 2 * 10^4 배열 값과 k 범위: 1 <= nums[i], k <= nums.length 풀이 풀기 전 머리를 이리저리 굴려봤는데 마땅한 풀이가 떠오르지 않았다...

문제 문제 링크 배열 nums와 두 정수 minK, maxK가 주어진다. nums의 subarray 중에서 최대값이 maxK이고 최소값이 minK인 subarray 개수를 구해야 한다. 제약 조건 배열 길이: 2 <= nums.length <= 10^5 배열 값과 minK, maxK 범위: 1 <= nums[i], minK, maxK <= 10^6 ...

문제 문제 링크 단어와 공백이 들어간 문자열 s가 주어진다. 마지막 단어의 길이를 구해야 한다. 제약 조건 문자열 길이: 1 <= s.length <= 10^4 s에는 영어와 공백(' ')만 들어감 최소 한 개의 단어가 존재함 풀이 풀기 전 4월 문제 시작이라 그런지 쉬운 문제가 나왔다. 이번 달은 문자열인가!? 코드 푼 후 쉬운 문제긴 했...

문제 문제 링크 두 문자열 s와 t가 주어진다. 두 문자열이 isomorphic 한지 알아내야 한다. isomorphic 하다는 건 두 문자열에서 같은 위치(인덱스)에 있는 문자들이 서로 대응되어 교체될 수 있는 상태이다. 예를 들어 a라는 문자는 어떤 문자에든 대응될 수 있지만, 1:1로만 대응되어야 한다. egg와 add는 isomorphic 하다....

문제 문제 링크 m x n 크기의 board와 문자열 word가 주어진다. word가 board 안에 있는지 확인해야 한다. board 안에서 수직/수평으로 인접한 문자들을 연결해서 word가 나올 수 있으면 word는 board 안에 있다고 할 수 있다. 제약 조건 1 <= m, n <= 6 문자열 크기: 1 <= word.length <= 15 ...

문제 문제 링크 VPS(valid parentheses string)인 문자열 s가 주어질 때, 가장 깊은 depth를 구해야 한다. VPS는 아래 조건을 만족한다. 빈 문자열("")일 수 있다. "(", ")"이 아닌 단일 문자열일 수 있다. VPS인 A와 B가 있을 때, AB도 VPS이다. A가 VPS일 때, (A)도 V...

문제 문제 링크 영어 대소문자로 이루어진 문자열 s가 주어진다. s를 Good string으로 바꿔서 반환해야 한다. Good string이란 서로 근접한 문자가 대소문자인 경우가 없는 문자열이다. 제약 조건 문자열 길이: 1 <= s.length <= 100 풀이 풀기 전 제약 조건이 널널하다. 무식하게 풀어도 풀릴 거 같다. 처음에 무식하게 풀어서...

문제 문제 링크 '(', ')'와 영어 소문자로 이루어진 문자열 s가 주어진다. '(' 또는 ')'를 최소한으로 지워서 괄호가 제대로 닫혀있는 문자열을 반환해야 한다. 제약 조건 문자열 길이: 1 <= s.length <= 10^5 풀이 풀기 전 처음에 잘못 생각해서 '그냥 열고 닫는 괄호 개수 각각 센 다음 적은 괄호 빼주면 되지 않나' 했는데 닫는...

문제 문제 링크 '(', ')', '*'로 이루어진 문자열 s가 주어진다. s가 valid 한지 구해야 한다. valid 하다는 건 아래 조건을 만족하는 경우이다. '(' 이후에는 짝이 되는 ')'가 존재해야 한다. ')' 이전에는 짝이 되는 '('가 존재해야 한다. '*'은 '(' 또는 ')' 또는 빈 문자열로 취급될 수 있다. 제약 조건 ...

문제 문제 링크 배열 students와 배열 sandwiches가 주어진다. sandwiches에는 샌드위치 종류인 0과 1이 들어가 있다. students에는 각 학생이 먹고 싶은 샌드위치 종류가 들어가 있다. 학생은 아래 순서에 따라 샌드위치를 가져간다. students 배열 맨 앞에 있는 학생이 먹고 싶은 샌드위치를 확인한다. 먹고 싶은 샌드위...

문제 문제 링크 배열 tickets와 정수 k가 주어진다. tickets[i]는 i번째에 있는 사람이 사고 싶은 티켓 개수를 의미한다. 0번째에 있는 사람부터 티켓을 한 장씩 사기 시작한다. 티켓을 산 후에 아직 사려는 티켓을 다 못 샀다면 맨 뒤로 가서 다시 순서를 기다린다. 티켓을 모두 샀다면 다시 기다리지 않고 떠난다. 이때 k번째에 있는 사람이 티켓...

문제 문제 링크 배열 deck이 주어진다. 배열 안에는 카드 번호가 들어있다. 카드를 정렬한 뒤 아래 순서로 카드를 뽑았을 때 번호가 오름차순으로 뽑힐 수 있게 하려고 한다. 카드를 어떻게 정렬해야 하는지 구해야 한다. 맨 앞에 있는 카드를 뽑고 번호를 확인한 뒤 배열에서 뺀다. 아직 배열에 카드가 남아있다면 맨 앞에 있는 카드를 맨 뒤로 배치한다....

문제 문제 링크 문자열 num과 정수 k가 주어진다. num은 문자열이지만 숫자로 이루어져 있다. num에서 k개의 숫자(digit)를 제거해서 만들 수 있는 가장 작은 수를 구해야 한다. 제약 조건 num과 k의 범위: 1 <= k <= num.length <= 10^5 num에는 숫자만 들어간다. num은 0을 제외하고는 0부터 시작하지 않는...

문제 문제 링크 각 막대의 너비가 1인 높이 지도를 나타내는 양의 정수 배열 height가 주어진다. 비가 온 후에 얼마의 물이 채워지는지 구해야 한다. 예시 제약 조건 height 길이: 1 <= height.length <= 2 * 10^4 height 값 범위: 0 <= height[i] <= 10^5 풀이 풀기 전 규칙을 찾기 위해 예시로...

문제 문제 링크 0과 1로 채워진 2차원 배열 matrix가 주어진다. 1로만 채워진 직사각형 영역 중 가장 큰 영역의 넓이를 구해야 한다. 제약 조건 배열 길이: 1 <= matrix.length, matrix[0].length <= 200 예시 풀이 풀기 전 풀 방법을 이리저리 찾아보다가 뭔가 값을 누적해서 풀 수 있을 거 같았다. 그러고 아래 규...

문제 문제 링크 이진 트리인 root가 주어진다. 모든 left leaves의 합을 구해야 한다. leaf는 자식이 없는 노드를 의미한다. left leaf는 다른 노드의 왼쪽 자식인 leaf를 의미한다. 제약 조건 tree에 있는 노드 개수: [1, 1000] 노드 값 범위: -1000 <= Node.val <= 1000 풀이 풀기 전 트리 탐색...

문제 문제 링크 [0, 9] 범위의 값을 갖는 이진 트리 root가 주어진다. 트리에서 각 root-to-leaf 경로는 숫자를 나타낸다. 예를 들어 root-to-leaf 경로가 1 -> 2 -> 3이면 123이라는 숫자로 나타낼 수 있다. 주어진 이진 트리 root에 존재하는 root-to-leaf의 총합을 구해야 한다. 테스트케이스는 정답이 32-bi...

문제 문제 링크 이진 트리 root와 두 정수 val, depth가 주어진다. tree의 depth 위치에 val 값을 갖는 노드를 추가해야 한다. root는 depth가 1이다. 노드를 추가할 때는 아래 규칙을 따른다. 트리의 depth-1에 있는 null이 아닌 노드를 cur라고 한다면, val 값을 갖는 노드 두개를 각각 cur의 왼쪽, 오른쪽 자...

문제 문제 링크 이진 트리 root가 주어진다. 각 노드는 [0, 25] 범위의 값을 가진다. 그리고 각 값은 ['a', 'z']에 대응된다. leaf 노드에서 root로 이어지는 문자열 중에, 사전적으로 가장 작은 문자열을 구해야 한다. leaf 노드는 자식 노드를 가지고 있지 않은 노드이다. 제약 조건 트리에 있는 노드의 개수: [1, 8500] 예...

문제 문제 링크 지도를 나타내는 2차원 배열 grid가 주어진다. gridi 값이 1이면 땅을 의미하고, 0이면 물을 의미한다. grid 안에 있는 섬의 둘레를 구해야 한다. grid는 물로 둘러쌓여 있고, 안에는 단 하나의 섬이 존재한다. 섬 안에는 호수가 없다. 호수는 섬 외부에 있는 물과 연결되지 않은 물이다. 하나의 셀은 한 변의 길이가 ...

문제 문제 링크 지도를 나타내는 2차원 배열 grid가 주어진다. 값이 1인 곳은 땅을, 0인 곳은 물을 의미한다. 지도에 있는 섬의 개수를 구해야 한다. 섬은 물로 둘러쌓여 있고, 수직수평으로 땅이 연결된 곳을 의미한다. 제약 조건 grid 크기: 1 <= row, col <= 300 풀이 풀기 전 grid를 순회하다가 땅을 만났을 때 섬에 포함되는...

문제 문제 링크 땅을 나타내는 이차원 배열 land가 주어진다. 각 배열 값은 0 또는 1을 갖는다. 0은 숲을 의미하고, 1은 농지를 의미한다. 농지는 전체 모양이 직사각형을 이루도록 구성되어 있고, 이를 group이라고 한다. group은 왼쪽상단의 좌표와 오른쪽하단의 좌표로 표현할 수 있다. 예를 들면 왼쪽상단 좌표가 (r1, c1)이고 오른쪽 하단 ...

문제 문제 링크 정수 n과 이차원 배열 edges가 주어진다. n개의 노드를 가진 양방향 그래프에서, 각 노드는 0에서 n-1로 라벨링 되어있고 edges는 노드들의 연결관계를 나타낸다. 각 노드는 최대 한 개의 간선으로 연결되어 있고, 자신을 참조하진 못한다. 그리고 노드를 나타내는 정수 source와 destination이 주어진다. 그래프 상에서 so...

문제 문제 링크 네개의 원형 바퀴 형태를 가진 자물쇠가 있다. 각 바퀴는 0~9의 값을 갖고, 바퀴를 돌려서 슬롯에 값을 맞출 수 있다. 자물쇠는 "0000"으로 세팅되어 있다. 그리고 문자열 배열인 deadends와 문자열 target이 주어진다. deadends에는 특정 자물쇠 값들이 들어있는데, 자물쇠가 deadends에 있는 값과 같아지면 자물쇠는 ...

문제 문제 링크 트리가 있을 때, 노드의 개수를 나타내는 정수 n과 노드의 연결 관계를 나타내는 이차원 배열 edges가 주어진다. 각 노드는 0~n-1의 라벨을 갖는다. 트리의 root를 임의로 정할 수 있는데, 특정 노드를 root로 정했을 때 트리는 높이 h를 갖는다. 가능한 모든 트리 중에서 가장 낮은 높이를 갖는 트리들을 MHT(Minimum He...

문제 Tribonacci는 T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0으로 정의된다. 정수 n이 주어질 때, Tn을 구해야 한다. 제약 조건 n 범위: 0 <= n <= 37 정답은 32 bit 정수 범위 안에 있다. 풀이 풀기 전 피보나치인데 계산하는 항이 하나 추가되었다. 피보...

문제 소문자 알파벳으로 이루어진 문자열 s와 정수 k가 주어진다. 아래를 만족하는 문자열을 t라고 정의한다. t는 s의 subsequence이다. subsequence는 문자열에 있는 문자의 순서는 유지한 상태에서 특정 문자들을 선택적으로 지워서 만들 수 있는 문자열이다. 인접한 두 문자에 대해 알파벳 순서 차이의 절댓값이 k보다 작거나 같아야 한다...

문제 n x n의 이차원 정수 배열 grid가 주어진다. non-zero shift로 하강하는 경로의 합 중에서 가장 작은 값을 구해야 한다. non-zero shift라는 건 같은 열로 하강해서는 안 된다는 의미이다. 하강한다는 건 위쪽 행에서부터 아래쪽 행으로 내려가는 걸 의미한다. 제약 조건 n의 범위: 1 <= n <= 200 값의 범위: -...

문제 문제 링크 문자열 ring과 key가 주어진다. ring은 첫 문자가 12시 방향에 놓인 원형의 다이얼을 나타낸다. ring을 시계방향 또는 반시계방향으로 돌릴 수 있다. key는 ring의 12시 방향에 순서대로 놓아야 하는 문자들이다. ring을 최소한으로 돌려서 key에 있는 문자를 순서대로 맞출 때, 가장 작은 step을 구해야 한다. 각 st...

문제 문제 링크 n개의 노드를 가진 무방향 트리가 있다. 정수 n과 노드의 연결 관계를 나타내는 이차원 배열 edges가 주어진다. 노드는 0~n-1로 라벨링 되어있다. 배열 answer를 반환해야 하는데, answer[i]는 i번째 노드에서부터 그 외 모든 노드까지 거리를 모두 더한 값이다. 제약 조건 n의 범위: 1 <= n <= 3 * 10^4 ...

문제 문제 링크 정수 배열 nums와 양수 k가 주어진다. nums에 있는 모든 수의 xor 결과가 k와 같아지게 만들어야 한다. nums에 있는 수에 대해서 몇 번이고 비트를 플립할 수 있을 때 k와 같아지게 만드는 최소 플립 횟수를 구해야 한다. 제약 조건 nums 배열 길이: 1 <= nums.length <= 10^5 nums 값 범위: 0 ...

문제 문제 링크 설명 문자열 word가 주어진다. 최대 한 문자가 홀수번 포함되는 문자열을 wonderful string이라고 한다. word의 substring 중에서 wonderful string 개수를 구해야 한다. 제약 조건 word 길이: 1 <= word.length <= 10^5 word에는 'a'부터 'j'까지의 소문자만 들어간다...

문제 문제 링크 문자열 word와 문자 ch가 주어진다. word를 앞에서부터 순회하다가 ch를 처음 만나면, 맨앞과 ch를 포함한 인덱스까지 뒤집어야 한다. word에 ch가 포함되어 있지 않다면 word 그대로 반환한다. 만약 word="abcdef" ch='c'라면, 반환되는 문자열은 "cbadef"이다. 제약 조건 word 문자열 길이: 1 <=...