3SumSolution (세 수의 합)
정수 배열 nums가 주어질 때, 다음 조건을 만족하는 모든 삼중쌍(트리플릿) \[nums[i], nums[j], nums[k]\]를 반환하세요.
•
i != j, i != k, j != k
•
nums[i] + nums[j] + nums[k] == 0
결과에는 중복된 트리플릿이 포함되면 안 됩니다.
예시 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
서로 다른 트리플릿은 [-1,0,1] 과 [-1,-1,2] 입니다.
출력의 순서나 트리플릿 내부의 순서는 중요하지 않습니다.
Plain Text
복사
예시 2:
Input: nums = [0,1,1]
Output: []
Explanation: 합이 0이 되는 트리플릿을 만들 수 없습니다.
Plain Text
복사
예시 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: 유일한 트리플릿의 합이 0입니다.
Plain Text
복사
제약 조건:
•
3 <= nums.length <= 3000
•
-10^5 <= nums[i] <= 10^5
힌트 #1
세 수 x, y, z의 합이 특정 값(여기서는 0)이 되도록 찾아야 합니다. 한 수 x를 고정하면 나머지는 2Sum 문제로 바뀝니다.
힌트 #2
2Sum에서 한 수를 고정하면, 나머지 한 수 y는 value - x가 됩니다. 배열을 어떤 방식으로 바꾸면 탐색이 더 빨라질까요?
힌트 #3
배열을 바꾸지 않고도, 해시맵 같은 추가 공간을 써서 더 빠르게 찾을 수 있을까요?
Set Matrix ZeroesSolution (행렬 0 만들기)
m x n 정수 행렬 matrix가 주어집니다. 어떤 원소가 0이면, 그 원소가 속한 행 전체와 열 전체를 모두 0으로 설정하세요.
반드시 제자리(in place)로 수행해야 합니다.
예시 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Plain Text
복사
예시 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Plain Text
복사
제약 조건:
•
m == matrix.length
•
n == matrix[0].length
•
1 <= m, n <= 200
•
-2^31 <= matrix[i][j] <= 2^31 - 1
추가 과제(Follow up):
•
O(mn) 공간을 쓰는 단순한 해법은 좋은 선택이 아닙니다.
•
O(m + n) 공간으로 개선할 수 있지만, 이것도 최선은 아닙니다.
•
O(1) 추가 공간(상수 공간)으로 해결할 수 있을까요?
힌트 #1
0이 있는 행/열 번호를 따로 기록하려면 추가 메모리가 필요합니다. 추가 메모리를 쓰지 않으려면 행렬 자체를 표식으로 활용하는 방법을 생각해보세요.
힌트 #2
순회 중에 바로 0으로 바꾸면 나중에 원래 0이 아니었던 값까지 전파될 수 있습니다. 표식을 위해 다른 값을 쓰는 방법도 있지만, 더 좋은 O(1) 공간 해법이 있습니다.
힌트 #3
행/열을 기록하기 위해 집합 2개를 쓸 수도 있지만, O(1) 공간을 위해서는 특정 행 하나와 특정 열 하나를 기록 용도로 사용할 수 있습니다.
힌트 #4
각 행의 첫 칸과 각 열의 첫 칸을 플래그로 사용하면, 해당 행/열을 0으로 만들어야 하는지 판단할 수 있습니다.
Group AnagramsSolution (애너그램 그룹화)
문자열 배열 strs가 주어질 때, 서로 애너그램(철자 재배열로 서로가 될 수 있는 단어)인 것끼리 묶어 반환하세요.
반환 순서는 어떤 순서든 상관없습니다.
예시 1:
입력: strs = ["eat","tea","tan","ate","nat","bat"]
출력: [["bat"],["nat","tan"],["ate","eat","tea"]]
설명:
•
"bat"은 다른 문자열과 애너그램 관계가 아닙니다.
•
"nat"과 "tan"은 서로 애너그램입니다.
•
"ate", "eat", "tea"는 서로 애너그램입니다.
예시 2:
입력: strs = [""]
출력: [[""]]
예시 3:
입력: strs = ["a"]
출력: [["a"]]
제약 조건:
•
1 <= strs.length <= 10^4
•
0 <= strs[i].length <= 100
•
strs[i]는 소문자 영어 알파벳으로만 구성됩니다.
Longest Substring Without Repeating CharactersSolution (중복 없는 가장 긴 부분 문자열)
문자열 s가 주어질 때, 중복 문자가 없는 가장 긴 부분 문자열(substring)의 길이를 구하세요.
예시 1:
Input: s = "abcabcbb"
Output: 3
Explanation: "abc"의 길이가 3입니다. "bca"나 "cab"도 정답이 될 수 있습니다.
Plain Text
복사
예시 2:
Input: s = "bbbbb"
Output: 1
Explanation: "b"의 길이가 1입니다.
Plain Text
복사
예시 3:
Input: s = "pwwkew"
Output: 3
Explanation: 정답은 "wke"이며 길이는 3입니다.
"pwke"는 subsequence(부분수열)이지 substring(연속 부분 문자열)이 아닙니다.
Plain Text
복사
제약 조건:
•
0 <= s.length <= 5 * 10^4
•
s는 영문자, 숫자, 기호, 공백으로 구성됩니다.
힌트 #1
(힌트 문구 원문이 다소 부정확할 수 있습니다.) 가능한 모든 부분 문자열을 생성해 확인하는 방식은 비효율적일 수 있으니, 더 효율적인 방법(예: 슬라이딩 윈도우)을 떠올려보세요.
Longest Palindromic SubstringSolution (가장 긴 팰린드롬 부분 문자열)
문자열 s가 주어질 때, s 안에서 가장 긴 팰린드롬(앞에서 읽으나 뒤에서 읽으나 동일) 부분 문자열을 반환하세요.
예시 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba"도 정답이 될 수 있습니다.
Plain Text
복사
예시 2:
Input: s = "cbbd"
Output: "bb"
Plain Text
복사
제약 조건:
•
1 <= s.length <= 1000
•
s는 숫자와 영문자만으로 구성됩니다.
힌트 #1
이미 계산한 팰린드롬 정보를 재사용해서 더 큰 팰린드롬을 계산할 수 있을까요?
힌트 #2
"aba"가 팰린드롬이면 "xabax"도 팰린드롬일까요? 그렇다면 "xabay"는 어떨까요?
힌트 #3
무식하게 모든 구간 (start, end)에 대해 팰린드롬인지 검사하면, 구간 쌍은 O(n^2)개이고 매번 검사는 O(n)이어서 전체가 O(n^3)이 됩니다. 검사를 O(1)에 가깝게 줄일 수 있는 방법이 있을까요?
Increasing Triplet SubsequenceSolution (증가하는 길이 3 부분수열)
정수 배열 nums가 주어질 때, 다음을 만족하는 인덱스 세 쌍 (i, j, k)가 존재하면 true를 반환하세요.
•
i < j < k
•
nums[i] < nums[j] < nums[k]
존재하지 않으면 false를 반환합니다.
예시 1:
Input: nums = [1,2,3,4,5]
Output: true
Explanation: i < j < k 를 만족하는 어떤 트리플릿이든 가능합니다.
Plain Text
복사
예시 2:
Input: nums = [5,4,3,2,1]
Output: false
Explanation: 증가하는 트리플릿이 존재하지 않습니다.
Plain Text
복사
예시 3:
Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: (1,4,5)가 한 예입니다. nums[1]=1 < nums[4]=4 < nums[5]=6
Plain Text
복사
제약 조건:
•
1 <= nums.length <= 5 * 10^5
•
-2^31 <= nums[i] <= 2^31 - 1
추가 과제(Follow up):
O(n) 시간과 O(1) 공간으로 구현할 수 있을까요?
Missing RangesSolution (누락된 구간 찾기)
포함 구간 [lower, upper]와 정렬되어 있고 중복이 없는 정수 배열 nums가 주어집니다. nums의 모든 원소는 [lower, upper] 범위 안에 있습니다.
x가 다음을 만족하면 x는 누락(missing)된 값입니다.
•
x는 [lower, upper] 범위에 포함된다.
•
x는 nums에 존재하지 않는다.
모든 누락된 수를 겹치지 않게 정확히 한 번씩 덮는, 가장 작은(최소 개수의) 정렬된 구간 리스트를 반환하세요.
각 구간 [a,b]는 다음 형식으로 출력합니다.
•
a != b이면 "a->b"
•
a == b이면 "a"
예시 1:
Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation:
[2,2] -> "2"
[4,49] -> "4->49"
[51,74] -> "51->74"
[76,99] -> "76->99"
Plain Text
복사
예시 2:
Input: nums = [], lower = 1, upper = 1
Output: ["1"]
Explanation: 유일한 누락 구간은 [1,1] 이며 "1"이 됩니다.
Plain Text
복사
예시 3:
Input: nums = [], lower = -3, upper = -1
Output: ["-3->-1"]
Plain Text
복사
예시 4:
Input: nums = [-1], lower = -1, upper = -1
Output: []
Plain Text
복사
예시 5:
Input: nums = [-1], lower = -2, upper = -1
Output: ["-2"]
Plain Text
복사
제약 조건:
•
-10^9 <= lower <= upper <= 10^9
•
0 <= nums.length <= 100
•
lower <= nums[i] <= upper
•
nums의 모든 값은 유일합니다.
Count and SaySolution (카운트 앤 세이)
count-and-say 수열은 다음과 같이 정의되는 숫자 문자열 수열입니다.
•
countAndSay(1) = "1"
•
countAndSay(n)은 countAndSay(n - 1)을 런 길이 인코딩(RLE) 한 결과입니다.
런 길이 인코딩(RLE)은 연속해서 같은 문자가 나올 때, 그 문자를 (개수 + 문자)로 바꾸는 압축 방식입니다.
예를 들어 "3322251"을 압축하면,
•
"33" → "23"
•
"222" → "32"
•
"5" → "15"
•
"1" → "11"
따라서 결과는 "23321511"입니다.
양의 정수 n이 주어질 때, count-and-say 수열의 n번째 원소를 반환하세요.
예시 1:
입력: n = 4
출력: "1211"
설명:
countAndSay(1) = "1"
countAndSay(2) = "1"의 RLE = "11"
countAndSay(3) = "11"의 RLE = "21"
countAndSay(4) = "21"의 RLE = "1211"
Plain Text
복사
예시 2:
입력: n = 1
출력: "1"
설명: 기본 케이스입니다.
제약 조건:
•
1 <= n <= 30
추가 과제(Follow up):
반복문(Iterative) 방식으로 풀 수 있을까요?
힌트 #1
문자열(또는 숫자 문자열)을 받아서, 연속된 숫자와 그 빈도를 \[\[digit, count\], ...\] 형태로 만드는 헬퍼 함수를 만드세요.
힌트 #2
위의 쌍 배열을 받아서 count + digit를 이어붙여 새로운 문자열을 만드는 헬퍼 함수를 만드세요.
힌트 #3
"1"에서 시작해 위 과정을 n-1번 반복하면 마지막 문자열이 정답입니다.