Intro
2018년 카카오 블라인드 테스트에 출제된 문제로
구현이 주요하며, 이전에 올린 투포인터 연속된 부분 수열의 합에 나오는 투포인터 알고리즘 개념이 조금 활용해서 풀어 보았다.
투포인터 개념이 잘 이해가 되지 않는다면,
앞선 게시글
또는 댓글을 통해 이야기 해주시면, 최대한 고민되는 부분 또는 막히는 부분을 확인해 이해하실 수 있게 최대한 노력해 보도록 하겠습니다.
오늘은 최대한 간단하게 이야기를 하려한다.(과연)
항상 그렇듯 먼저 코드를 보자.
코드
import java.util.List;
import java.util.ArrayList;
class Solution {
public int solution(int m, int n, String[] board) {
int answer = 0;
char[][] blocks = new char[m][n];
//작업과 교체가 편리하게 변환
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
blocks[i][j] = board[i].charAt(j);
//2*2 블록 찾기//삭제//교체의 while
while(true){
List<int[]> list = new ArrayList<>();
//찾기
for(int i = 0; i < m - 1; i++){
for(int j = 0; j < n - 1; j++){
char c = blocks[i][j];
if(c=='-') continue;
if(blocks[i+1][j] == c && blocks[i][j+1] == c && blocks[i+1][j+1] == c)//4방위
list.add(new int[] {i,j});
}
}
if(list.size()==0) break; //탈출조건 더이상 겹치는 것이 없음
//삭제
for(int i =0; i < list.size(); i++){
int [] block = list.get(i);
int x = block[0], y = block[1];
blocks[x][y] = '-';
blocks[x+1][y] = '-';
blocks[x][y+1] = '-';
blocks[x+1][y+1] = '-';
}
//교체
for(int j = 0; j < n; j++){
int i = m-1;//끝
while(i>=0){
if(blocks[i][j] == '-'){
int k = i -1;
while(k>=0 &&blocks[k][j]=='-') k--;
if(k<0) break;
//swap
blocks[i][j]=blocks[k][j];//위에서 아래로
blocks[k][j]='-';//위에 부분 삭제됐다는 표시
}
i--;
}
}
}
//최종 값 확인.
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(blocks[i][j]=='-')answer++;
return answer;
}
}우선 간단하게 이야기 해 보면
위 코드의 형태가 가장 해당 문제를 짧게 푸는 방식 중 하나다.
해당 문제를 풀 때, 메서드 형태로 기능들을
나누는 방식도 좋은 풀이지만
아직 해당 방식에 대한 익숙도나 구현도가 정밀하지는 못해서
하나의 메서드 안에 기능별로 나누어 구현해 보았다.
주석처리된 부분처럼.
기본적으로 4가지 형태로 나누고
맨 앞의 포맷을 맞추는 부분까지 고려한다면 총 5가지의 작업이 이루어진다.
for문이 엄청 많아 보이고 실제로도 그렇다.
하지만, 해당 문제의 경우
입력형식이
2 ≦ n, m ≦ 30이기 때문에 끽 해 봐야
30의 30의 900을 900*900 순회하는 것이기 때문에
810,000번의 연산만 이루어진다.
시간 복잡도 측면에서 10^9 연산(10억 번)이 C언어 기준
1초 연산이므로, 81만번은 충분히 이중 for문으로 대략 100번은 넘게 수행해도 좋은 형태인 셈이다.
이처럼 조건 사항을 통해 문제를 분석해 보는 것도 풀이의 재미인 것 같다.
그럼 차근차근 다섯가지 형태의 내용과 부수적인 내용 1가지로 해서
6가지를 알아보자.
1. 포맷변경..char[][]을 사용한 이유.
맨 윗단에
public int solution(int m, int n, String[] board) {
int answer = 0;
char[][] blocks = new char[m][n];
//작업과 교체가 편리하게 변환
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
blocks[i][j] = board[i].charAt(j);위와 같은 작업을 한 이유는,
앞으로 해 나갈 방식인 '교체'에 대한 이유가 가장 큰 부분이다.
자바에서는 문자열 String이 불변객체이기 때문에 속도 측면에서
빈번한 수정 및 교체에 불리하다는 사실은 어렴풋이 듣거나
늘상 듣는 이야기 중 하나다.
즉, 게다가 문자열 하나씩만 끊어서 사용하고 있는데,
이는 다붆이 문자열로 나누어 달라는 것과 같은 형태이다.
m과 n이 주어지는 이유는 자바의 경우에는 length라는
메서드(length() 또는 static 변수(length)로 확인이 가능하지만,
갑자기TMI
C언어의 경우 저런 변수가 주어지지 않으면
길이를 확인할 방법이 없기 때문인 것으로 보인다.
즉, 실질적으로 문제에서 활용하는 변수는 board하나이며
나머지는 크게 관여하지 않아도 된다.
(다만, 활용하지 않을 이유도 없다.)
그냥, 과거에 저런 변수들 꼭 사용해야 되지 않을까?
어떤 의미가 있는 건가?
이런 의문이 있었는데
그 의문은 제로베이스 수강하면서,
코테 리뷰 강의에서 줍줍한 지식으로
해당 부분이 맞다는 걸 C를 주 개발 언어로 하시는
박사 과정의 선배님으로부터도 확인했다.
여튼 문자열을 문자형 이차원 배열로 blocks을
새로 만들어 교체를 편리하게 할 기초를 만들었다.
2. 교체할 값 찾기.
List<int[]> list = new ArrayList<>();
//찾기
for(int i = 0; i < m - 1; i++){
for(int j = 0; j < n - 1; j++){
char c = blocks[i][j];
if(c=='-') continue;
if(blocks[i+1][j] == c && blocks[i][j+1] == c && blocks[i+1][j+1] == c)//4방위
list.add(new int[] {i,j});
}
}교체할 값을 찾고, 해당 교체값을 List의 제네릭을
int[]로 선언해 삭제가 가능한 경우
4방위 자기자신(i,j) 오른쪽(i, j+1), 아래(i+1,j), 우하단 (i+1, j+1)
위와 같이 방위를 활용하는 연산식에 익숙해질 필요가 있다.
오른쪽으로 이동해서 확인할 때는 왼쪽을 확인해야 해서
뺄셈을 한다던지,
4방위가 아니라 8방위를 확인한다던지
방위에 관한 개념은 정말 다양하게 잡힌다.
다만, 여기서는 우측으로 확인하는 형태만을 구현했기 때문에 길이의 범위에 대한 부분만 관리해 줬지만,
만약 8방위와 같은 부분이 관리 대상이었다면 0부터 시작이 아니라 1부터 시작하는 형태로 구현이 가능했을 것이다.
그리고
4방위의 값이 같다면, 인덱스를 저장해 주고 다음은 값을 변경해 주는 부분이다.
3. (삭제)값 변경.
if(list.size()==0) break; //탈출조건 더이상 겹치는 것이 없음
//삭제
for(int i =0; i < list.size(); i++){
int [] block = list.get(i);
int x = block[0], y = block[1];
blocks[x][y] = '-';
blocks[x+1][y] = '-';
blocks[x][y+1] = '-';
blocks[x+1][y+1] = '-';
}위에서 '-'이 부분이 뭐지 싶을 텐데, 임의의 들어가지 않을
값을 만들어 준 것이다.
이렇게 해서, 관리해주는 것의 문자값은
개인의 취향과 기호에 맞게 하면 될 거 같다.
나는 A~Z가 아닌 값을 넣어주었다.
위의 탈출조건이라는 부분도 잘 볼 필요가 있는데
최종적으로 while문의 동작에서 전체를 탐색했을 때
삭제할 블록이 없다면 탈출한다는 의미로 이해하면 된다.
값 삭제의 경우 앞서 이야기한 방위의 개념의 연장이기에 빠르게 넘어가자.
4. (교체) 값 변경
마지막으로 해당 부분이 굉장히 주요한 부분이라고 생각한다.
그러면서도 해당 부분은 일종의
투포인터 개념이 적용되었다고 볼 수 있다.
//교체
for(int j = 0; j < n; j++){
int i = m-1;//끝
while(i>=0){
if(blocks[i][j] == '-'){
int k = i -1;
while(k>=0 &&blocks[k][j]=='-') k--;
if(k<0) break;
//swap
blocks[i][j]=blocks[k][j];//위에서 아래로
blocks[k][j]='-';//위에 부분 삭제됐다는 표시
}
i--;
}
}위의 코드가 조금 헷갈릴 수 있다.
그 이유는 첫 for문이 j로 시작되어서 그런데,
해당 부분을 위와 같이 구현한 이유는 j 부분을 고정하고,
i를 주 변경의 포인트로 잡아서 그렇다.
게다가 i의 변경 기준이
k라는 또다른 변수로 선언된다.
위의 개념에서 i와 k가 일종의 투포인터의 역할을 한다.
i의 경우 제일 끝을 나타내고, (m-1)
k의 경우 그 보다 작은 값 (i-1)로 표현한다.
이를 통해서, k의 값을 변경해 변경되어야 하는 값,
즉, 남아있는 문자를 찾는다.
'-'로 이미 삭제된 값들은 뛰어넘으며 값을 바꿔주고
//swap이라고 해준 것처럼 값을 변경해 줌으로써
다시 while문을 돌며 2*2 블록이 발생했는지를 체크한다.
여기서 앞서 말한 종료조건의 위치가 쉽게 다가올 수 있게 된다.
이러한 조정들이 다 있은 이후에도,
List<> list에 값이 들어가지 않는다면 길이가 0이라면
더이상 해당 while을 돌 필요 없이 탈출하면 된다.
while의 조건이 내부에서 결정되는 형태기 때문에
대전제를 true로 잡고
내부의 값의 변경이 탈출할 필요성이 있는지를 확인한 형태다.
5. 마지막 값 출력을 위한 확인
갑 출력을 위한 확인은 위의 while을 탈출하고
몇 개가 삭제 되었는지 확인하는 이중 for문으로
//최종 값 확인.
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(blocks[i][j]=='-')answer++;으로 구현되었다. 중괄호를 잘 안 쓰는 걸 선호하는 타입이라
위와 같은 형태로 구현했다.
이로써 모든 것이 끝이 났다.
- 부수적인 부분은
위의 설명에서 종료조건과 true 선언 이유
i--;를 작성한 것이 맨마지막이 아니라,
while(i>=0){i--;} 앞과 같이 미리 쓰고 문제를
써 나가면 좋다. 이런 자잘한 부분이다.
추가적으로 List<> list = new ArrayList<>();
이렇게 선언하는 것이 익숙하지 않을 수 있는데
ArrayList<> list = new ArrayList<>();
가 더 명시적이지 않냐! 할 수 있다.
다만 내가 쓰는 방식은 JDK 공식 문서의
권장사항 같은 부분이어서 사용하는 것이기 때문에
크게 이유가 있지는 않다.
해당 부분의 이유 중 하나는 List라는 인터페이스로
선언해, 언제든 LinkedList<>(); ArrayList<>();
로 손 쉽게 변형이 가능하다는 장점이 있다.
다만, 저렇게 되면 조금 문제가 될 수 있는 부분도 분명 있다.
TreeMap의 선언을 위와 같은 형태인
Map<String, Integer> map = new TreeMap<>();
으로 하게 되면
트리맵에만 있는 구현체인 lastKey()같은
메서드를 사용할 수 없다.
즉 인터페이스에 있는 기본적인 메서드만
사용할 수 있다.
해당 부분의 유형에서 한 번 헤맨 적이 있고,
구체적인 예시가 헤맸던 내용이었어서
해당 부분을 같이 마무리 삼아 올려둔다.
