프렌즈 4블록 - 카카오 기출

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

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

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    int check[31][31];
    memset(check,0,sizeof(check));
    bool toggle = true;
    while(toggle == true){
    //2*2 찾기 
      toggle= false;
     for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
          
           char pivot =  board[i][j];
            if(pivot !='z'){
            if(i+1<m && j+1<n){
           if((board[i+1][j]==pivot) && (board[i][j+1]==pivot)&&(board[i+1][j+1]==pivot)){
                toggle= true;
                if(check[i+1][j]==0){check[i+1][j]=1;answer++;}
                if(check[i][j+1]==0){check[i][j+1]=1;answer++;}
                if(check[i+1][j+1]==0){check[i+1][j+1]=1;answer++;}
                if(check[i][j]==0){check[i][j]=1;answer++;}
            }
        } }}  }
        
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
        
            if(check[i][j]==1){
                board[i][j]='z';
            }
       
        }
    }
        
        
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(i+1<m){
        if(board[i][j]!='z'&& board[i+1][j]=='z'){
            int x = i+1;
            while(board[x][j]=='z'&&x<m){
                x++;
            }
            x--;
            int k = i;
            while(k>=0&&x>=0){
            if(board[k][j]!='z'){
            int tmp = board[k][j];
            board[k][j]= board[x][j];
            board[x][j]=tmp;
            
            }
            k--;
            x--;
            }
            
        }}
                
        }
        
    }

        memset(check,0,sizeof(check));
        }
    return answer;
}

어떤 알고리즘 어떤 논리로? 

- 문자열을 전부 돌면서 만족하는 조건의 문자들을 모두 삭제하고 기조에 있던것을 다 내려오도록 구현을 했다. 

 

<JAVA>

import java.util.*;
class Solution {
    
    int[][] check;
    int dx[] = {0,1,1,0};
    int dy[] = {0,0,1,1};
    static int n,m;
   int answer =0;
    public boolean cango(int x, int y){
        return x>=0 && x<m && y>=0 &&y<n;
    }
    
    public class Pair{
        int x,y;
        Pair(int x, int y){
            this.x = x;
            this.y =y;
        }
    }
    
    public void move(String[] board){
            
        for(int j=0; j<n; j++){ //열
            
            int i = m-1;
            
            while(i>=0){
            
            while(cango(i,j)&&board[i].charAt(j)!='z'){
                i--;
            }
            
            int x = i; //맨 아래 제로 
            int y = j;
            
            while(cango(i,j)&&board[i].charAt(j)=='z'){
                i--;
            }
                int nx = i; //가장 가까운 캐릭터
                int ny = j; 
            
            if(cango(x,y)&&cango(nx,ny)){
                char tmp = board[x].charAt(y);
                StringBuilder sb = new StringBuilder(board[x]);
            
                sb.replace(y,y+1,Character.toString(board[nx].charAt(ny)));
                board[x] = sb.toString();
                
                sb = new StringBuilder(board[nx]);
                sb.replace(ny,ny+1,Character.toString(tmp));
                board[nx]=sb.toString();
            }
            
            i = x-1;
            
            } 
        }
            
        }
    
    
    
    public void delete(String[] board, ArrayList<Pair>arr ){
        
        for(Pair p : arr){
            int x = p.x;
            int y = p.y;
            for(int i=0; i<4; i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                StringBuilder sb = new StringBuilder(board[nx]);
                if(sb.charAt(ny)!='z'){sb.replace(ny,ny+1,Character.toString('z'));}
                board[nx]=sb.toString();
            }
        }
        
    }
    
    
    public boolean search(String[] board, ArrayList<Pair>arr){
        
        for(int i=0; i<m; i++){
            String str = board[i];
            for(int j=0; j<n; j++){
                
                int cnt=0;
                char c = str.charAt(j);
                
                if(c=='z'){continue;}
                
                for(int t=0; t<4; t++){
                    int nx = i+dx[t];
                    int ny = j+dy[t];
                    if(!cango(nx,ny)){break;}
                    if(c==board[nx].charAt(ny)){
                        cnt++;
                    }
                    else{
                        break;
                    }
                }
                if(cnt==4){
                   
                    arr.add(new Pair(i,j));
                }
                
            }
            
            
        }
        return arr.size()>0;
 }
    
    
    
    public int solution(int om, int on, String[] board) {
    
        m = om;
        n = on;
        check = new int[m][n];
        ArrayList<Pair>arr = new ArrayList<>();

        while(search(board,arr)){
            delete(board,arr);
            move(board);
            arr= new ArrayList<>();
        }
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i].charAt(j)=='z'){answer++;}
             //   System.out.print(board[i].charAt(j));
            }
              //System.out.println();
        }
        
        return answer;
    }
}

- String[] board -> char[][]board로 바꿔서 풀어야 훨씬 쉬울 문제이다. 

- 문자열에서 교환이나 삭제가 있을경우 StringBuilder을 써야한다 그러다보니 String[] board를 그대로 사용하게되면 코드가 더 복잡해진다.