(C++) 2018 KAKAO BLIND RECRUITMENT[1차] 프렌즈4블록

1. 문제

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

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

 

2. 풀이

문제는 크게 3가지로 나눌 수 있다. 

 

step 1. 오른쪽 / 아래 / 대각선아래가 같은지 확인

step 2. 같은 것 표시

step 3. 같은 것 제거 후 아래로 내리기

step 4. 반복

 

따라서 나는 

step1. 이중 for문을 이용하여 보드의 모든 원소 오른쪽/아래/대각선아래 확인

step2. 같은 게 있다면 또다른 room 배열에 표시

step 3. room 배열에 표시된 원소를 다시 보드에서 삭제 후 보드 정리

step 4. 더이상 바뀔게 없을때까지 반복

순서로 진행하였다. 

 

여기서 보드 정리하는 부분이 어려웠는데 이유는 내가 인덱스를 헷갈렸기 때문,,ㅠㅠ 

예시에 나온 그림은 다음의 표와 같이 표시된다. 

T	T	T	A	N	T
R	R	F	A	C	C
R	R	R	F	C	C
T	R	R	R	A	A
T	T	M	M	M	F
T	M	M	T	T	J

이 표의 입력 방식은 다음과 같다

["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]

즉 위에서부터 입력이 먼저 들어오므로 아래로 당겨진다는 뜻은 인덱스가 뒤로 밀린다는 뜻을 말한다.

 

즉 아래로 밀린 표가  다음과 같을 때

			A
			A
T		T	F	N	T
T	T	F	R	A	A
T	T	M	M	M	F
T	M	M	T	T	J

["000A00", "000A00", "T0TFNT", "TTFRAA", "TTMMMF", "TMMTTJ"]

으로 앞의 index가 0으로 바뀌고 뒤의 index로 이동하게 된다.

이를 코드로 표현하면 다음과 같이 표현할 수 있다.

for (int k = i-1; k >=0; k--) {
	board[k + 1][j] = board[k][j]; //앞의 인덱스를 뒤의 인덱스로 밀기
	board[k][j] = 0; //앞의 인덱스 비우기
}

 

3. 코드

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<string> board) {
	int answer = 0;
    //시작용
	bool flag = true;
    
    //더이상 바뀔게 없을때까지
	while (flag) {
        
		//그 자리에서 바로 바꾸면 다음 비교를 할 수 없으므로
        //똑같이 생긴 배열을 하나 더 만든 뒤 방문했던 곳을 저장한다. 
        //라운드가 끝날때마다 초기화
        vector<vector<bool>> room(m, vector<bool>(n));
        
        //pop시작
        //flag = 바뀜
		flag = false; //바뀐게 없음
		for (int i = 0; i <m-1;i++) {
			for (int j = 0; j < n - 1; j++) {
                char now = board[i][j];
				if (now == 0)
					continue;
				if ((now == board[i][j + 1])&& (now== board[i + 1][j])&&(now== board[i + 1][j + 1])) {
					room[i][j] = 1;
					room[i][j+1] = 1;
					room[i+1][j] = 1;
					room[i + 1][j + 1] = 1;
					flag = true; //바뀌었으므로
				}
			}
		}
        
        //방문했던곳 체크 -> 아래로 끌고오기
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				//바뀐게 있으면
                if (room[i][j]==1) {
					answer++;
                    //앞의 인덱스를 터진곳까지 밀기
					for (int k = i-1; k >=0; k--) {
						board[k + 1][j] = board[k][j];
						board[k][j] = 0; //앞의 인덱스 비우기
					}
				}
			}
		}
	}
	return answer;
}

 

4. 그외

나는 좌표만 나오면 왜이리 어려운지ㅠㅠㅠ 머리가 뱅글뱅글 돌 것 같다...

쉽게 생각하면 풀리는 문제를 시간복잡도 적게 풀려고 하면 자꾸 에러가 난다..

알고리즘의 딜레마랄까...

새로운 방식 -> 망함 -> 기존의 방식 -> 풀림 -> 새로운방식의 다른 사람 풀이 -> 오 나도 다음에 저렇게 풀어봐야지->새로운 방식 ->망함 ->...

 

이런달까..?

그래도 언젠가 실력이 늘겠지...ㅠㅠ

오늘도 푼 것에 의의를 두며,,,,,
문제푸는데 세시간이나 걸렸다 ㅋㅋ ㅋㅋ
인생...쓰다..