[프로그래머스] 프렌즈4블록

2018 카카오 채용 코딩 테스트 문제입니다.

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

문제 확인

 

구현 문제입니다.

 

풀이

 

3개의 과정을 정확하게 나누어 구현하여야 합니다.

1. 지울 블록들을 찾습니다. : 조건문
2. 찾은 블록들을 한 번에 지웁니다. : visited 배열 활용
3. 빈 공간들을 블록을 떨어뜨려 채웁니다. : 인덱싱

 

3번 단계에서 메모리 접근 시간을 빠르게 하기 위해 배열을 전치시켜 떨어뜨릴 때 ary[i][0~j] 한 줄에서 해결할 수 있도록 합니다. 또한 0번 인덱스부터 접근할 수 있도록 전치시킬 때 회전시켜 입력할 수 있도록 합니다.

for (int i = 0; i < m; i++)
	for (int j = 0; j < n; j++)
		ary[j][m - i - 1] = board[i][j];

 

1번 과정은 간단하게 빈 공간이 아닌 블록이 오른쪽, 아래쪽, 오른쪽 아래 대각선 방향의 블록이 모두 같다면 지울 블록으로 선택합니다. 정사각형 형태의 4개의 블록을 검사하므로 n-1, m-1 이전 범위까지만 탐색하면 됩니다.

for (int i = 0; i < n - 1; i++) {
	for (int j = 0; j < m - 1; j++) {
		if (ary[i][j] && ary[i][j] == ary[i][j + 1] && ary[i][j] == ary[i + 1][j] && ary[i][j] == ary[i + 1][j + 1]) {
			visited[i][j] = visited[i][j + 1] = visited[i + 1][j] = visited[i + 1][j + 1] = 1;
			f = 1;
		}
	}
}

변수 f는 지워야 할 블록이 생기면 3번까지 진행한 후 한번 더 이 과정을 진행해야 하기 위한 변수입니다.

 

2번 과정은 간단하게 visited가 체크되어 있는 배열을 지워줍니다.

for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
		if (visited[i][j]) {
			ary[i][j] = 0;
			answer++;
		}
memset(visited, 0, sizeof visited);

 

3번 과정에선 가장 먼저 나오는 빈 공간의 위치를 pos로 둔 후 이후에 나오는 블록들을 pos 위치에 순서대로 채워줍니다.

for (int i = 0; i < n; i++) {
	int pos = 0;
	while (pos < m && ary[i][pos])pos++;
	for (int j = pos + 1; j < m; j++) {
		if (ary[i][j]) {
				ary[i][pos++] = ary[i][j];
			ary[i][j] = 0;
		}		
	}
}

 

코드

#include <iostream>
 
#include <string>
#include <vector>
 
using namespace std;
 
int solution(int m, int n, vector<string> board) {
    int answer = 0;
    char ary[30][30] = { 0 };
 
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            ary[j][m - i - 1] = board[i][j];//블록을 떨어뜨릴 때 매모리 접근성 향상
 
    bool visited[30][30] = { 0 };
    bool f = 1;
    while (f) {//지운 블록이 없을 때까지
        f = 0;
        for (int i = 0; i < n - 1; i++) {//검사
            for (int j = 0; j < m - 1; j++) {
                
                if (ary[i][j] && ary[i][j] == ary[i][j + 1] && ary[i][j] == ary[i + 1][j] && ary[i][j] == ary[i + 1][j + 1]) {
                    visited[i][j] = visited[i][j + 1] = visited[i + 1][j] = visited[i + 1][j + 1] = 1;
                    f = 1;
                }
            }
        }
        if (f) {
            for (int i = 0; i < n; i++)//블록 지우기
                for (int j = 0; j < m; j++)
                    if (visited[i][j]) {
                        ary[i][j] = 0;
                        answer++;
                    }
            memset(visited, 0, sizeof visited);
 
            for (int i = 0; i < n; i++) {//빈공간 떨어뜨리기
                int pos = 0;
                while (pos < m && ary[i][pos])pos++;
                for (int j = pos + 1; j < m; j++) {
                    if (ary[i][j]) {
                        ary[i][pos++] = ary[i][j];
                        ary[i][j] = 0;
                    }    
                }
            }
        }
    }
    
    return answer;
}
 
int main() {
    vector<string> t = { "ttbb", "aacc","aabb", "zzcc","aabb", "aacc" };
    solution(6, 4, t);
 
}

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.93MB)
테스트 2 〉	통과 (0.01ms, 3.72MB)
테스트 3 〉	통과 (0.01ms, 3.95MB)
테스트 4 〉	통과 (0.01ms, 3.95MB)
테스트 5 〉	통과 (0.36ms, 3.94MB)
테스트 6 〉	통과 (0.04ms, 3.96MB)
테스트 7 〉	통과 (0.01ms, 3.97MB)
테스트 8 〉	통과 (0.01ms, 3.96MB)
테스트 9 〉	통과 (0.01ms, 3.93MB)
테스트 10 〉	통과 (0.01ms, 3.96MB)
테스트 11 〉	통과 (0.02ms, 3.94MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0