📌 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/150366
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제설명
정사각형의 2차원 배열 속 좌표를 갖는 표의 셀의 병합과, 병합 해제, 값 변경 등의 구현을 해야하는 문제였습니다. 문제의 설명 중, 인접하지 않은 두 셀에 대해서도 병합이 가능하다는 설명이 있고, 두 점에 대하여 병합한다는 점에서 Union-Find 알고리즘 즉 서로소 집합 알고리즘이 적용될 수 있는 문제였습니다.
제약조건
- 1 ≤ commands의 길이 ≤ 1,000
- commands의 각 원소는 아래 5가지 형태 중 하나입니다.
- "UPDATE r c value"
- r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
- value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
- "UPDATE value1 value2"value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
- "MERGE r1 c1 r2 c2"
- r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
- "UNMERGE r c"
- r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
- "PRINT r c"
- r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
- commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.
풀이설명
문제에서 구현을 요하는 5가지 명령어에 대해 메서드를 만들고, 그 메서드를 수행하기 위한 메서드를 하나 더 만들어서 각 명령어 종류마다 작업을 수행하는 식으로 코드를 구현했습니다.
구현을 요하는 5가지 메서드 중 PRINT 메서드를 제외한 4가지 메서드의 동작을 그림으로 그려보면 아래와 같습니다.
실제 표의 각각의 셀에 어떤 변화를 줄 수 있는 메서드의 동작은 위의 그림과 같이 동작하는데,
여기서 유심히 보아야 할 점은 세 가지 입니다.
1. 병합할 때 인접한 셀끼리만 병합이 이루어지지 않을 수 있습니다.
2. UPDATE 시 병합된 셀에 접근한다면 루트 셀로 이동하여 값을 변경해야 합니다.
3. 병합을 해제 할 경우(UNMERGE) 루트 셀에 값이 남는 것이 아니라,
병합을 요청한 셀의 값이 남고 나머지는 초기화 된다는 점 입니다.
이러한 조건을 만족하며 명령을 수행한다면 그에 따른 셀의 변화는 아래와 같습니다.
(설명의 편의를 위해 2차원 좌표가 아닌 1차원 배열을 예시로 설명을 드리겠습니다.)
위와 같이 1차원 배열이 있고 4개의 명령어가 있다고 예시를 들겠습니다.
① MERGE : 셀을 병합하여, 3번 셀을 1번 셀과 같은 index를 갖도록 합니다.
② PRINT : 3번 인덱스를 프린트 하는데, 3번은 1번을 바라보고 있으므로 1번 인덱스의 값을 출력합니다.
③ UPDATE : 3번 인덱스를 업데이트 하는데, 3번은 1번을 바라보고 있으므로 1번 인덱스의 값을 업데이트 합니다. (루트 값 1개만 변경!)
④ UNMERGE : 3번 인덱스의 병합을 해제합니다. 예시에서는 2개의 셀이 병합되었지만 2개 이상의 셀이 병합된 경우라도 모든 셀의 병합이 해제되어야 합니다. 이번 경우에서는 1번과 3번이 해제되고 각각 초기 index를 가진 후 값은 3번 인덱스에 해당하는 곳에만 남습니다.
위와 같이 각 메서드들이 동작할 수 있도록 구현한다면 문제를 풀 수 있습니다.
❗ 주의
- 문제에서 주어진 테스트 케이스에서는 위와 같은 예시가 주어지지 않습니다.
- 그러나, 구현해야할 메서드들의 동작이 어떻게 구현이 되어야 하는지를 설명하기 위해 1차원 배열로 치환하여 설명한 것입니다.
2차원 좌표를 1차원 배열로 관리하기
문제에서는 2차원 배열 속 좌표를 기준으로 셀의 변경이 발생합니다.
그러나, 2차원 배열로 곧바로 구현한다면 값 조회시 2차원 배열을 탐색해야 하므로 다중 for문을 사용해야할 수도 있고 결정적으로는 알고리즘의 최적화를 위해 고려할 점이 많아져 더 복잡해질 수 있습니다.
그러므로, 2차원 좌표를 1차원 배열로 관리할 수 있는데 이를 위해 일반식을 세운다면 아래와 같습니다.
위의 일반식을 응용하여 명령어로 주어진 좌표를 관리하면
메서드를 구현할 때 조금 더 직관적으로 기능을 구현할 수 있습니다.
소스코드
Kotlin
import java.util.*
class Solution2 {
// static 변수 및 상수
companion object{
const val SIZE = 2500;
val parents = Array<Int>(SIZE+1, {0});
val values = Array<String>(SIZE+1, {""});
}
// init 함수를 통해 배열을 초기화 해줌.
private fun init(){
for( i in 1..SIZE){
parents?.set(i, i);
values?.set(i, "");
}
}
// union find 알고리즘
private fun find(a:Int) : Int {
return if(parents?.get(a) == a) a
else {
parents?.set(a, find(parents?.get(a)));
parents?.get(a);
};
}
private fun union(a:Int, b:Int):Boolean{
val rootA = find(a);
val rootB = find(b);
if(rootA == rootB) return false;
parents?.set(rootB, rootA);
return true;
}
// 2차원 좌표를 1차원 배열 인덱스로 컨버팅 해주는 함수
private fun getCvtIdx(r:Int, c:Int):Int{
val res = 50 * (r - 1);
return res + c;
}
fun solution(commands: Array<String>): Array<String> {
init();
val result = arrayListOf<String>();
for(cmd in commands){
val st = StringTokenizer(cmd);
centralProcess(st, result);
}
return result.toTypedArray(); // 코틀린의 문법, 스트림보다도 더 간단하게 한줄로 배열 변환 가능..!
}
private fun centralProcess(st:StringTokenizer, list:ArrayList<String>){
// switch case 문 보다 더 가독성이 좋은 코틀린의 when 절 사용 ^_^
// 모든 명령어는 동작이 첫 번째 토큰, 즉 헤더 부분에 있음,
when(st.nextToken()){ // header 라는 변수로 빼지 않고 바로 토큰에서 꺼내어 분기, < IntelliJ에서 권장 >
"UPDATE" -> {
if(st.countTokens() == 2){ // update value value
val value1 = st.nextToken();
val value2 = st.nextToken();
updateAll(value1, value2);
}else { // update r c value
val r = st.nextToken().toInt();
val c = st.nextToken().toInt();
val value = st.nextToken();
updateCell(r, c, value);
}
}
"MERGE" -> {
val r1 = st.nextToken().toInt();
val c1 = st.nextToken().toInt();
val r2 = st.nextToken().toInt();
val c2 = st.nextToken().toInt();
merge(r1, c1, r2, c2);
}
"UNMERGE" -> {
val r = st.nextToken().toInt();
val c = st.nextToken().toInt();
unMerge(r, c);
}
"PRINT" ->{
val r = st.nextToken().toInt();
val c = st.nextToken().toInt();
print(r, c, list);
}
}
}
// 배열 전체를 순회하여, 같은 값이 있는 경우 update만 해준다.
// merge 작업으로 인해 여러 값이 묶인 경우는 한 개의 값 만 바뀌므로
// 그냥 배열 전체를 순회하며 값을 바꾸어 주면 된다.
private fun updateAll(value1: String, value2: String) {
for(i in 1..SIZE){
if(value1?.equals(values[i])){
values[i] = value2;
}
}
}
// 특정 좌표에 접근하여 값을 바꾸는데,
// 핵심은 병합된 좌표에 접근할 수 있는데, 접근할 경우 루트로 이동해야하고
// 루트 값을 바꾸는 로직으로 구현해야 한다는 것! <문제 속 설명!>
private fun updateCell(r:Int, c:Int, value:String){
val cIdx = getCvtIdx(r, c); // 조회하고자 하는 좌표를 가져오고
val root = find(cIdx); // 루트 index를 찾은 다음
values[root] = value; // 루트의 값을 바꾼다.
}
// 두 셀을 병합하는 = union 함수가 사용되는 함수!
private fun merge(r1:Int, c1:Int, r2:Int, c2:Int){
val cIdx1 = getCvtIdx(r1, c1);
val cIdx2 = getCvtIdx(r2, c2);
val rootA = find(cIdx1);
val rootB = find(cIdx2);
if(rootA == rootB) return; // 이미 병합된 것이라면 작업을 종료
val rootValue = values[rootA].ifEmpty { values[rootB] }; // 코틀린의 문법!
values[rootA] = ""; // 각각의 루트 값을 비워주고
values[rootB] = "";
union(rootA, rootB); // 병합한 후
values[rootA] = rootValue; // 새로 할당
}
// 병합된 셀을 푸는 작업,
// 병합을 해제하는 경우 해제하고자 하는 좌표를 기준으로 해당 좌표만 값을 보존하고
// 연결되었던 (루트인 경우도 포함!) 모든 셀들은 초기화 시켜주는 함수
private fun unMerge(r:Int, c:Int){
val cIdx = getCvtIdx(r, c);
val root = find(cIdx); // 루트 인덱스를 탐색 후
val rootValue = values[root]; // 기존의 루트 값을 보존한다.
values[root] = "" // 루트를 초기화한 후
values[cIdx] = rootValue; // 조회하는 곳의 값을 루트 값으로 보존해줌
// 병합된 셀을 모두 찾고, 루트와 같으면, 리스트에 저장
// why? for문에서 찾자마자 바꿔버리면 연결이 끊겨서, 모든 연결을 제거하지 못함
val dList = arrayListOf<Int>();
for(i in 1..SIZE){
if(find(i) == root){
dList.add(i);
}
}
for(idx in dList){
parents[idx] = idx;
}
}
// 값을 조회하는 함수!
// 값을 조회할 때 단순히 index에 접근해서 조회하면 "" 를 조회할 수 있음
// why ? 병합 작업 시 루트 빼고 "" 처리 했으므로
// 그러므로 좌표를 조회할 때 현재 인덱스를 기준으로 루트 인덱스를 찾고
// 그 루트 인덱스에 저장된 값을 저장해야함
private fun print(r:Int, c:Int, list:ArrayList<String>){
val cIdx = getCvtIdx(r, c);
val root = find(cIdx);
val value = values[root].ifEmpty { "EMPTY" };
list.add(value);
}
}
fun main() {
val sol = Solution2();
val ans = sol.solution(
arrayOf<String>(
"UPDATE 1 1 menu",
"UPDATE 1 2 category",
"UPDATE 2 1 bibimbap",
"UPDATE 2 2 korean",
"UPDATE 2 3 rice",
"UPDATE 3 1 ramyeon",
"UPDATE 3 2 korean",
"UPDATE 3 3 noodle",
"UPDATE 3 4 instant",
"UPDATE 4 1 pasta",
"UPDATE 4 2 italian",
"UPDATE 4 3 noodle",
"MERGE 1 2 1 3",
"MERGE 1 3 1 4",
"UPDATE korean hansik",
"UPDATE 1 3 group",
"UNMERGE 1 4",
"PRINT 1 3",
"PRINT 1 4"
))
println(Arrays.toString(ans)); // 출력
}
Java
import java.util.*;
class Solution2 {
private static final int SIZE = 2500;
private static int[] parents;
private static String[] values;
//union find 구조
private static void make() {
parents = new int[SIZE+1];
values = new String[SIZE+1];
for(int i = 1 ; i <= SIZE ; i++) {
parents[i] = i;
values[i] = "";
}
}
private static int find(int a) {
if(parents[a] == a) return a;
else return parents[a] = find(parents[a]);
}
private static boolean union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if(aRoot == bRoot) return false;
parents[bRoot] = aRoot;
return true;
}
// 2차원 좌표를 1차원 배열 인덱스로 컨버팅 해주는 함수
private static int getConvertedIndex(int x, int y) {
int result = 50 * (x-1);
return result + y;
}
// solution
public String[] solution(String[] commands) {
List<String> result = new ArrayList<>();
make(); // index를 관리할 parents, 값을 관리할 value init!
for(String s : commands) {
StringTokenizer st = new StringTokenizer(s);
centralProcess(st, result);
}
int size = result.size();
String[] answer = result.stream().toArray(s -> new String[size]);
return answer;
}
//
private static void centralProcess(StringTokenizer st, List<String> result) {
String header = st.nextToken(); // 모든 명령어는 동작이 첫 번째 토큰, 즉 헤더 부분에 있음!
// 헤더를 기준으로 분기한다.
if("UPDATE".equals(header)) {
if(st.countTokens() == 2) { // update value value
String value1 = st.nextToken();
String value2 = st.nextToken();
updateAll(value1, value2);
}else if(st.countTokens() == 3) { // update r c value
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
String value = st.nextToken();
updateCell(r, c, value);
}
}else if("MERGE".equals(header)) { // merge r1 c1 r2 c2
int r1 = Integer.parseInt(st.nextToken());
int c1 = Integer.parseInt(st.nextToken());
int r2 = Integer.parseInt(st.nextToken());
int c2 = Integer.parseInt(st.nextToken());
merge(r1, c1, r2, c2);
}else if("UNMERGE".equals(header)) {
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
unMerge(r, c);
}else if("PRINT".equals(header)) {
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
print(r,c, result);
}
}
// UPDATE r c value
private static void updateCell(int r, int c, String value){
int cIdx = getConvertedIndex(r, c); // 1차원 배열에서의 index를 가져온다.
values[find(cIdx)] = value; // 값 대입
}
// UPDATE value value
private static void updateAll(String before, String after){
for(int i = 1 ; i <= SIZE; i++) {
if(before.equals(values[i])) {
values[i] = after;
}
}
}
// MERGE r1 c1 r2 c2
private static void merge(int r1, int c1, int r2, int c2){
int cIdx1 = getConvertedIndex(r1, c1);
int cIdx2 = getConvertedIndex(r2, c2);
int rootA = find(cIdx1);
int rootB = find(cIdx2);
if(rootA == rootB) return; // 값이 같으면 종료
String rootValue = values[rootA].isEmpty() ? values[rootB] : values[rootA];
values[rootA] = "";
values[rootB] = "";
union(rootA, rootB);
values[rootA] = rootValue;
}
// UNMERGE r c
private static void unMerge(int r, int c){
int cIdx = getConvertedIndex(r, c);
int root = find(cIdx);
String rootValue = values[root]; // 값을 찾고
values[root] = ""; // 루트를 초기화
values[cIdx] = rootValue; // 머지 풀 셀 값만 남기고
// 병합된 셀을 모두 찾고, 루트와 같으면, 리스트에 저장
// why? for문에서 찾자마자 바꿔버리면 연결이 끊겨서, 모든 연결을 제거하지 못함
List<Integer> deleteList = new ArrayList<>();
for(int i = 1; i <=SIZE; i++) {
if(find(i)==root) {
deleteList.add(i);
}
}
// 끊을 연결에 대해서만 초기화
for(int idx : deleteList) {
parents[idx] = idx; // 처음 인덱스로 초기화
}
}
// PRINT r c
private static void print(int r, int c, List<String> list){
int cIdx = getConvertedIndex(r, c);
int root = find(cIdx);
list.add(values[root].isEmpty() ? "EMPTY" : values[root]);
}
public static void main(String[] args) {
Solution2 sol2 = new Solution2();
String[] ans = sol2.solution(
new String[]{"UPDATE 1 1 menu",
"UPDATE 1 2 category",
"UPDATE 2 1 bibimbap",
"UPDATE 2 2 korean",
"UPDATE 2 3 rice",
"UPDATE 3 1 ramyeon",
"UPDATE 3 2 korean",
"UPDATE 3 3 noodle",
"UPDATE 3 4 instant",
"UPDATE 4 1 pasta",
"UPDATE 4 2 italian",
"UPDATE 4 3 noodle",
"MERGE 1 2 1 3",
"MERGE 1 3 1 4",
"UPDATE korean hansik",
"UPDATE 1 3 group",
"UNMERGE 1 4",
"PRINT 1 3",
"PRINT 1 4"});
System.out.println(Arrays.toString(ans));
}
}'알고리즘(Algorihtm) > PGR' 카테고리의 다른 글
| [PGR] 2019 카카오 개발자 겨울 인턴십 - 호텔 방 배정 (0) | 2023.07.20 |
|---|
