Remove Duplicates from Sorted Array (중복 제거 - 정렬된 배열에서)
문제 설명
비내림차순(오름차순 또는 같은 값이 있을 수 있음)으로 정렬된 정수 배열 nums가 주어졌을 때, 배열 내 중복 요소를 제거하여 각 원소가 한 번만 나타나도록 하세요.
**제자리(in-place)**에서 수정해야 하며, 원소들의 상대적 순서는 변경되지 않아야 합니다.
그런 다음 중복을 제거한 후 남은 고유한 요소의 개수 k를 반환하세요.
요구 조건 (Custom Judge)
당신의 솔루션은 아래의 방식으로 테스트됩니다:
int[] nums = [...]; // 입력 배열
int[] expectedNums = [...]; // 기대 결과 (중복 제거된 상태)
int k = removeDuplicates(nums); // 구현한 함수 호출
assert k == expectedNums.length;
for (int i = 0; i < k; i++)
{
assert nums[i] == expectedNums[i];
}
C++
복사
위의 모든 assert 문이 통과한다면, 당신의 솔루션은 정답으로 인정됩니다.
예시 1
입력:
nums = [1,1,2]
출력:
k = 2, nums = [1, 2, _]
설명:
함수는 k = 2를 반환해야 하며, nums의 처음 두 요소는 각각 1과 2가 되어야 합니다.
k 이후의 값은 중요하지 않으므로 _로 표기합니다.
예시 2
입력:
nums = [0,0,1,1,1,2,2,3,3,4]
출력:
k = 5, nums = [0,1,2,3,4,_,_,_,_,_]
설명:
중복을 제거하고 남은 고유한 값은 0, 1, 2, 3, 4로 5개입니다.
배열 nums의 앞부분 5개가 이 값들을 포함하면 됩니다.
Solution
#include <iostream>
#include <vector>
using namespace std;
int removeDuplicates(std::vector<int>& nums)
{
int ret = 0;
return ret;
}
int main()
{
std::vector<int> nums = { 1, 1, 2 };
int newLength = removeDuplicates(nums);
std::cout << "New length: " << newLength << std::endl;
std::cout << "Modified array: ";
for (int i = 0; i < newLength; ++i)
{
std::cout << nums[i] << " ";
}
std::cout << std::endl;
return 0;
}
C++
복사
Best Time to Buy and Sell Stock II
(주식을 사고팔아 최대 이익 얻기 II)
문제 설명
정수 배열 prices가 주어집니다.
여기서 prices[i]는 i번째 날의 주식 가격을 의미합니다.
각 날에 대해, 주식을 살 수도 있고, 팔 수도 있습니다. 단, **동시에 한 주(share)**만 보유할 수 있으며,
같은 날에 바로 사고 파는 것도 가능합니다.
당신이 얻을 수 있는 최대 이익을 계산해서 반환하세요.
예시
예제 1:
입력: prices = [7,1,5,3,6,4]
출력: 7
설명:
- 2일차에 주식을 사고(가격=1), 3일차에 팔면(가격=5) 이익 = 5 - 1 = 4
- 4일차에 주식을 사고(가격=3), 5일차에 팔면(가격=6) 이익 = 6 - 3 = 3
- 총 이익 = 4 + 3 = 7
Plain Text
복사
예제 2:
입력: prices = [1,2,3,4,5]
출력: 4
설명:
- 1일차에 사고 5일차에 팔면 이익 = 5 - 1 = 4
- 총 이익 = 4
Plain Text
복사
예제 3:
입력: prices = [7,6,4,3,1]
출력: 0
설명:
- 가격이 계속 하락하므로 이익을 낼 수 있는 방법이 없음.
- 아무 것도 안 사고 안 팔면 최대 이익 = 0
Plain Text
복사
제약 조건
•
1 <= prices.length <= 30,000
•
0 <= prices[i] <= 10,000
Solution
#include <iostream>
#include <vector>
using namespace std;
int maxProfit(vector<int>& nums)
{
int max = 0;
return max;
}
int main()
{
std::vector<int> prices = { 7, 1, 5, 3, 6, 4 };
int maxProfitValue = maxProfit(prices);
return 0;
}
C++
복사
문제: 배열 회전
정수 배열 nums와 비음수 정수 k가 주어집니다.
배열을 오른쪽으로 k칸 회전하세요.
예제
예제 1
입력: nums = [1,2,3,4,5,6,7], k = 3
출력: [5,6,7,1,2,3,4]
설명:
- 1회 회전: [7,1,2,3,4,5,6]
- 2회 회전: [6,7,1,2,3,4,5]
- 3회 회전: [5,6,7,1,2,3,4]
Plain Text
복사
예제 2
입력: nums = [-1,-100,3,99], k = 2
출력: [3,99,-1,-100]
설명:
- 1회 회전: [99,-1,-100,3]
- 2회 회전: [3,99,-1,-100]
Plain Text
복사
제약 조건
•
1 <= nums.length <= 10⁵
•
2³¹ <= nums[i] <= 2³¹ - 1
•
0 <= k <= 10⁵
추가 도전 과제
•
가능한 다양한 방법으로 풀어보세요. 최소 3가지 방법이 존재합니다.
•
*O(1)**의 추가 공간만 사용하여 제자리에서(in-place) 해결할 수 있나요?
Single Number
문제 설명
비어있지 않은 정수 배열 nums가 주어집니다.
이 배열에서 모든 원소는 두 번씩 등장하며, 단 한 원소만 한 번 등장합니다.
그 한 번만 등장하는 원소를 찾아 반환하세요.
조건
•
시간 복잡도는 O(n) (선형 시간)이어야 하며,
•
추가 공간 사용은 O(1) (상수 공간)으로 해결해야 합니다.
예제 1
입력: nums = [2, 2, 1]
출력: 1
예제 2
입력: nums = [4, 1, 2, 1, 2]
출력: 4
예제 3
입력: nums = [1]
출력: 1
제약 사항
•
1 ≤ nums.length ≤ 30,000
•
30,000 ≤ nums[i] ≤ 30,000
•
배열의 모든 원소는 두 번씩 등장하지만, 단 하나만 한 번 등장합니다.
#include <iostream>
#include <vector>
using namespace std;
int singleNumber(vector<int>& nums)
{
int result = 0;
return result;
}
int main()
{
std::vector<int> nums = { 2, 2, 1 };
int result = singleNumber(nums);
return 0;
}
C++
복사
Intersection of Two Arrays II
두 배열의 교집합 II
문제 설명
두 개의 정수 배열 nums1과 nums2가 주어집니다.
두 배열의 교집합을 구하여 반환하세요.
단, 각 요소는 두 배열 모두에서 등장하는 횟수만큼 결과에 포함되어야 하며, 결과 배열의 순서는 상관없습니다.
예제 1
입력: nums1 = [1,2,2,1], nums2 = [2,2 ]
출력: [2,2]
예제 2
입력: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
출력: [4,9]
설명: [9,4]도 정답으로 인정됩니다.
제약 조건
•
1 ≤ nums1.length, nums2.length ≤ 1000
•
0 ≤ nums1[i], nums2[i] ≤ 1000
심화 질문 (Follow-up):
1.
배열이 이미 정렬되어 있다면, 알고리즘을 어떻게 최적화할 수 있을까요?
2.
nums1의 크기가 nums2보다 훨씬 작다면, 어떤 알고리즘이 더 좋을까요?
3.
nums2의 원소가 디스크에 저장되어 있고, 메모리가 제한되어 있어 전체를 한 번에 불러올 수 없다면, 어떻게 해야 할까요?
#include <iostream>
#include <vector>
using namespace std;
vector<int> singleNumber(vector<int>& nums1, vector<int>& nums2)
{
vector<int> result;
return result;
}
int main()
{
std::vector<int> nums1 = { 1,2,2,1 };
std::vector<int> nums2 = { 2,2 };
vector<int> result = singleNumber(nums1, nums2);
return 0;
}
C++
복사
문제: 플러스 원 (Plus One)
당신은 큰 정수를 나타내는 정수 배열 digits를 받았습니다.
•
각 digits[i]는 해당 자리의 숫자를 의미하며,
•
가장 큰 자릿수부터 가장 작은 자릿수까지 왼쪽에서 오른쪽으로 배열되어 있습니다.
•
이 큰 정수는 앞에 0이 없습니다.
이 정수에 1을 더한 결과를 배열 형태로 반환하세요.
예제
예제 1
입력: digits = [1,2,3]
출력: [1,2,4]
설명: 배열은 정수 123을 나타냅니다.
123 + 1 = 124 → 결과는 [1,2,4]
Plain Text
복사
예제 2
입력: digits = [4,3,2,1]
출력: [4,3,2,2]
설명: 배열은 4321을 나타냅니다.
4321 + 1 = 4322 → 결과는 [4,3,2,2]
Plain Text
복사
예제 3
입력: digits = [9]
출력: [1,0]
설명: 배열은 9를 나타냅니다.
9 + 1 = 10 → 결과는 [1,0]
Plain Text
복사
제약 조건
•
1 <= digits.length <= 100
•
0 <= digits[i] <= 9
•
배열은 앞자리 숫자에 0이 포함되지 않습니다.
class Solution {
public:
vector<int> plusOne(vector<int>& digits)
{
return digits;
}
};
C++
복사
문제: 제로를 이동하라 (Move Zeroes)
정수 배열 nums가 주어집니다.
•
모든 0을 배열 끝으로 이동시키되,
•
0이 아닌 요소들의 상대적인 순서는 유지해야 합니다.
주의: 이 작업은 반드시 배열을 복사하지 않고 in-place(제자리에서) 수행해야 합니다.
예제
예제 1
입력: nums = [0,1,0,3,12]
출력: [1,3,12,0,0]
Plain Text
복사
예제 2
입력: nums = [0]
출력: [0]
Plain Text
복사
제약 조건
•
1 <= nums.length <= 10,000
•
2^31 <= nums[i] <= 2^31 - 1
추가 질문 (Follow up):
•
이 작업에서 전체 연산 횟수를 최소화할 수 있을까요?
class Solution
{
public:
void moveZeroes(vector<int>& nums)
{
}
};
C++
복사
Two Sum (두 수의 합)
문제 설명
정수 배열 nums와 하나의 정수 target이 주어집니다.
배열에서 두 숫자를 골라 그 합이 target이 되는 경우,
그 두 숫자의 인덱스를 배열로 반환하세요.
•
같은 요소를 두 번 사용할 수는 없습니다.
•
정답은 항상 하나만 존재합니다.
•
반환 순서는 상관없습니다.
예제
예제 1
입력: nums = [2, 7, 11, 15], target = 9
출력: [0, 1]
설명: nums[0] + nums[1] = 2 + 7 = 9이므로 [0, 1] 반환
예제 2
입력: nums = [3, 2, 4], target = 6
출력: [1, 2]
예제 3
입력: nums = [3, 3], target = 6
출력: [0, 1]
제약 사항
•
2 ≤ nums.length ≤ 10,000
•
10⁹ ≤ nums[i] ≤ 10⁹
•
10⁹ ≤ target ≤ 10⁹
•
정답은 반드시 하나만 존재함
추가 질문 (Follow-up)
•
*O(n²)**보다 더 빠른 알고리즘을 생각해 볼 수 있을까요?
#include <iostream>
#include <vector>
std::pair<int, int> TwoSum(std::vector<int>& nums, int target)
{
return { -1, -1 }; // Return an invalid pair if no solution is found
}
int main()
{
std::vector<int> nums = { 2, 7, 11, 15 };
int target = 9;
auto result = TwoSum(nums, target);
return 0;
}
C++
복사
Valid Sudoku (유효한 스도쿠)
문제 설명
9×9 크기의 스도쿠 보드가 주어집니다.
숫자가 채워진 칸들만 검사해서 현재 상태가 유효한 스도쿠인지 확인하세요.
다음 규칙을 따라야 합니다:
1.
*각 행(row)**에는 숫자 1부터 9까지가 중복 없이 한 번씩만 등장해야 합니다.
2.
*각 열(column)**에도 숫자 1부터 9까지가 중복 없이 한 번씩만 등장해야 합니다.
3.
전체 보드를 9개의 **3×3 박스(sub-box)**로 나눌 수 있는데,
각 박스에도 숫자 1부터 9까지가 중복 없이 한 번씩만 있어야 합니다.
참고 사항
•
주어지는 보드는 부분적으로만 채워져 있을 수 있습니다.
•
문제는 해결 가능한 스도쿠인지가 아니라, 현재 채워진 상태가 규칙을 위반하지 않는지만 확인하면 됩니다.
•
즉, "."은 빈 칸을 의미하며 검사 대상이 아닙니다.
예제 1
Input:
board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Python
복사
→ 현재 채워진 숫자들은 행/열/박스 모두 중복 없이 유효합니다.
예제 2
Input:
board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Python
복사
→ 첫 번째 3×3 박스에 8이 두 번 있음. (좌상단 박스: [8, 3, ., 6, ., ., ., 9, 8]) → 규칙 위반
제약 조건
•
board.length == 9
•
board[i].length == 9
•
board[i][j]는 "1"~"9" 또는 "." 중 하나입니다.
#include <iostream>
#include <vector>
using namespace std;
bool ValidSudoku(vector<vector<int>>& sudoku)
{
return false;
}
int main()
{
vector<vector<int>> board =
{ {'5', '3', '.', '.', '7', '.', '.', '.', '.'}
, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}
, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}
, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}
, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}
, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}
, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}
, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}
, {'.', '.', '.', '.', '8', '.', '.', '7', '9'} };
bool ret = ValidSudoku(board);
return 0;
}
C++
복사
Rotate ImageSolution
문제 설명
n x n 크기의 2차원 정수 배열 matrix가 주어집니다.
이 배열은 이미지라고 가정하며, 이미지를 90도 시계 방향으로 회전하세요.
•
in-place(제자리에서) 회전해야 하므로,
새로운 2차원 배열을 만들지 말고, 주어진 배열 자체를 수정해야 합니다.
Input: matrix =
[[1,2,3]
,[4,5,6]
,[7,8,9]]
Output:
[[7,4,1]
,[8,5,2]
,[9,6,3]]
Plain Text
복사
Example 2:
Input: matrix =
[[5,1,9,11]
,[2,4,8,10]
,[13,3,6,7]
,[15,14,12,16]]
Output:
[[15,13,2,5]
,[14,3,4,1]
,[12,6,8,9]
,[16,7,10,11]]
Plain Text
복사
제약 조건
•
n == matrix.length == matrix[i].length (정사각형 행렬)
•
1 <= n <= 20
•
1000 <= matrix[i][j] <= 1000
