[프로그래머스][1차] 프렌즈4블록도움말

2018 KAKAO BLIND RECRUITMENT 였던 문제!

programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록

단순 구현 문제였다.

for문 여러 개 써서 해결!

처음 이 문제를 풀 때는 감이 도저히 안 오고 푸는 내내 힘겨웠던 기억이 있는데 지금도 다시 블록을 채우는 과정에서 약간 고생하긴 했지만 수월하게 풀었다.

bfs나 dfs이런거 없이 그냥 stack이나 for문 이용해서 풀어도 잘 풀리고 효율성 체크를 안 하기 때문에 충분히 시간 초과가 생기지는 않았다.

---

나의 구상 한 순서

1. 블럭 찾기
    1) 일단 찾아서 boolean에다가 표시할까?
    2) 왼쪽 위를 기준으로 3군데 탐색 → ↓ ↘
    3) 찾을 수 있는지 없는지 flag 필요함.
2. 찾은 블럭 비우기
    1) 완전 탐색하면서 boolean true 인 부분 비워지게 하기.
3. 빈 곳에 블럭 옮기기
    1) 값이 없다 -> continue;
    2) boolean이 true다
        1. stack에 넣기
        2. 빈 세로 찾기
        3.stack이용해서 다시 채우기

---

package com.example.demo;

import java.util.*;
class Solution {
	static boolean[][] remove;
	static char[][] map;
	static boolean isFind;
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        //m은 높이, n은 폭
        map = new char[m][n];
        
        for (int i = 0; i < m; i++) {
			map[i] = board[i].toCharArray();
		}
        
    	while(true) {
    		findBlocks(m, n);
    		
    		if(!isFind) break;
    		
    		clearProcess(m,n);
    		moveProcess(m, n);
    	}
    	
    	answer = isCount(m,n);

    	return answer;
    }
    
    //4블럭이 있는지 찾기.
    public static void findBlocks(int height, int width) {
    	isFind = false;
    	int[][] dir = {{0, 1},{1, 0},{1, 1}};//→ ↓ ↘
    	remove = new boolean[height][width];
    	
    	for (int i = 0; i < height-1; i++) {
			for (int j = 0; j < width-1; j++) {
				char c = map[i][j];
				boolean isFalse = false;
				
				//블럭인지 찾는 과정.
				for (int k = 0; k < 3; k++) {
					int nextR = i + dir[k][0];
					int nextC = j + dir[k][1];
					
					if(c=='0'|| c != map[nextR][nextC]) {
						isFalse = true;
						break;
					}
				}
				if(isFalse) continue;
				
				//4블럭이 완성 되면 제거될 대상으로 설정하고 찾았음을 표시/
				isFind = true;
				remove[i][j] = true;
				for (int k = 0; k < 3; k++) {
					int nextR = i + dir[k][0];
					int nextC = j + dir[k][1];
					remove[nextR][nextC] = true;
				}
			}
		}
    }
    
    //제거될 대상을 진짜로 제거.
    public static void clearProcess(int height, int width) {
    	for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				if(remove[i][j]) map[i][j] = '0';
			}
		}
    }
    
    //블록이 업데이트 되었으니 블록을 재배열. 
    //그냥 세로 라인의 모든 값을 전부 받아서 다시 넣어줬다.
    //(방법이 있기야 하겠지만 복잡할 것 같아서 이렇게 했다. 별 차이도 없을듯.)
    public static void moveProcess(int height, int width) {
    	Stack<Character> stack = new Stack<Character>();
    	for (int i = 0; i < width; i++) {
    		for (int j = 0; j < height; j++) {
				if(map[j][i] !='0' && !remove[j][i]) {
					stack.add(map[j][i]);
					map[j][i] = '0';
				}
			}
    		//stack을 통해 밑에서 부터 넣어주었다.
			int index = height-1;
			while(!stack.isEmpty()) {
				if(map[index--][i] !='0') continue;
				map[index+1][i] = stack.pop();
			}
		}
    }
    
    //결과를 알기 위핸 갯수를 셈.
    public static int isCount(int height, int width) {
    	int cnt = 0;
    	for (int i = 0; i < height; i++) {
    		for (int j = 0; j < width; j++) {
    			if(map[i][j] =='0') cnt++;
    		}
    	}
    	return cnt;
    }
}

예전에 stack대신 queue를 이용해서 푼 로직

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Solution {
	
	static int []dr = {0,1,1};
	static int []dc = {1,1,0};
	static Character [][]array;

    public int solution(int m, int n, String[] board) {
        int answer = 0;
        boolean isElse = true;
        array = new Character[m][n];
        for (int i = 0; i < m; i++) {
			for (int j = 0; j <n; j++) {
				array[i][j] = board[i].charAt(j);
			}
		}
        
        while(isElse) {
            
        	Queue<Dot> queue = new LinkedList<Dot>();
        	for (int i = 0; i < array.length; i++) {
				for (int j = 0; j < array.length; j++) {
					Dot dot =find( new Dot(i, j),m,n);
					
					if(dot != null) {
						queue.add(dot);
                    }
				}
			}
        	
        	if(queue.isEmpty()) break;
        	            
			while(!queue.isEmpty()) {
				Dot d = queue.poll();
				array[d.row][d.cor] ='#';
		    	for (int i = 0; i < dr.length; i++) {
		    		int nextX = d.row +dr[i];
		    		int nextY = d.cor +dc[i];
		    		array[nextX][nextY] = '#';
					
				}
			}
            //내리기
			for (int col = 0; col < n; col++) {
				Queue<Character> temp = new LinkedList<>();
				for (int row = m-1; row >=0 ; row--) {
					if(array[row][col] !='#') {
						temp.add(array[row][col]);
					}
				}
				for (int row = m-1; row >=0 ; row--) {
					if(!temp.isEmpty()) {
						array[row][col] = temp.poll();
					}else {
						array[row][col] ='#';
					}
				}
			}
        }
        for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if(array[i][j] =='#') answer++;
			}
		}
        //System.out.println(answer);
        return answer;
    }
    
    
    public static Dot find(Dot dot, int m, int n) {
    	Queue<Character> queue = new LinkedList<Character>();
    	
    	if(array[dot.row][dot.cor] == '#') return null;
    	
    	for (int i = 0; i < dr.length; i++) {
    		int nextX = dot.row +dr[i];
    		int nextY = dot.cor +dc[i];
			if(nextX < 0 || nextY < 0 || nextX>=m || nextY>=n) return null;
			if(array[dot.row][dot.cor] != array[nextX][nextY]) return null;
			
		}
    	
    	return dot;
    	
    }

}

class Dot{
	int row;//가로
	int cor;//세로
	Dot(int row, int cor){
		this.row = row;
		this.cor = cor;
	}
}​