배열 섞기 (Shuffle an Array)
문제 설명
정수 배열 nums가 주어질 때, 해당 배열을 무작위로 섞는 알고리즘을 설계하세요.
모든 배열의 순열(permutation)은 동일한 확률로 반환되어야 합니다.
Solution 클래스를 다음과 같이 구현하세요:
•
Solution(int[] nums)
→ 객체를 배열 nums로 초기화합니다.
•
int[] reset()
→ 배열을 초기 상태로 되돌리고 반환합니다.
•
int[] shuffle()
→ 배열을 무작위로 섞은 결과를 반환합니다.
TIP : rand() 함수를 활용
예시
입력:
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Plain Text
복사
출력:
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
Plain Text
복사
설명:
Solution solution({ 1, 2, 3 });
solution.shuffle(); // 예: [3, 1, 2] 반환. [1,2,3]의 어떤 순열도 동일한 확률로 나올 수 있음
solution.reset(); // [1, 2, 3] 반환 (초기 상태로 복원)
solution.shuffle(); // 예: [1, 3, 2] 반환 (무작위 순열)
C++
복사
제약 조건
•
1 <= nums.length <= 50
•
10⁶ <= nums[i] <= 10⁶
•
배열의 모든 원소는 서로 다름
•
reset()과 shuffle()은 총 최대 10,000번 호출될 수 있음
class Solution
{
vector<int> original;
int n;
public:
Solution(const vector<int>& nums)
{
}
vector<int> reset()
{
}
vector<int> shuffle()
{
//make a copy of the original
vector<int> shuffled = original;
return shuffled;
}
};
C++
복사
Min Stack (최솟값을 추적하는 스택)
문제 설명
다음 연산들을 **상수 시간(O(1))**에 지원하는 스택을 설계하세요:
•
push(int val): 스택에 원소 val을 추가합니다.
•
pop(): 스택의 맨 위 원소를 제거합니다.
•
top(): 스택의 맨 위 원소를 반환합니다.
•
getMin(): 스택 내 최소값을 반환합니다.
클래스 정의
다음과 같이 MinStack 클래스를 구현하세요:
MinStack() // 스택 객체 초기화
push(int val) // val을 스택에 삽입
pop() // 맨 위 원소 제거
top() -> int // 맨 위 원소 반환
getMin() -> int // 현재 스택의 최소값 반환
C++
복사
모든 연산은 O(1) 시간 복잡도로 수행되어야 합니다.
예시
입력:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Plain Text
복사
출력:
[null,null,null,null,-3,null,0,-2]
Plain Text
복사
설명:
MinStack minStack;
minStack.push(-2); // [-2]
minStack.push(0); // [-2, 0]
minStack.push(-3); // [-2, 0, -3]
minStack.getMin(); // => -3
minStack.pop(); // [-2, 0]
minStack.top(); // => 0
minStack.getMin(); // => -2
C++
복사
제약 조건
•
2³¹ <= val <= 2³¹ - 1
•
pop, top, getMin는 항상 비어 있지 않은 스택에서 호출됩니다.
•
최대 30,000번까지 push, pop, top, getMin 함수가 호출될 수 있습니다.