2차원 벡터가 주어졌을 때, 이를 1차원처럼 순회할 수 있는 반복자(Iterator)를 설계하고 구현해야 합니다. 이 문제는 흔히 '2D 벡터 평탄화'라고 불리며, 다음과 같은 두 가지 핵심 메서드를 제공해야 합니다.
next() — 현재 위치의 다음 요소를 반환합니다.
hasNext() — 다음에 반환할 요소가 존재하는지 여부를 확인합니다.
동작 예시
입력이 [[1,2],[3],[4]]와 같이 주어지고, 아래 순서대로 메서드를 호출한다고 가정해 보겠습니다.
iterator.next(); iterator.next(); iterator.next(); iterator.hasNext(); iterator.hasNext(); iterator.next(); iterator.hasNext();
이때 출력 결과는 [1, 2, 3, true, true, 4, false]가 됩니다. 즉, 빈 행이 있더라도 건너뛰면서 전체 요소를 순서대로 탐색할 수 있어야 합니다.
풀이 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
2차원 배열
v를 멤버 변수로 정의합니다.생성자에서 2차원 배열을 받아 초기화하며, 행 포인터(
rowPointer)와 열 포인터(colPointer)를 0으로 설정합니다.총 행의 개수
n을 저장합니다.생성자와
next()내부에서, 현재 행이 비어 있는 경우(colPointer가 해당 행의 크기 이상인 경우) 다음 유효한 행까지 rowPointer를 이동시킵니다.next() 함수:
현재 위치의 값
x = v[rowPointer][colPointer]를 저장합니다.colPointer를 1 증가시키고, 만약 현재 행의 끝에 도달했다면 colPointer를 0으로 초기화하고 rowPointer를 증가시킨 뒤, 빈 행을 건너뛰도록 while 루프를 실행합니다.
저장해 둔 값 x를 반환합니다.
hasNext() 함수: rowPointer가 n과 같으면 더 이상 요소가 없으므로 false를, 그렇지 않으면 true를 반환합니다.
C++ 구현 코드
아래 예제를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Vector2D {
public:
int rowPointer, colPointer;
int n;
vector<vector<int>> v;
Vector2D(vector<vector<int>>& v){
this->v = v;
rowPointer = 0;
colPointer = 0;
n = v.size();
// 생성 시점에 빈 행이 있다면 건너뜀
while (rowPointer < n && colPointer >= v[rowPointer].size()){
rowPointer++;
}
}
int next(){
int x = v[rowPointer][colPointer];
colPointer++;
if (colPointer == v[rowPointer].size()) {
colPointer = 0;
rowPointer++;
// 빈 행은 건너뛰기
while (rowPointer < n && colPointer >= v[rowPointer].size()) {
rowPointer++;
}
}
return x;
}
bool hasNext(){
return !(rowPointer == n);
}
};
main(){
vector<vector<int>> v = {{1,2},{3},{4}};
Vector2D ob(v);
cout << (ob.next()) << endl;
cout << (ob.next()) << endl;
cout << (ob.next()) << endl;
cout << (ob.hasNext()) << endl;
cout << (ob.next()) << endl;
cout << (ob.hasNext());
}입력
ob.next() ob.next() ob.next() ob.hasNext() ob.next() ob.hasNext()
출력
1 2 3 1 4 0
정리 및 시간 복잡도
이 구현의 핵심은 두 개의 포인터(rowPointer, colPointer)를 활용해 2차원 구조를 선형적으로 탐색하는 것입니다. 각 호출 시 빈 행을 건너뛰는 로직 덕분에 중간에 비어 있는 벡터가 포함되어 있어도 올바르게 동작합니다.
시간 복잡도 측면에서 보면, next()와 hasNext() 호출 하나당 최악의 경우 O(n)이 소요될 수 있지만, 전체 순회 관점에서는 모든 요소를 한 번씩만 방문하므로 총 O(N)(N은 전체 요소 개수)입니다. 공간 복잡도는 추가 배열 없이 포인터만 사용하므로 O(1)입니다.