[Algorithm] Grid Challenge

Grid Challenge

---

[Problem]

소문자로만 이루어진 2차원 배열 G가 있다. 

i행 j열의 원소를 G[i][j]라고 한다.

2차원 배열 G는 소문자로만 이루어져있다.

이 2차원 배열을 가지고 1가지의 연산만을 할 수 있다.

G[i][j]와 G[i][j+1]의 두 원소를 SWAP할 수 있다.

이 때, 주어진 배열 G가 swap연산만을 사용하여 

G[i][1]≤G[i][2]≤⋯≤G[i][N]$G[i][1]\le G[i][2]\le \cdots \le G[i][N]$ for 1≤i≤N$1\le i\le N$ and 
G[1][j]≤G[2][j]≤⋯≤G[N][j]$G[1][j]\le G[2][j]\le \cdots \le G[N][j]$ for 1≤j≤N

을 만족할 수 있는가? 

[Input Format]

첫 줄에는 총 TestCasts T.

각 테스트 케이스마다 2차원 배열 G의 크기인 N이 주어진다.

이후 N줄에 대해서 배열 G의 원소들이 입력된다.

[Output Format]

주어진 조건을 만족하면  "YES"

만족하지 않으면 "NO"

[Sample Input]

1
5
ebacd
fghij
olmkn
trpqs
xywuv

[Sample Output]

YES

[Solve]

2차원 배열 G가 해당 조건을 만족하는지 알기 위해서, 

1) 각 행에 대해서 bubbleSort를 수행.

2) bubbleSort를 수행한 결과에 대해서 열을 기준으로 조건을 만족하는지 검사.

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

    public static char[][] G = null;

    public static String[] GG = null;

    

    public static void main(String[] args) {

        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

Scanner scanner = new Scanner(System.in);

        

        int T = scanner.nextInt();

        

        for(int i=0; i<T; i++){

            int N = scanner.nextInt();

            scanner.nextLine();

            G = new char[N][];

            

            for(int r=0; r<N; r++){

                G[r] = scanner.nextLine().toCharArray();

            }// input

           

            gridChallenge(N);

        }

        

    }// end main

    

    public static void gridChallenge(int N){

        for(int i=0; i<N; i++){

            bubbleSort(i,N);

        }

        checkOrder(N);

    }

    

    public static void bubbleSort(int row, int N){    

        char tmp=0;

        for(int idx=1; idx<N; idx++){

            for(int go=0; go<N-idx;go++){

                //System.out.println("row, idx, go : " + row + ","+idx+","+go);

                if(G[row][go]>G[row][go+1]){

                    tmp = G[row][go] ;

                    G[row][go] = G[row][go+1];

                    G[row][go+1] = tmp;

                }

            }

        }

    }// end bubblesort

    

    public static void checkOrder(int N){

        for(int col=0; col<N; col++){

            for(int row=0; row<N-1; row++){

                if(G[row][col]>G[row+1][col]){

                    System.out.println("NO");

                    return ;

                }

            }

        }

        System.out.println("YES");

    }    

}