2차원 벡터 평탄화 (Flatten 2D Vector)
2차원 벡터(2D vector)를 1차원처럼 순회할 수 있도록 평탄화(flatten) 하는 이터레이터(iterator)를 설계하세요. 이 이터레이터는 next 와 hasNext 연산을 지원해야 합니다.
Vector2D 클래스를 구현하세요:
•
Vector2D(int[][] vec): 2차원 벡터 vec로 객체를 초기화합니다.
•
next(): 2차원 벡터에서 다음 원소를 반환하고, 포인터를 한 칸 앞으로 이동합니다. next 호출은 항상 유효하다고 가정해도 됩니다.
•
hasNext(): 아직 반환하지 않은 원소가 남아 있으면 true, 없으면 false를 반환합니다.
예시:
입력
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
출력
[null, 1, 2, 3, true, true, 4, false]
설명
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next(); // 1 반환
vector2D.next(); // 2 반환
vector2D.next(); // 3 반환
vector2D.hasNext(); // True 반환
vector2D.hasNext(); // True 반환
vector2D.next(); // 4 반환
vector2D.hasNext(); // False 반환
Plain Text
복사
주의 사항(Notes):
1.
Vector2D에 선언한 클래스 변수/정적 변수(static/class variables)는 여러 테스트 케이스에 걸쳐 유지될 수 있으므로, 반드시 초기화(RESET) 해주세요. 자세한 내용은 여기를 참고하세요.
2.
next() 호출은 항상 유효합니다. 즉, next()가 호출될 때는 2차원 벡터에 최소 한 개 이상의 다음 원소가 존재합니다.
제약 조건:
•
0 <= vec.length <= 200
•
0 <= vec[i].length <= 500
•
-500 <= vec[i][j] <= 500
•
next와 hasNext는 최대 10^5번 호출됩니다.
틱택토 설계 (Design Tic-Tac-Toe)
n x n 보드에서 두 명이 플레이하는 틱택토 게임에 대해 아래 규칙을 가정합니다:
1.
각 수는 항상 유효하며, 비어 있는 칸에만 놓입니다.
2.
승리 조건이 달성되면 더 이상 수를 둘 수 없습니다.
3.
어떤 플레이어가 가로/세로/대각선 중 하나에 자신의 표시를 n개 연속으로 놓으면 승리합니다.
TicTacToe 클래스를 구현하세요:
•
TicTacToe(int n): 보드 크기 n으로 객체를 초기화합니다.
•
int move(int row, int col, int player): player(id가 1 또는 2인 플레이어)가 (row, col) 칸에 표시를 둡니다. 수는 항상 유효하며, 두 플레이어는 번갈아 수를 둡니다. 반환값은 다음과 같습니다.
◦
수를 둔 뒤 승자가 없으면 0
◦
player 1이 승리하면 1
◦
player 2가 승리하면 2
예시 1:
입력
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
출력
[null, 0, 0, 0, 0, 0, 0, 1]
설명
TicTacToe ticTacToe = new TicTacToe(3);
player 1은 "X", player 2는 "O"라고 가정합니다.
ticTacToe.move(0, 0, 1); // 0 반환 (승자 없음)
|X| | |
| | | | // player 1이 (0, 0)에 둠
| | | |
ticTacToe.move(0, 2, 2); // 0 반환 (승자 없음)
|X| |O|
| | | | // player 2가 (0, 2)에 둠
| | | |
ticTacToe.move(2, 2, 1); // 0 반환 (승자 없음)
|X| |O|
| | | | // player 1이 (2, 2)에 둠
| | |X|
ticTacToe.move(1, 1, 2); // 0 반환 (승자 없음)
|X| |O|
| |O| | // player 2가 (1, 1)에 둠
| | |X|
ticTacToe.move(2, 0, 1); // 0 반환 (승자 없음)
|X| |O|
| |O| | // player 1이 (2, 0)에 둠
|X| |X|
ticTacToe.move(1, 0, 2); // 0 반환 (승자 없음)
|X| |O|
|O|O| | // player 2가 (1, 0)에 둠
|X| |X|
ticTacToe.move(2, 1, 1); // 1 반환 (player 1 승리)
|X| |O|
|O|O| | // player 1이 (2, 1)에 둠
|X|X|X|
Plain Text
복사
제약 조건:
•
2 <= n <= 100
•
player는 1 또는 2입니다.
•
0 <= row, col < n
•
서로 다른 move 호출에 대해 (row, col)은 항상 유일합니다(같은 칸에 두 번 두지 않음).
•
move는 최대 n^2번 호출됩니다.
추가 질문(Follow-up): move() 연산을 매번 O(n^2)보다 더 빠르게 할 수 있나요?
이진 트리 직렬화/역직렬화 (Serialize and Deserialize Binary Tree)
직렬화(Serialization) 란 자료구조/객체를 비트 시퀀스 형태로 변환하는 과정입니다. 이렇게 변환하면 파일이나 메모리 버퍼에 저장하거나, 네트워크를 통해 전송한 뒤, 동일하거나 다른 환경에서 다시 복원할 수 있습니다.
이진 트리를 직렬화하고 역직렬화하는 알고리즘을 설계하세요. 직렬화/역직렬화 방식에는 제한이 없습니다. 핵심은 이진 트리를 문자열로 직렬화할 수 있고, 그 문자열을 이용해 원래 트리 구조로 복원(역직렬화) 할 수 있어야 한다는 점입니다.
추가 설명(Clarification):
예시 1:
입력: root = [1,2,3,null,null,4,5]
출력: [1,2,3,null,null,4,5]
Plain Text
복사
예시 2:
입력: root = []
출력: []
Plain Text
복사
제약 조건:
•
트리 노드 수는 [0, 10^4] 범위입니다.
•
-1000 <= Node.val <= 1000
삽입/삭제/랜덤 추출 O(1) (Insert Delete GetRandom O(1))
RandomizedSet 클래스를 구현하세요:
•
RandomizedSet(): RandomizedSet 객체를 초기화합니다.
•
bool insert(int val): 값 val이 없다면 set에 삽입합니다. 삽입이 새로 일어났다면 true, 이미 존재했다면 false를 반환합니다.
•
bool remove(int val): 값 val이 있다면 set에서 삭제합니다. 삭제에 성공하면 true, 존재하지 않으면 false를 반환합니다.
•
int getRandom(): 현재 set에 있는 원소 중 하나를 랜덤으로 반환합니다(이 메서드가 호출될 때 최소 한 개 이상의 원소가 존재함이 보장됩니다). 각 원소는 동일한 확률로 반환되어야 합니다.
각 함수는 평균적으로 O(1) 시간 복잡도로 동작하도록 구현해야 합니다.
예시 1:
입력
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
출력
[null, true, false, true, 2, true, false, 2]
설명
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 1 삽입, true 반환
randomizedSet.remove(2); // 2 없음, false 반환
randomizedSet.insert(2); // 2 삽입, true 반환. set = [1,2]
randomizedSet.getRandom(); // 1 또는 2 중 랜덤 반환
randomizedSet.remove(1); // 1 삭제, true 반환. set = [2]
randomizedSet.insert(2); // 이미 있음, false 반환
randomizedSet.getRandom(); // 원소가 2뿐이므로 항상 2 반환
Plain Text
복사
제약 조건:
•
-2^31 <= val <= 2^31 - 1
•
insert, remove, getRandom은 최대 2 * 10^5번 호출됩니다.
•
getRandom이 호출될 때 자료구조에는 최소 1개의 원소가 존재합니다.