[JAVA] 프렌즈4블록 - String

한때 프렌즈팝 열심히 했었죠

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

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

 

생각과정

- 순서

1) 2*2 형태의 같은 블록이 있는지 확인 -> 없으면 종료

2) 1) 조건에 맞는 블록 터뜨리기(지우기)

3) 블록 밑에 빈공간 없도록 떨어뜨리기 -> 1)로 이동

- 2*2 형태가 여러개 겹쳐져도 모두 터뜨려야 함.

 => 1) 조건에 해당하는 블록에 지울 거라고 표시하기 (다른 블록과도 비교해야 하니까 문자를 바꾸면 안됨)

 => 문자를 바꾸지 않고 표시할 방법 => 기본 형태는 모두 대문자이니 소문자로 표시하면 다른 블록과 비교할 수 있음!

 => 1)에서 확인할 때 문자를 모두 toLowerCase로 맞춰주고, 

 => 2)에서는 소문자만 모두 지워버린다. 이때, '#'를 빈 칸을 나타내는 문자로 정한다.

- 2*2 형태는

(i, j) (i, j+1)

(i+1, j) (i+1, j+1)

이렇게 되어 있다.

- 3)에서 블록을 떨어뜨릴 때 진행 순서

a) 빈칸이 있는 row를 찾는다.

b) 빈칸 index의 column에 문자가 있는지 검사하고, 있으면 한칸 내린다.

  => 이때, 빈칸이 있는 row가 i라면, i-1부터 0까지 row의 값을 검사한다. (이때, column은 index로 동일하다)

  => 떨어뜨릴 블록이 빈 칸이라면, 그냥 통과시킨다.

  => 떨어뜨릴 블록의 윗칸이 빈칸이거나, 꼭대기에 있으면(row가 0이면) 마지막으로 떨어진 블록이므로 떨어지고 난 빈 공간을 '#'로 표시해준다.

구현

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        String pattern = "^[a-z]*$";
        int find = 0;
        
        //2*2 블록을 찾을 수 없을 때 종료
        while(true){
            find = 0;
            //2*2 블록 찾기
            for(int i=0;i<m-1;i++){
                for(int j=0;j<n-1;j++){
                    //윗줄에 빈칸이 있으면 바로 종료
                    if(board[i].charAt(j)=='#' || board[i].charAt(j+1)=='#')
                        continue;
                    char a1 = Character.toLowerCase(board[i].charAt(j));
                    char a2 = Character.toLowerCase(board[i].charAt(j+1));
                    char b1 = Character.toLowerCase(board[i+1].charAt(j));
                    char b2 = Character.toLowerCase(board[i+1].charAt(j+1));
                    if(a1 == a2 && a1 == b1 && b1 == b2){
                        //소문자로 바꾸기 - 지우기 예약
                        board[i] = board[i].substring(0, j) + a1 + a2 + board[i].substring(j+2);
                        board[i+1] = board[i+1].substring(0, j) + a1 + a2 + board[i+1].substring(j+2);
                        find = 1;
                    }
                }
            }
            //2*2 못찾으면 종료
            if(find == 0){
                break;
            }
            //지우기
            for(int i=0;i<m;i++){
                board[i] = board[i].replaceAll("[a-z]", "#");
            }
            //위에 있는 블록 떨어뜨리기
            int index = 0;
            for(int i=0;i<m;i++){
                index = 0;
                while(true){
                    if(index >= n) //빈칸 있는지 다 확인한 경우
                        break;
                    if(board[i].indexOf('#', index) != -1){
                        // 빈칸 인덱스 찾고 꼭대기까지 올라가면서 한칸씩 떨어뜨리기
                        index = board[i].indexOf('#', index);
                        for(int j=i-1;j>=0;j--){
                            if(board[j].charAt(index) != '#'){
                                if(j == 0){
                                    //아랫칸으로 떨어뜨리기
                                    board[j+1] = board[j+1].substring(0, index) + board[j].charAt(index) + board[j+1].substring(index+1);
                                      //마지막으로 떨어지는 칸은 빈칸 표시하기
                                    board[j] = board[j].substring(0, index) + "#" + board[j].substring(index+1);
                                }else{
                                    if(board[j-1].charAt(index) == '#'){
                                       //아랫칸으로 떨어뜨리기
                                        board[j+1] = board[j+1].substring(0, index) + board[j].charAt(index) + board[j+1].substring(index+1);
                                        //마지막으로 떨어지는 칸은 빈칸 표시하기
                                        board[j] = board[j].substring(0, index) + "#" + board[j].substring(index+1);
                                    }else{
                                        //아랫칸으로 떨어뜨리기
                                         board[j+1] = board[j+1].substring(0, index) + board[j].charAt(index) + board[j+1].substring(index+1);
                                    }
                                }
                               
                            }
                         
                        }
                         //indexOf할때 방금 찾은 인덱스의 한칸 뒤에서부터 찾게 하기
                        index += 1;
                    }
                    else{
                        //더이상 빈칸 없으면 종료
                        break;
                    }
                }
            }
        }
        //for(int i=0;i<board.length;i++){System.out.println(board[i]);}
        // # 개수 세기
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i].charAt(j) == '#')
                    answer +=1;
            }
        }
        return answer;
    }
}

 

결과

테스트 5만 통과 못했었는데 인덱스 오류 때문이었다..

 

String.replaceAll()

replaceAll 메소드에서 바뀔 문자의 조건을 넣는 인자에 정규 표현식을 넣을 수 있다고 한다. 구현 코드에서는 알파벳 소문자를 '#'으로 바꾸기 위해 '[a-z]'라는 식을 넣었다. [ ]는 배열을 의미한다.

 

문자열 안의 특정 문자를 모두 찾기

String.indexOf()를 활용한다. indexOf 메소드는 기본으로 첫번째로 찾은 문자의 인덱스만 반환하는데, 두번째 인자로 인덱스 값을 넣어주면 문자열의 해당 인덱스부터 탐색하게 된다.

이를 구현하기 위해서 인덱스를 저장할 변수가 필요하다. 아래는 간단한 구현 코드이다.

String str = "ababab";
int index = 0;

for(int i=0;i<str.length();i++){
    index = str.indexOf('a', index);
	if(index != -1) {//찾고싶은 문자가 있을 경우}
 }

 

참고

https://goni9071.tistory.com/6

java - 문자열 특정 문자 개수 구하기

https://stackoverflow.com/questions/13554017/how-to-replace-lowercase-letters-with-an-other-character

how to replace lowercase letters with an other character?

https://jamesdreaming.tistory.com/85

[ 자바 코딩 ] Java replace() vs replaceAll()