백준 23716 자바 - Transform the String (BOJ 23716 JAVA)

문제 : boj23716

 

 

  로직 자체는 별게 없다. S의 모든 문자열에 대해 각각 F의 각 문자열을 순회하며 가장 차이가 작은 문자를 고르면 된다. O(|S||F|) 다만 자바 한정으로 난이도가 급상승하는데, String으로 받는 순간 메모리 초과가 된다 ㅋㅋㅋㅋ (String은 char 배열형태이고, char은 2byte가 필요하다. byte 자료형은 1byte이다. -128~127까지 표현 가능하지만 어쨌든 소문자 표현은 가능하다.)

C++이나 파이썬의 겨우엔 그냥 받아진다.

 

  자바는 그래서 어떻게 해야 하냐면, character 배열인 String을 쓰면 안되고 모든 문자를 byte단위로 처리해야 한다. 따라서 byte 단위로 한 문자씩 입력받아 처리해야 한다. 아마 차후 자바의 경우 추가 메모리가 주어질 것 같으므로 자바로 풀꺼면 나중에 푸는걸 추천드림.

 

 

코드 : github

import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;

public class Main extends FastInput {
    private static final int AZ_GAP = 'z'-'a'+1;
    private byte[][] arr;

    private void init() {
        arr = new byte[AZ_GAP][AZ_GAP];
        for (int i = 0; i < AZ_GAP; i++) {
            for (int j = 0; j < AZ_GAP; j++) {
                if (i == j) continue;
                int l = i<j?i:j;
                int h = i>j?i:j;
                arr[i][j] = (byte) Math.min(h-l, AZ_GAP-h+l);
            }
        }
    }

    private void solution() throws Exception {
        init();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = nextInt();
        for (int tcNum = 1; tcNum <= tc; tcNum++) {
            System.gc();
            byte[] s = nextLine(true);
            int sLen = FastInput.lastLineLen;
            byte[] f = nextLine(false);
            int fLen = FastInput.lastLineLen;

            int sum = 0;
            for (int i = 0; i < sLen; i++) {
                int cur = s[i]-'a';
                int min = AZ_GAP;
                for (int j = 0; j < fLen; j++) {
                    int gap = arr[cur][f[j]-'a'];
                    if (min > gap)
                        min = gap;
                }
                sum += min;
            }
            bw.write(String.format("Case #%d: %d\n", tcNum, sum));
            bw.flush();
        }
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;
    protected static int lastLineLen = 0;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static byte[] nextLine(boolean isS) throws IOException {
        byte[] buf = new byte[isS?100001 : 27];
        int cnt = 0, c;
        while ((c = read()) != -1) {
            if (c == '\n') {
                if (cnt != 0) break;
                continue;
            }
            buf[cnt++] = (byte)c;
        }
        lastLineLen = cnt;
        return buf;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}