- 다음 순열
정수 배열의 순열은 모든 요소를 일렬로 나열한 것을 의미합니다. 주어진 정수 배열에서 사전순으로 다음에 오는 더 큰 순열을 찾아야 합니다. 만약 더 큰 순열이 없다면, 배열을 가장 작은 순서로 재배치해야 합니다.
#include <vector>
#include <algorithm>
class Solution {
public:
void nextPermutation(std::vector<int>& nums) {
int n = nums.size();
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
int j = n - 1;
while (j >= 0 && nums[j] <= nums[i]) j--;
std::swap(nums[i], nums[j]);
}
std::reverse(nums.begin() + i + 1, nums.end());
}
};
- 가장 긴 유효한 괄호
주어진 문자열에서 올바른 괄호 쌍으로 이루어진 가장 긴 부분 문자열의 길이를 반환합니다.
#include <stack>
#include <string>
class Solution {
public:
int longestValidParentheses(std::string s) {
std::stack<int> st;
st.push(-1);
int maxLen = 0;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') st.push(i);
else {
st.pop();
if (!st.empty()) maxLen = std::max(maxLen, i - st.top());
else st.push(i);
}
}
return maxLen;
}
};
- 회전된 정렬된 배열 검색
회전된 정렬된 배열에서 특정 값의 인덱스를 찾습니다.
#include <vector>
class Solution {
public:
int search(std::vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
};
- 정렬된 배열에서 요소의 시작 및 끝 위치 찾기
정렬된 배열에서 특정 값을 포함하는 첫 번째와 마지막 위치를 찾습니다.
#include <vector>
class Solution {
public:
std::vector<int> searchRange(std::vector<int>& nums, int target) {
int start = findLeft(nums, target);
int end = findRight(nums, target);
return {start, end};
}
private:
int findLeft(const std::vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return (left < nums.size() && nums[left] == target) ? left : -1;
}
int findRight(const std::vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
return (right >= 0 && nums[right] == target) ? right : -1;
}
};
- 검색 삽입 위치
정렬된 배열에서 특정 값을 찾거나 삽입할 위치를 반환합니다.
#include <vector>
class Solution {
public:
int searchInsert(std::vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
};
- 유효한 수独
9x9 수독 게임판이 유효한지 확인합니다.
#include <unordered_set>
#include <vector>
class Solution {
public:
bool isValidSudoku(std::vector<std::vector<char>>& board) {
std::unordered_set<std::string> seen;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
char c = board[i][j];
if (c != '.') {
std::string row = "row" + std::to_string(i) + c;
std::string col = "col" + std::to_string(j) + c;
std::string box = "box" + std::to_string(i / 3) + std::to_string(j / 3) + c;
if (seen.count(row) || seen.count(col) || seen.count(box)) return false;
seen.insert(row);
seen.insert(col);
seen.insert(box);
}
}
}
return true;
}
};
- 수독 풀기
빈 칸을 채워서 유효한 수독을 완성합니다.
#include <vector>
class Solution {
public:
void solveSudoku(std::vector<std::vector<char>>& board) {
backtrack(board, 0, 0);
}
private:
bool backtrack(std::vector<std::vector<char>>& board, int row, int col) {
if (col == 9) {
col = 0;
row++;
if (row == 9) return true;
}
if (board[row][col] != '.') return backtrack(board, row, col + 1);
for (char c = '1'; c <= '9'; ++c) {
if (isValid(board, row, col, c)) {
board[row][col] = c;
if (backtrack(board, row, col + 1)) return true;
board[row][col] = '.';
}
}
return false;
}
bool isValid(const std::vector<std::vector<char>>& board, int row, int col, char c) {
for (int i = 0; i < 9; ++i) {
if (board[row][i] == c || board[i][col] == c || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
}
return true;
}
};
- 외观数열
n번째 항의 외형 수열을 계산합니다.
#include <string>
class Solution {
public:
std::string countAndSay(int n) {
if (n == 1) return "1";
std::string prev = countAndSay(n - 1);
std::string result = "";
int count = 1;
for (int i = 0; i < prev.size(); ++i) {
if (i + 1 < prev.size() && prev[i] == prev[i + 1]) count++;
else {
result += std::to_string(count) + prev[i];
count = 1;
}
}
return result;
}
};
- 조합의 합
주어진 후보자들로 목표값을 만들 수 있는 모든 가능한 조합을 찾습니다.
#include <vector>
class Solution {
public:
std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
std::vector<std::vector<int>> result;
std::vector<int> current;
backtrack(candidates, target, 0, current, result);
return result;
}
private:
void backtrack(const std::vector<int>& candidates, int target, int start, std::vector<int>& current, std::vector<std::vector<int>>& result) {
if (target < 0) return;
if (target == 0) {
result.push_back(current);
return;
}
for (int i = start; i < candidates.size(); ++i) {
current.push_back(candidates[i]);
backtrack(candidates, target - candidates[i], i, current, result);
current.pop_back();
}
}
};
- 조합의 합 II
각 숫자를 한 번만 사용하여 목표값을 만드는 모든 조합을 찾습니다.
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
std::sort(candidates.begin(), candidates.end());
std::vector<std::vector<int>> result;
std::vector<int> current;
backtrack(candidates, target, 0, current, result);
return result;
}
private:
void backtrack(const std::vector<int>& candidates, int target, int start, std::vector<int>& current, std::vector<std::vector<int>>& result) {
if (target < 0) return;
if (target == 0) {
result.push_back(current);
return;
}
for (int i = start; i < candidates.size(); ++i) {
if (i > start && candidates[i] == candidates[i - 1]) continue;
current.push_back(candidates[i]);
backtrack(candidates, target - candidates[i], i + 1, current, result);
current.pop_back();
}
}
};
- 첫 번째 누락된 양수
미리 정렬되지 않은 배열에서 가장 작은 양수를 찾습니다.
#include <vector>
class Solution {
public:
int firstMissingPositive(std::vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] <= 0 || nums[i] > n) nums[i] = n + 1;
}
for (int i = 0; i < n; ++i) {
int num = std::abs(nums[i]);
if (num <= n) nums[num - 1] = -std::abs(nums[num - 1]);
}
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) return i + 1;
}
return n + 1;
}
};
- 물 트래핑
높이가 주어진 지형에서 얼마나 많은 물이 쌓일 수 있는지 계산합니다.
#include <vector>
#include <stack>
class Solution {
public:
int trap(std::vector<int>& height) {
std::stack<int> st;
int ans = 0;
for (int i = 0; i < height.size(); ++i) {
while (!st.empty() && height[i] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty()) break;
int distance = i - st.top() - 1;
int bounded_height = std::min(height[i], height[st.top()]) - height[top];
ans += distance * bounded_height;
}
st.push(i);
}
return ans;
}
};
- 문자열 곱하기
두 개의 비트 없는 정수 문자열을 곱합니다.
#include <vector>
#include <string>
class Solution {
public:
std::string multiply(std::string num1, std::string num2) {
int m = num1.size(), n = num2.size();
std::vector<int> res(m + n, 0);
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
int mul = (num1[i] - '0') * (num2[j] - '0');
int sum = mul + res[i + j + 1];
res[i + j] += sum / 10;
res[i + j + 1] = sum % 10;
}
}
std::string result = "";
for (auto num : res) {
if (!(result.empty() && num == 0)) result.push_back(num + '0');
}
return result.empty() ? "0" : result;
}
};
- 와일드카드 매칭
'?'와 '*'를 사용하여 문자열과 패턴을 매치합니다.
#include <vector>
class Solution {
public:
bool isMatch(std::string s, std::string p) {
int m = s.size(), n = p.size();
std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));
dp[0][0] = true;
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
- 점프 게임 II
배열에서 마지막 위치까지 도달하기 위해 필요한 최소 점프 횟수를 계산합니다.
#include <vector>
#include <algorithm>
class Solution {
public:
int jump(std::vector<int>& nums) {
int jumps = 0, current_end = 0, farthest = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
farthest = std::max(farthest, i + nums[i]);
if (i == current_end) {
jumps++;
current_end = farthest;
}
}
return jumps;
}
};
- 전체 순열
중복되지 않는 숫자들의 배열에서 모든 가능한 순열을 생성합니다.
#include <vector>
class Solution {
public:
std::vector<std::vector<int>> permute(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
std::vector<int> current;
std::vector<bool> used(nums.size(), false);
backtrack(nums, used, current, result);
return result;
}
private:
void backtrack(const std::vector<int>& nums, std::vector<bool>& used, std::vector<int>& current, std::vector<std::vector<int>>& result) {
if (current.size() == nums.size()) {
result.push_back(current);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (used[i]) continue;
used[i] = true;
current.push_back(nums[i]);
backtrack(nums, used, current, result);
current.pop_back();
used[i] = false;
}
}
};
- 전체 순열 II
중복 숫자가 있는 배열에서 중복되지 않는 모든 순열을 생성합니다.
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result;
std::vector<int> current;
std::vector<bool> used(nums.size(), false);
backtrack(nums, used, current, result);
return result;
}
private:
void backtrack(const std::vector<int>& nums, std::vector<bool>& used, std::vector<int>& current, std::vector<std::vector<int>>& result) {
if (current.size() == nums.size()) {
result.push_back(current);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
used[i] = true;
current.push_back(nums[i]);
backtrack(nums, used, current, result);
current.pop_back();
used[i] = false;
}
}
};
- 이미지 회전
nxn 행렬을 시계 방향으로 90도 회전합니다.
#include <vector>
class Solution {
public:
void rotate(std::vector<std::vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
std::swap(matrix[i][j], matrix[n - 1 - i][j]);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
std::swap(matrix[i][j], matrix[j][i]);
}
}
}
};
- 아나그램 그룹화
문자열 배열에서 아나그램을 그룹화합니다.
#include <unordered_map>
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
std::unordered_map<std::string, std::vector<std::string>> groups;
for (const auto& str : strs) {
std::string sorted_str = str;
std::sort(sorted_str.begin(), sorted_str.end());
groups[sorted_str].push_back(str);
}
std::vector<std::vector<std::string>> result;
for (const auto& pair : groups) {
result.push_back(pair.second);
}
return result;
}
};
- x^n 계산
x의 n제곱을 계산합니다.
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1.0;
double half = myPow(x, n / 2);
if (n % 2 == 0) return half * half;
if (n > 0) return half * half * x;
return half * half / x;
}
};
- N-퀸 문제
NxN 체스판에 N개의 퀸을 서로 공격하지 않도록 배치하는 방법을 찾습니다.
#include <vector>
class Solution {
public:
std::vector<std::vector<std::string>> solveNQueens(int n) {
std::vector<std::vector<std::string>> result;
std::vector<std::string> board(n, std::string(n, '.'));
DFS(result, board, 0, n);
return result;
}
private:
void DFS(std::vector<std::vector<std::string>>& result, std::vector<std::string>& board, int row, int n) {
if (row == n) {
result.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (isValid(board, row, col, n)) {
board[row][col] = 'Q';
DFS(result, board, row + 1, n);
board[row][col] = '.';
}
}
}
bool isValid(const std::vector<std::string>& board, int row, int col, int n) {
for (int i = 0; i < row; ++i) {
if (board[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 'Q') return false;
}
return true;
}
};
- N-퀸 문제 II
NxN 체스판에 N개의 퀸을 서로 공격하지 않도록 배치하는 방법의 수를 반환합니다.
#include <vector>
class Solution {
public:
int totalNQueens(int n) {
std::vector<std::vector<std::string>> result;
std::vector<std::string> board(n, std::string(n, '.'));
DFS(result, board, 0, n);
return result.size();
}
private:
void DFS(std::vector<std::vector<std::string>>& result, std::vector<std::string>& board, int row, int n) {
if (row == n) {
result.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (isValid(board, row, col, n)) {
board[row][col] = 'Q';
DFS(result, board, row + 1, n);
board[row][col] = '.';
}
}
}
bool isValid(const std::vector<std::string>& board, int row, int col, int n) {
for (int i = 0; i < row; ++i) {
if (board[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 'Q') return false;
}
return true;
}
};
- 최대 부분 배열 합
최대 합을 가진 연속적인 부분 배열을 찾습니다.
#include <vector>
#include <algorithm>
class Solution {
public:
int maxSubArray(std::vector<int>& nums) {
int res = nums[0];
for (int i = 1; i < nums.size(); ++i) {
nums[i] += std::max(nums[i - 1], 0);
res = std::max(res, nums[i]);
}
return res;
}
};
- 나선형 행렬
m x n 행렬을 나선형으로 탐색하여 모든 요소를 반환합니다.
#include <vector>
class Solution {
public:
std::vector<int> spiralOrder(std::vector<std::vector<int>>& matrix) {
std::vector<int> result;
if (matrix.empty()) return result;
int top = 0, bottom = matrix.size() - 1;
int left = 0, right = matrix[0].size() - 1;
while (top <= bottom && left <= right) {
for (int i = left; i <= right; ++i) result.push_back(matrix[top][i]);
top++;
for (int i = top; i <= bottom; ++i) result.push_back(matrix[i][right]);
right--;
if (top <= bottom) {
for (int i = right; i >= left; --i) result.push_back(matrix[bottom][i]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; --i) result.push_back(matrix[i][left]);
left++;
}
}
return result;
}
};
- 점프 게임
배열에서 마지막 위치까지 도달할 수 있는지를 확인합니다.
#include <vector>
class Solution {
public:
bool canJump(std::vector<int>& nums) {
int k = 0;
for (int i = 0; i < nums.size(); ++i) {
if (i > k) return false;
k = std::max(k, i + nums[i]);
}
return true;
}
};
- 구간 병합
중첩된 구간들을 병합합니다.
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
std::vector<std::vector<int>> merged;
if (intervals.empty()) return merged;
std::sort(intervals.begin(), intervals.end());
merged.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] <= merged.back()[1]) {
merged.back()[1] = std::max(merged.back()[1], intervals[i][1]);
} else {
merged.push_back(intervals[i]);
}
}
return merged;
}
};
- 구간 삽입
구간 리스트에 새로운 구간을 삽입하고 필요시 병합합니다.
#include <vector>
class Solution {
public:
std::vector<std::vector<int>> insert(std::vector<std::vector<int>>& intervals, std::vector<int>& newInterval) {
std::vector<std::vector<int>> result;
int i = 0;
while (i < intervals.size() && intervals[i][1] < newInterval[0]) {
result.push_back(intervals[i++]);
}
while (i < intervals.size() && intervals[i][0] <= newInterval[1]) {
newInterval[0] = std::min(newInterval[0], intervals[i][0]);
newInterval[1] = std::max(newInterval[1], intervals[i][1]);
i++;
}
result.push_back(newInterval);
while (i < intervals.size()) {
result.push_back(intervals[i++]);
}
return result;
}
};
- 마지막 단어의 길이
문자열에서 마지막 단어의 길이를 반환합니다.
#include <string>
class Solution {
public:
int lengthOfLastWord(const std::string& s) {
int length = 0;
int i = s.size() - 1;
while (i >= 0 && s[i] == ' ') i--;
while (i >= 0 && s[i] != ' ') {
length++;
i--;
}
return length;
}
};
- 나선형 행렬 II
nxn 행렬을 나선형으로 채웁니다.
#include <vector>
class Solution {
public:
std::vector<std::vector<int>> generateMatrix(int n) {
std::vector<std::vector<int>> result(n, std::vector<int>(n, 0));
int top = 0, bottom = n - 1;
int left = 0, right = n - 1;
int num = 1;
while (top <= bottom && left <= right) {
for (int i = left; i <= right; ++i) result[top][i] = num++;
top++;
for (int i = top; i <= bottom; ++i) result[i][right] = num++;
right--;
if (top <= bottom) {
for (int i = right; i >= left; --i) result[bottom][i] = num++;
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; --i) result[i][left] = num++;
left++;
}
}
return result;
}
};
- 순열 순서
n!개의 순열 중 k번째 순열을 찾습니다.
#include <vector>
#include <string>
class Solution {
public:
std::string getPermutation(int n, int k) {
std::string result;
std::vector<int> nums;
int factorial = 1;
for (int i = 1; i <= n; ++i) {
nums.push_back(i);
factorial *= i;
}
k--;
for (int i = 0; i < n; ++i) {
factorial /= (n - i);
int index = k / factorial;
result += std::to_string(nums[index]);
nums.erase(nums.begin() + index);
k %= factorial;
}
return result;
}
};