[알고리즘] 제곱근을 통한 문자열 자르기 - encryption

문제

한글로 쉽게 정리

이 문제는 제곱근에 관련한 문제, 문자열 길이를 가지고 사각형 메트릭스에 최대한 가로와 세로의 차이가 안나도록 배열을 생성하는 문제. 알고리즘의 핵심은 가로와 세로의 차이가 최대한 나지않도록 가로, 세로를 구해야한다.

원문

An English text needs to be encrypted using the following encryption scheme. First, the spaces are removed from the text. Let L be the length of this text. Then, characters are written into a grid, whose rows and columns have the following constraints:

[√L] <= row <= column <= [√L] , where [x] is the floor function and [x] is ceil function

Example

s = if man was meant to stay on the ground god would have given us roots

After removing spaces, the string is 54 characters long. √54 is between 7 and 8, so it is written in the form of a grid with 7 rows and 8 columns.

ifmanwas  
meanttos          
tayonthe  
groundgo  
dwouldha  
vegivenu  
sroots

• Ensure that rows x columns >= L
• If multiple grids satisfy the above conditions, choose the one with the minimum area, i.e. rows x columns.

The encoded message is obtained by displaying the characters of each column, with a space between column texts. The encoded message for the grid above is:

imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau

Create a function to encode a message.

Function Description

Complete the encryption function in the editor below.

encryption has the following parameter(s):

• string s: a string to encrypt

Returns

• string: the encrypted string

Input Format

One line of text, the string s

Constraints

• 1 <= length of s <= 81
• s contains characters in the range ascii[a-z] and space, ascii(32).

Sample Input 0

haveaniceday

Sample Output 0

hae and via ecy

Explanation 0

L = 12, √12 is between 3 and 4.
Rewritten with 3 rows and 4 columns:

have
anic
eday

Sample Input 1

feedthedog    

Sample Output 1

fto ehg ee dd

Explanation 1

L = 10, √10 is between 3 and 4.
Rewritten with 3 rows and 4 columns:

feed
thed
og

Sample Input 2

chillout

Sample Output 2

clu hlt io

Explanation 2

L = 8, √8 is between 2 and 3.
Rewritten with 3 columns and 3 rows (2 * 3 = 6 < 8 so we have to use 3 X 3.)

해결책

시작

문제는 어렵지 않다고 생각해서 가볍게 시작하였고 해커랭크에서도 대다수가 푼 문제라고 나와서 작성중 놓친 케이스는 81, 64 같은 딱 떨어지는 케이스를 간과한 것 그 케이스를 제외하곤 쉬운 문제이고 지금의 이 솔루션 보다 더 좋은 코드가 당연히 작성 가능하지만 정리를 얼른 마쳐야 하는 마음에 이만 이렇게 작성

soluction

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'encryption' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts STRING s as parameter.
     */

    public static String encryption(String s) {
    
        int inputSize = s.length();
        int rowCount = (int) Math.sqrt(inputSize);
        int cellCount = rowCount + 1;
        if(rowCount * rowCount == inputSize) cellCount = rowCount;
        if(inputSize > rowCount * cellCount) rowCount++;


        char[][] encryptionArray = new char[rowCount][cellCount];
        char[] inputArray = s.toCharArray();

        for( int i = 0 ; i < rowCount ; i++ ) {
            for( int j = 0 ; j < cellCount ; j++ ) {
                encryptionArray[i][j] = '0';
            }
        }
        for( int i = 0 ; i < rowCount ; i++ ) {
            for( int j = 0 ; j < cellCount ; j++ ) {
                int checkIndex = i * cellCount + j;
                if(inputSize > checkIndex) {
                    encryptionArray[i][j] = inputArray[checkIndex];        
                }
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        for( int i = 0 ; i < cellCount ; i++ ) {
            for( int j = 0 ; j < rowCount ; j++ ) {
                char temp = encryptionArray[j][i];
                if(temp != '0') {
                    stringBuilder.append(temp);
                }
            }
            
            if(i + 1 != cellCount) {
                stringBuilder.append(' ');    
            }

        }

        return stringBuilder.toString();
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String s = bufferedReader.readLine();

        String result = Result.encryption(s);

        bufferedWriter.write(result);
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}