[HackerRank] Grid Challenge

Problem

---

Given a square grid of characters in the range ascii[a-z], rearrange elements of each row alphabetically, ascending. Determine if the columns are also in ascending alphabetical order, top to bottom. Return YES if they are or NO if they are not.

 

Example

grid = ['abc', 'ade', 'efg']

The grid is illustrated below.

a b c
a d e
e f g

The rows are already in alphabetical order. The columns a a e, b d f and c e g are also in alphabetical order, so the answer would be YES. Only elements within the same row can be rearranged. They cannot be moved to a different row.

 

Function Description

Complete the gridChallenge function in the editor below.

gridChallenge has the following parameter(s):

• string grid[n]: an array of strings

Returns

• string: either YES or NO

Input Format

The first line contains t, the number of testcases.

Each of the next t sets of lines are described as follows:
- The first line contains n, the number of rows and columns in the grid.
- The next n lines contains a string of length n

Constraints

1 ≤ t ≤ 100
1 ≤ n ≤ 100
Each string consists of lowercase letters in the range ascii[a-z]

Output Format

For each test case, on a separate line print YES if it is possible to rearrange the grid alphabetically ascending in both its rows and columns, or NO otherwise.

Sample Input

STDIN   Function
-----   --------
1       t = 1
5       n = 5
ebacd   grid = ['ebacd', 'fghij', 'olmkn', 'trpqs', 'xywuv']
fghij
olmkn
trpqs
xywuv

Sample Output

YES

Explanation

The 5x5 grid in the 1 test case can be reordered to

abcde
fghij
klmno
pqrst
uvwxy

This fulfills the condition since the rows 1, 2, ..., 5 and the columns 1, 2, ..., 5 are all alphabetically sorted.

---

주어진 grid 리스트는 문자로 이루어진 2차원 그리드입니다. 이 그리드에서 각 행의 문자들을 오름차순으로 정렬한 후, 모든 열도 오름차순으로 정렬되었는지 확인하는 함수를 작성하세요.

 

입력 및 출력

• 입력으로는 각 행이 문자열로 구성된 리스트 grid가 주어집니다.
• 각 행을 정렬한 후, 모든 열이 알파벳 순서로 되어 있으면 YES, 그렇지 않으면 NO를 반환합니다.

예제

• 입력:

["abcde", "fghij", "klmno", "pqrst", "uvwxy"]

 

• 출력: YES

 

Solution

---

public static String gridChallenge(List<String> grid) {
    // 각 행을 오름차순으로 정렬
    for (int i = 0; i < grid.size(); i++) {
        char[] row = grid.get(i).toCharArray();
        Arrays.sort(row);
        grid.set(i, new String(row)); // 정렬된 행으로 업데이트
    }

    // 각 열이 오름차순인지 확인
    int columnCount = grid.get(0).length();
    for (int col = 0; col < columnCount; col++) {
        for (int row = 1; row < grid.size(); row++) {
            // 이전 행의 현재 열 값과 비교하여 순서 확인
            if (grid.get(row).charAt(col) < grid.get(row - 1).charAt(col)) {
                return "NO";
            }
        }
    }

    return "YES";
}

 

 

• 행 정렬: 각 행의 문자열을 문자 배열로 변환하고 Arrays.sort()를 사용해 오름차순으로 정렬한 후, 다시 문자열로 변환해 grid 리스트를 업데이트합니다.
• 열 정렬 확인: 첫 번째 행부터 순차적으로 이전 행의 같은 열 값과 비교하여, 현재 열 값이 더 작은 경우 NO를 반환합니다. 모든 열이 오름차순이면 YES를 반환합니다.
• 이 코드는 O(n * m log m) 시간 복잡도로 효율적으로 동작하며, n은 행 수, m은 각 행의 길이입니다.

1. toCharArray()

• toCharArray() 메서드는 문자열을 문자 배열(char[])로 변환합니다.
• 예를 들어, grid.get(i)가 "fghij"일 때 toCharArray()를 사용하면 ['f', 'g', 'h', 'i', 'j'] 배열이 생성됩니다.
• 이렇게 문자 배열로 변환하면 배열 내 문자들을 쉽게 조작할 수 있어, 이후 Arrays.sort(row)를 사용해 알파벳 오름차순 정렬을 수행할 수 있습니다.

2. Arrays.sort(row)

• Arrays.sort() 메서드는 배열의 요소를 오름차순으로 정렬합니다.
• 이 메서드는 O(m log m)의 시간 복잡도로 동작하며, m은 배열의 길이입니다.
• row 배열을 알파벳순으로 정렬한 결과가 된다면, 예를 들어 ['f', 'h', 'g', 'j', 'i'] 배열은 ['f', 'g', 'h', 'i', 'j']가 됩니다.
• 이를 통해 각 행이 오름차순 정렬된 상태가 됩니다.

3. grid.set(i, new String(row))

• new String(row)는 정렬된 row 배열을 다시 문자열로 변환합니다.
• grid.set(i, new String(row))는 grid 리스트의 i번째 요소를 정렬된 문자열로 업데이트합니다.
• 예를 들어, grid의 i번째 행이 "fghij"였다면, 이제 정렬된 "fghij"가 그 위치에 저장됩니다.
• 이를 통해 grid는 각 행이 알파벳 오름차순으로 정렬된 상태를 가지게 됩니다.

4. if (grid.get(row).charAt(col) < grid.get(row - 1).charAt(col))

• 이 조건문은 모든 열이 오름차순으로 정렬되어 있는지 확인하는 핵심 부분입니다.
• grid.get(row).charAt(col)는 grid 리스트에서 row 번째 행의 col 번째 열에 있는 문자를 가져옵니다.
• grid.get(row - 1).charAt(col)와 비교하여, 현재 행의 col 번째 문자가 이전 행의 col 번째 문자보다 작은지 확인합니다.
  • 만약 현재 문자가 더 작다면 열이 오름차순이 아니므로, 이 경우 NO를 반환하여 함수가 종료됩니다.
  • 모든 열에서 이러한 검사를 통과하면 YES를 반환합니다.