[level 2][1차] 프렌즈4블록 - 17679
성능 요약
메모리: undefined, 시간: .
구분
코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT
채점결과
Empty
제출 일자
2025년 01월 12일 01:33:30
문제 설명
프렌즈4블록
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.
블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.
만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.
위 초기 배치를 문자로 표시하면 아래와 같다.
TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ
각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.
입력 형식
- 입력으로 판의 높이
m, 폭n과 판의 배치 정보board가 들어온다. - 2 ≦
n,m≦ 30 board는 길이n인 문자열m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
출력 형식
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
입출력 예제
| m | n | board | answer |
|---|---|---|---|
| 4 | 5 | ["CCBDE", "AAADE", "AAABF", "CCBBF"] | 14 |
| 6 | 6 | ["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"] | 15 |
예제에 대한 설명
- 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
- 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
문제 풀이
level 2 치고 어려운 문제가 아닌가 싶다.
2x2 블록 찾기
전체 보드를 순회하면서 2x2 형태의 같은 문자 블록을 찾습니다
찾은 블록들의 위치를 Set에 저장 (중복 제거)
최적화를 위해 startPos를 활용하여 이미 체크한 위치는 건너뜁니다
블록 제거
- Set에 저장된 위치의 블록들을 'X'로 변경하여 제거 표시, 제거된 블록 개수는 Set의 크기로 계산
중력 적용
- 각 열마다 아래에서부터 위로 올라가면서 X를 발견하면 그 위치로 위의 블록을 떨어뜨림
- 이 과정을 각 위치에서 맨 아래까지 반복
주의할 점
1. Set 사용
- 2x2 블록의 위치를 저장할 때 Set을 사용하여 중복을 제거
- 위치는 i * M + j 형태로 1차원 정수로 변환하여 저장
- 각 사이클 후에 반드시 Set을 clear해야 함 (중력으로 인해 새로운 블록이 형성될 수 있기 때문)
2. startPos 최적화
- 2x2 블록을 발견하면 그 위치를 startPos에 저장
- 다음 순회때는 그 위치부터 시작하여 불필요한 순회를 줄임
- 단, 중력 적용 후 새로운 사이클 시작시에는 (0,0)부터 다시 체크해야 함
3. 중력 처리
- 각 열별로 처리.
- 아래에서부터 위로 올라가면서 X를 발견하면 현재 위치부터 맨 아래까지 swap을 반복하여 블록을 떨어뜨림
시간 복잡도
- 보드의 크기가 N x M일 때 각 사이클마다 보드 전체 순회: O(NM)
- 중력 적용: O(N²M) (각 열마다 각 행을 체크하고 최대 N번 swap 가능)
- 전체 블록이 모두 제거될 때까지 반복될 수 있으므로 최악의 경우 O(N³M)
코드
import java.util.*;
class Solution {
static int N, M, res=0;
static char[][] map;
// 한 사이클마다 지워야 할 부분을 Set에 넣어서 넣어서 크기로 개수체크함 -> 사이클마다 clear 필수(밑으로 내려오면 중복됨)
static Set<Integer> toBeDeleted = new HashSet<>();
// startPos 쓴 이유 : 체크했을 떄 2x2있다고 찾은 위치부터 시작하고자. 필요없는순회 제거
// 주의점 : 중력으로 밑으로 내린 후 isEnd 적용때마다는 (0,0) 부터 해야하고, 2x2제거만 startPos부터
static int[] startPos = {0, 0};
public int solution(int m, int n, String[] board) {
N = board.length;
M = board[0].length();
map = new char[N][M];
for(int i=0; i<N; i++){
map[i] = board[i].toCharArray();
}
while(!isEnd()){
for(int i=0; i<N-1; i++){
for(int j=0; j<M-1; j++){
// startPos 건너뛰는 부분 (순회 최적화)
if(i < startPos[0]) continue;
else if(i==startPos[0] && j < startPos[1]) continue;
else{
if(check2by2(i, j)) {
// 지울 부분을 정수로 구분하고자 i열 j행을 고유의 숫자 0 ~ (N*N-1)로 표시
toBeDeleted.add(i * M + j);
toBeDeleted.add(i * M + j+1);
toBeDeleted.add((i+1) * M + j);
toBeDeleted.add((i+1) * M + j+1);
}
}
}
}
for(int pos : toBeDeleted) { // Set에 추가
int i = pos / M;
int j = pos % M;
map[i][j] = 'X';
}
// 개수 추가 및 Set 비우기
res += toBeDeleted.size();
System.out.println(toBeDeleted);
toBeDeleted.clear();
// 빈칸만큼 아래로 매꾸기
goDown();
// 중력체크(출력)
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
System.out.print(map[i][j]);
}
System.out.println();
}
}
return res;
}
private boolean check2by2(int r, int c){
if(map[r][c] == 'X') return false;
return map[r][c]==map[r][c+1] && map[r][c+1]==map[r+1][c] && map[r+1][c]==map[r+1][c+1];
}
private boolean isEnd(){
for(int i=0; i<N-1; i++){
for(int j=0; j<M-1; j++){
if(check2by2(i, j)) {
startPos[0] = i;
startPos[1] = j;
return false;
}
}
}
return true;
}
private void goDown(){ // 아래부터 swap하며 맨 위 행까지 올라가기
for(int j=0; j<M; j++) {
for(int i=N-2; i>=0; i--) {
for(int k=i; k<N-1; k++) {
if(map[k][j] != 'X' && map[k+1][j] == 'X') {
swap(k, j);
}
}
}
}
}
private void swap(int i, int j){
char tmp = map[i][j];
map[i][j] = map[i+1][j];
map[i+1][j] = tmp;
}
}