문제 개요
이 문제에서는 숫자 m과 n개의 부분 리스트로 이루어진 중첩 리스트 A가 주어집니다. 총 m개의 전구가 있으며, 처음에는 모두 꺼져 있는 상태입니다. 또한 n개의 스위치가 있고, 각 스위치는 특정 전구들과 연결되어 있습니다. 즉, A[i]는 i번째 스위치를 눌렀을 때 켜질 수 있는 전구들의 집합을 의미합니다. 우리가 확인해야 할 것은 스위치들을 적절히 눌러서 모든 전구를 켤 수 있는지 여부입니다.
예를 들어 입력이 A = [[1, 4], [1, 3, 1], [2]], m = 4라고 한다면 출력은 True가 됩니다. 세 개의 스위치를 모두 누르면 1, 2, 3, 4번 전구가 모두 켜지기 때문입니다.
해결 접근 방법
이 문제는 집합(set) 자료구조를 활용하면 매우 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 모든 스위치가 제어할 수 있는 전구 번호를 하나의 집합에 모두 삽입합니다.
- 집합은 중복된 값을 자동으로 제거하므로, 최종적으로 집합에 남아 있는 원소의 개수는 '켤 수 있는 서로 다른 전구의 개수'와 같습니다.
- 이 개수가 m과 일치하면 모든 전구를 켤 수 있다는 뜻이므로 true를 반환하고, 그렇지 않으면 false를 반환합니다.
알고리즘 단계
집합 s를 하나 정의한다
i := 0부터 시작하여 i < A의 크기인 동안 i를 1씩 증가시키며 반복:
j := 0부터 시작하여 j < A[i]의 크기인 동안 j를 1씩 증가시키며 반복:
A[i][j]를 s에 삽입
s의 크기가 m과 같으면:
true 반환
그렇지 않으면:
false 반환예제 코드
다음 C++ 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<vector<int>> A, int m){
set<int> s;
for (int i = 0; i < A.size(); i++){
for (int j = 0; j < A[i].size(); j++){
s.insert(A[i][j]);
}
}
if (s.size() == m)
return true;
else
return false;
}
int main(){
vector<vector<int>> A = { { 1, 4 }, { 1, 3, 1 }, { 2 } };
int m = 4;
cout <<solve(A, m) << endl;
}입력
{ { 1, 4 }, { 1, 3, 1 }, { 2 } }, 4출력
1
출력 설명
세 스위치가 제어하는 전구 번호를 모두 모으면 {1, 4}, {1, 3}, {2}가 되고, 이를 집합에 넣으면 {1, 2, 3, 4}가 됩니다. 집합의 크기가 4로 m과 일치하므로 함수는 true를 반환하고, 화면에는 1이 출력됩니다.
복잡도 분석
- 시간 복잡도: O(N), N은 모든 부분 리스트에 포함된 전체 원소의 개수입니다. 각 원소를 한 번씩 순회하며 집합에 삽입하기 때문입니다.
- 공간 복잡도: O(m), 집합에는 최대 m개의 서로 다른 전구 번호만 저장됩니다.