[프로그래머스][C++] 표 병합
표 병합
문제 링크
분석
2차원 배열인 표의 크기는 50 x 50이며, 초기에는 모든 칸이 비어있습니다.
각 칸(셀)은 문자열 값을 가질 수 있고, 다른 칸과 병합될 수 있습니다.
commands는 명령어를 의미하며, 총 5가지 명령어가 존재합니다.
명령어는 순차적으로 실행됩니다.
"UPDATE r c value"r,c는 선택할 셀의 위치를 나타내며,value는 셀에 입력할 내용을 나타냅니다.- 특정 셀의 값을 업데이트합니다.
- 병합된 셀인 경우 병합된 모든 셀의 값을 함께 바꿔주어야 합니다.
"UPDATE value1 value2"value1은 선택할 셀의 값,value2는 셀에 입력할 내용을 나타냅니다.- 모든 셀 중에서 값이
value1인 셀을 찾아value2로 바꿉니다.
"MERGE r1 c1 r2 c2"r1,c1,r2,c2는 선택할 셀의 위치를 나타냅니다.- 특정 셀과 다른 셀을 병합합니다.
- 병합된 셀끼리는 하나의 그룹으로 값을 공유합니다.
- 만약 두 셀에서 값이 있을 경우
r1,c1의 셀 값을 우선 사용합니다.
"UNMERGE r c"r,c는 선택할 셀의 위치를 나타냅니다.- 선택한 셀의 병합 그룹을 해제하고, 문자열을 유지합니다.
- 그룹이 해제된 다른 셀은 빈 문자열을 가집니다.
"PRINT r c"r,c는 선택할 셀의 위치를 나타냅니다.- 선택한 셀의 값을 출력하며, 값이 없는 경우
"EMPTY"를 출력합니다.
풀이
#include <string>
#include <vector>
using namespace std;
// 각 셀의 부모 좌표
pair<int, int> parent[51][51];
// 셀의 실제 값 저장
string table[51][51];
// 유니온 파인드의 find 연산 (경로 압축 적용)
pair<int, int> find(int r, int c)
{
// 자기 자신이 부모라면 루트 노드
if (parent[r][c] == make_pair(r, c))
{
return {r, c};
}
// 루트 노드를 찾아 경로 압축
return parent[r][c] = find(parent[r][c].first, parent[r][c].second);
}
// 모든 셀을 독립적으로 초기화
void init()
{
for (int r = 1; r <= 50; ++r)
{
for (int c = 1; c <= 50; ++c)
{
// 자기 자신을 부모로 설정하고 값을 비운다.
parent[r][c] = {r, c};
table[r][c] = "";
}
}
}
void merge(int r1, int c1, int r2, int c2)
{
pair<int, int> p1 = find(r1, c1);
pair<int, int> p2 = find(r2, c2);
// 이미 병합된 셀인 경우
if (p1 == p2)
{
return;
}
// 그룹1, 그룹2의 값
string& v1 = table[p1.first][p1.second];
string& v2 = table[p2.first][p2.second];
// 그룹2를 그룹1에 흡수
parent[p2.first][p2.second] = p1;
// p2와 같은 그룹이었던 셀들을 모두 p1으로 값 업데이트
for (int r = 1; r <= 50; ++r)
{
for (int c = 1; c <= 50; ++c)
{
if (find(r, c) == p2)
{
parent[r][c] = p1;
}
}
}
// p1에서 기존 값이 없는 경우 p2의 값을 사용
if (v1.empty())
{
v1 = v2;
}
}
void unmerge(int r, int c)
{
// 현재 셀의 루트
pair<int, int> root = find(r, c);
// 루트 셀 값
string cellValue = table[root.first][root.second];
// 같은 그룹인 셀들을 모두 찾아 초기화
for (int i = 1; i <= 50; ++i)
{
for (int j = 1; j <= 50; ++j)
{
if (find(i, j) == root)
{
// 부모 좌표를 제거해 독립 셀로 되돌리며 값을 초기화한다.
parent[i][j] = {i, j};
table[i][j] = "";
}
}
}
// 병합 해제를 요청한 셀은 값 유지
table[r][c] = cellValue;
}
void updateCell(int r, int c, const string& value)
{
// 특정 셀 값을 갱신하기 위해 루트 셀을 찾아 갱신한다.
auto p = find(r, c);
table[p.first][p.second] = value;
}
void updateValue(const string& from, const string& to)
{
// 전체 셀 중 값이 from인 값을 to로 변경한다.
for (int r = 1; r <= 50; ++r)
{
for (int c = 1; c <= 50; ++c)
{
pair<int, int> p = find(r, c);
if (table[p.first][p.second] == from)
{
table[p.first][p.second] = to;
}
}
}
}
string printCell(int r, int c)
{
// 루트 셀을 찾는다.
pair<int, int> p = find(r, c);
// 값을 확인하고 출력한다.
string& value = table[p.first][p.second];
return (value.empty()) ? "EMPTY" : value;
}
vector<string> solution(vector<string> commands) {
vector<string> answer;
init();
for (const string& command : commands)
{
vector<string> tokens;
string token;
// 명령어 문자열을 공백 기준으로 파싱합니다.
for (char e : command)
{
if (e == ' ')
{
tokens.push_back(token);
token.clear();
}
else
{
token += e;
}
}
// 마지막 토큰을 추가
tokens.push_back(token);
// 명령어 처리
if (tokens[0] == "UPDATE")
{
if (tokens.size() == 4)
{
int r = stoi(tokens[1]);
int c = stoi(tokens[2]);
string value = tokens[3];
updateCell(r, c, value);
}
else
{
updateValue(tokens[1], tokens[2]);
}
}
else if (tokens[0] == "MERGE")
{
int r1 = stoi(tokens[1]);
int c1 = stoi(tokens[2]);
int r2 = stoi(tokens[3]);
int c2 = stoi(tokens[4]);
merge(r1, c1, r2, c2);
}
else if (tokens[0] == "UNMERGE")
{
int r = stoi(tokens[1]);
int c = stoi(tokens[2]);
unmerge(r, c);
}
else if (tokens[0] == "PRINT")
{
int r = stoi(tokens[1]);
int c = stoi(tokens[2]);
// 출력은 반환 값으로 저장
answer.push_back(printCell(r, c));
}
}
return answer;
}
성능 요약
시간 복잡도는 O(m)$입니다.
- 유니온 파인드(Union-Find) 함수인
find$O(\alpha(n)) \approx O(1)$- $alpha$는 아커만 함수의 역함수로, 실질적으로는 5이하입니다.
merge함수에서 전체 셀을 순회하면서 부모를 변경하는 반복문 $O(51 \times 51) \approx $O(1)$unmerge함수에서 전체 셀을 순회하면서 같은 그룹에 속한 셀을 분리하는 반복문 $O((51 \times 51) \times \alpha) \approx $O(1)$- 특정 셀의 값을 변경하는 함수 $O(\alpha(n)) \approx O(1)$
- 모든 셀의 특정 값을 변경하는 함수 $O(51 \times 51) \approx $O(1)$
- 특정 값을 찾아 반환하는 함수 $O(\alpha(n)) \approx O(1)$
- 명령어를 순회하는 반복문 $O(m)$
m은 명령어의 수를 의미합니다.
- $(O(1) + O(1) + O(1) + O(1) + O(1) + O(1)) \times O(m)$
공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.
- 각 셀의 부모를 저장하는 2차원 배열
pair<int, int> parent$O(51 \times 51) \approx $O(1)$ - 셀의 값을 저장하는 2차원 문자열 배열 $O(1)$
- $O(1) + O(1)$
테스트 성능
테스트 1 〉 통과 (0.10ms, 3.77MB)
테스트 2 〉 통과 (0.09ms, 3.68MB)
테스트 3 〉 통과 (0.06ms, 4.21MB)
테스트 4 〉 통과 (0.05ms, 3.72MB)
테스트 5 〉 통과 (0.06ms, 3.79MB)
테스트 6 〉 통과 (0.08ms, 4.2MB)
테스트 7 〉 통과 (0.07ms, 4.14MB)
테스트 8 〉 통과 (0.10ms, 4.13MB)
테스트 9 〉 통과 (0.19ms, 4.21MB)
테스트 10 〉 통과 (0.20ms, 4.21MB)
테스트 11 〉 통과 (0.37ms, 4.13MB)
테스트 12 〉 통과 (0.43ms, 4.21MB)
테스트 13 〉 통과 (1.91ms, 4.2MB)
테스트 14 〉 통과 (2.05ms, 4.11MB)
테스트 15 〉 통과 (2.85ms, 4.07MB)
테스트 16 〉 통과 (2.71ms, 4.17MB)
테스트 17 〉 통과 (2.92ms, 4.14MB)
테스트 18 〉 통과 (3.15ms, 4.21MB)
테스트 19 〉 통과 (4.81ms, 4.2MB)
테스트 20 〉 통과 (5.77ms, 4.2MB)
테스트 21 〉 통과 (9.16ms, 3.83MB)
테스트 22 〉 통과 (2.74ms, 4.22MB)
댓글남기기