최근 응시한 코테에서 쓴 맛을 보았습니다. 시간이 부족해서 마지막 문제를 손도 못댄게 원인이었고, 자주 출제되는 문제 분류 위주로 실버 빨리 풀기에 포커스를 맞추려고 합니다.
문제 이름은 맹세였기에, 이 문제는 꼭 푼다고 맹세했습니다. 하지만, 자바로 풀면 메모리 제한이 심하게 적용되는 문제였습니다. 이를 풀이하는 과정이 기억에 남아 기록하려 합니다.
https://www.acmicpc.net/problem/3407
원소표에 있는 문자들로 주어진 문자열을 구성할 수 있는지 판단하는 실버 구현 문제입니다.
String arr[] = {"h", "b", "c", "n", "o", "f", "p", "s", "k", "v", "y", "i", "w", "u",
"ba", "ca", "ga", "la", "na", "pa", "ra", "ta", "db", "nb", "pb", "rb", "sb", "tb", "yb", "ac",
"sc", "tc", "cd", "gd", "md", "nd", "pd", "be", "ce", "fe", "ge", "he", "ne", "re", "se", "te",
"xe", "cf", "hf", "rf", "ag", "hg", "mg", "rg", "sg", "bh", "rh", "th", "bi", "li", "ni", "si",
"ti", "bk", "al", "cl", "fl", "tl", "am", "cm", "fm", "pm", "sm", "tm", "cn", "in", "mn", "rn",
"sn", "zn", "co", "ho", "mo", "no", "po", "np", "ar", "br", "cr", "er", "fr", "ir", "kr", "lr",
"pr", "sr", "zr", "as", "cs", "ds", "es", "hs", "os", "at", "mt", "pt", "au", "cu", "eu", "lu",
"pu", "ru", "lv", "dy"
};
문제를 접하고, 일단 주기율표 하드코딩은 피할 수 없다고 생각했습니다. N개의 문자를 비교하기 위해 어디든 저장해놓고 N번 사용해야 하기 때문입니다. 질문게시판에 마침 배열 선언 코드를 공유한 은인이 계셔서 이를 사용했습니다.
어떤 원소로 문자를 구성했는지는 관심사가 아니고, 문자를 구성할 수 있는지를 묻기에 그래프 탐색 없이 DP로 풀이가 가능했습니다. DP[idx]는 문자열을 idx 범위 까지만 잘랐을 때, 주기율표 원소들로 구성할 수 있는지를 기록한 boolean 배열로 놓았습니다.
주기율표 원소 길이를 al로 놓으면, dp[j] = true인 기준은 다음과 같습니다.
1. j - al >= 0 이다. (이항하면 j >= al)
2. dp[j - al]는 true이다.
3 j - al 에서 j까지 자른 문자열과 현재 주기율 원소가 일치해야 한다.
if (j >= al && dp[j - al] && arr[k].equals(s.substring(j - al, j)))
dp[j] = true;
첫 풀이 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException {
String arr[] = {"h", "b", "c", "n", "o", "f", "p", "s", "k", "v", "y", "i", "w", "u",
"ba", "ca", "ga", "la", "na", "pa", "ra", "ta", "db", "nb", "pb", "rb", "sb", "tb", "yb", "ac",
"sc", "tc", "cd", "gd", "md", "nd", "pd", "be", "ce", "fe", "ge", "he", "ne", "re", "se", "te",
"xe", "cf", "hf", "rf", "ag", "hg", "mg", "rg", "sg", "bh", "rh", "th", "bi", "li", "ni", "si",
"ti", "bk", "al", "cl", "fl", "tl", "am", "cm", "fm", "pm", "sm", "tm", "cn", "in", "mn", "rn",
"sn", "zn", "co", "ho", "mo", "no", "po", "np", "ar", "br", "cr", "er", "fr", "ir", "kr", "lr",
"pr", "sr", "zr", "as", "cs", "ds", "es", "hs", "os", "at", "mt", "pt", "au", "cu", "eu", "lu",
"pu", "ru", "lv", "dy"
};
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
String s = br.readLine().toLowerCase();
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int j = 1; j <= s.length(); j++) {
for (int k = 0; k < arr.length; k++) {
int al = arr[k].length();
if (j >= al && dp[j - al] && arr[k].equals(s.substring(j - al, j)))
dp[j] = true;
}
}
sb.append(dp[s.length()] ? "YES" : "NO").append("\n");
}
System.out.println(sb);
}
}
나름 합리적인 풀이라 생각했지만, 메모리 초과를 받았습니다.
때문에 두가지 메모리 최적화를 했습니다.
1. StringBuilder에 모으지 않고 바로 출력해서 시간복잡도를 늘리고 공간복잡도를 낮춘다.
2. 최대 boolean[5만] dp배열을 byte[3] 배열로 바꿔 동적 갱신한다.
문제에서, 주기율표 원소의 최대 길이는 2입니다.
i번째까지 자른 문자를 구성할 수 있는지 확인하려면,
원소의 길이가 2일 때 i-2번째가 true인지
원소의 길이가 1일 때 i-1번째가 true인지 판단하면 됐습니다.
따라서, 2개의 인덱스 만으로도 비교가 가능했기에 3크기의 배열을 사용했습니다. (2개로도 가능했습니다.)
추가로, boolean을 byte로 바꾼 동작은 유의미하지 않았습니다. boolean은 1bit로 표현 가능하지만, 어차피 CPU 및 자바 컴파일러의 최소 처리 단위가 1byte이기 때문에 boolean 또한 1byte를 사용한다고 합니다.
이후 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main2 {
public static void main(String[] args) throws IOException {
String arr[] = {"h", "b", "c", "n", "o", "f", "p", "s", "k", "v", "y", "i", "w", "u",
"ba", "ca", "ga", "la", "na", "pa", "ra", "ta", "db", "nb", "pb", "rb", "sb", "tb", "yb", "ac",
"sc", "tc", "cd", "gd", "md", "nd", "pd", "be", "ce", "fe", "ge", "he", "ne", "re", "se", "te",
"xe", "cf", "hf", "rf", "ag", "hg", "mg", "rg", "sg", "bh", "rh", "th", "bi", "li", "ni", "si",
"ti", "bk", "al", "cl", "fl", "tl", "am", "cm", "fm", "pm", "sm", "tm", "cn", "in", "mn", "rn",
"sn", "zn", "co", "ho", "mo", "no", "po", "np", "ar", "br", "cr", "er", "fr", "ir", "kr", "lr",
"pr", "sr", "zr", "as", "cs", "ds", "es", "hs", "os", "at", "mt", "pt", "au", "cu", "eu", "lu",
"pu", "ru", "lv", "dy"
};
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
String s = br.readLine().toLowerCase();
// 주기율표 원소의 최대 길이는 2이므로, [idx-2,idx-1, idx] 까지 자른 단어를 구성할 수 있는지 기록
// e.g. : "abcde", idx=3 이라면 => [ab(idx = 1), abc(idx = 2), abcd(idx = 3)]를 만들 수 있는지 기록
byte[] dp = new byte[3];
// 초기에 0번째 단어를 탐색하기 위해, -2번째와 -1번째는 구성할 수 있다고 가정
dp[0] = dp[1] = 1;
for (int j = 0; j < s.length(); j++) {
for (int k = 0; k < arr.length; k++) {
int al = arr[k].length();
// j - al(1 or 2)번째 까지 단어를 잘랐을 때 만들 수 있었고, 현재 주기 원소로 j 까지 자른 단어를 만들 수 있다면 true
if (dp[2 - al] == 1 && j >= al - 1 && arr[k].equals(s.substring(j + 1 - al, j + 1))) {
dp[2] = 1;
break;
}
}
// e.g. : [0, 1, 2]번 째 인덱스 기록용 배열을 [1, 2, 3]번 째 기록용 배열로 갱신
dp[0] = dp[1];
dp[1] = dp[2];
dp[2] = 0;
}
// sb.append(dp[1] == 1 ? "YES" : "NO").append("\n");
System.out.println(dp[1] == 1 ? "YES" : "NO");
}
// System.out.println(sb);
}
}
그럼에도 역시나 메모리 초과를 받았습니다.
이쯤되니 의문이 들었습니다. 하드 코딩한 배열은 1MB도 한참 안쓸 것이고, dp배열 또한 없는 수준의 크기인데도 메모리 초과였습니다. 이후 인터넷 검색을 하니 Java 풀이는 포스팅이 아예 없고 C++이랑 파이썬은 dp[5만]에 그래프탐색까지 하고도 정답 처리를 받았습니다. 여기서 살짝 꺾였지만 이 문제를 풀기로 맹세했기 때문에 계속 고민했습니다.
일단 Java로 푼 사람이 있는지 확인했고, 열명 남짓 있어서 되긴 한다고 생각했습니다. 이후엔 코드에 결함이 없다면 근본적으로 하드코딩한 String 배열을 최적화 하지 않으면 통과할 수 없다고 생각했습니다.
import java.util.Arrays;
public class Main3 {
public static void main(String[] args) {
String[] arr = {
"h", "b", "c", "n", "o", "f", "p", "s", "k", "v", "y", "i", "w", "u",
"ba", "ca", "ga", "la", "na", "pa", "ra", "ta", "db", "nb", "pb", "rb", "sb", "tb", "yb", "ac",
"sc", "tc", "cd", "gd", "md", "nd", "pd", "be", "ce", "fe", "ge", "he", "ne", "re", "se", "te",
"xe", "cf", "hf", "rf", "ag", "hg", "mg", "rg", "sg", "bh", "rh", "th", "bi", "li", "ni", "si",
"ti", "bk", "al", "cl", "fl", "tl", "am", "cm", "fm", "pm", "sm", "tm", "cn", "in", "mn", "rn",
"sn", "zn", "co", "ho", "mo", "no", "po", "np", "ar", "br", "cr", "er", "fr", "ir", "kr", "lr",
"pr", "sr", "zr", "as", "cs", "ds", "es", "hs", "os", "at", "mt", "pt", "au", "cu", "eu", "lu",
"pu", "ru", "lv", "dy"
};
byte[][] byteArr = new byte[arr.length][2];
for (int i = 0; i < arr.length; i++) {
byteArr[i][0] = (byte) arr[i].charAt(0);
if (arr[i].length() == 2) {
byteArr[i][1] = (byte) arr[i].charAt(1);
}
}
for (byte[] bArr : byteArr) {
System.out.println(Arrays.toString(bArr));
}
}
}
배열보다 효율적인 자료구조를 생각하다 학습했던 prefix tree가 생각났지만, 원소의 길이가 짧아 유의미하지 않았고, 문자 자체를 다른 방법으로 표현해야 한다고 생각했습니다.
아이디어는 다음과 같습니다.
알파벳은 총 26개이므로 1~26을 표현할 수 있는 자료형이여야 했습니다. 이는 5bit로 표현 가능하나, 앞서 말했듯이 자바 컴파일러의 최소 처리 단위는 byte라고 하기에 byte로 변환했습니다.
최대 길이 원소인 "zz"까지 다루기 위해서 1byte에 1~26*2를 표시는 방법이 생각났고, 일단 2byte를 통해 표현하고 여전히 메모리 초과면 적용하기로 했습니다.
코드에서 문자열을 toLowerCase() 이후 비교하기에, 1~26으로 바꿔 저장할 필요 없이 그대로 ASCII 값을 저장해도
byte 범위(-128~127)에서 소문자 표현이 가능했습니다. substring() 함수 또한 일단 지우고 인덱스로 비교했습니다.
최종 제출 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException {
byte[][] arr = {
{104, 0}, {98, 0}, {99, 0}, {110, 0}, {111, 0}, {102, 0}, {112, 0}, {115, 0}, {107, 0},
{118, 0}, {121, 0}, {105, 0}, {119, 0}, {117, 0}, {98, 97}, {99, 97}, {103, 97}, {108, 97},
{110, 97}, {112, 97}, {114, 97}, {116, 97}, {100, 98}, {110, 98}, {112, 98}, {114, 98}, {115, 98},
{116, 98}, {121, 98}, {97, 99}, {115, 99}, {116, 99}, {99, 100}, {103, 100}, {109, 100}, {110, 100},
{112, 100}, {98, 101}, {99, 101}, {102, 101}, {103, 101}, {104, 101}, {110, 101}, {114, 101},
{115, 101}, {116, 101}, {120, 101}, {99, 102}, {104, 102}, {114, 102}, {97, 103}, {104, 103},
{109, 103}, {114, 103}, {115, 103}, {98, 104}, {114, 104}, {116, 104}, {98, 105}, {108, 105},
{110, 105}, {115, 105}, {116, 105}, {98, 107}, {97, 108}, {99, 108}, {102, 108}, {116, 108},
{97, 109}, {99, 109}, {102, 109}, {112, 109}, {115, 109}, {116, 109}, {99, 110}, {105, 110},
{109, 110}, {114, 110}, {115, 110}, {122, 110}, {99, 111}, {104, 111}, {109, 111}, {110, 111},
{112, 111}, {110, 112}, {97, 114}, {98, 114}, {99, 114}, {101, 114}, {102, 114}, {105, 114},
{107, 114}, {108, 114}, {112, 114}, {115, 114}, {122, 114}, {97, 115}, {99, 115}, {100, 115},
{101, 115}, {104, 115}, {111, 115}, {97, 116}, {109, 116}, {112, 116}, {97, 117}, {99, 117},
{101, 117}, {108, 117}, {112, 117}, {114, 117}, {108, 118}, {100, 121}
};
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
String s = br.readLine().toLowerCase();
byte[] dp = new byte[3];
dp[0] = dp[1] = 1;
for (int j = 0; j < s.length(); j++) {
for (int k = 0; k < arr.length; k++) {
int al = arr[k][1] == 0 ? 1 : 2;
if (dp[2 - al] == 1 && j >= al - 1) {
if ((al == 1 && arr[k][0] == s.charAt(j) || al == 2 && arr[k][0] == s.charAt(j - 1) && arr[k][1] == s.charAt(j))
{
dp[2] = 1;
break;
}
}
}
dp[0] = dp[1];
dp[1] = dp[2];
dp[2] = 0;
}
System.out.println(dp[1] == 1 ? "YES" : "NO");
}
}
}
결론적으로, 자바로 푼 사람중 제일 메모리를 적게썼습니다. (뿌듯)
문제에서 메모리 제한은 128M고 자바는 x2 정도 해준다고 기억합니다. 수정 전의 코드도 1MB를 안쓴다고 생각하므로, 힙 영역이 터져서 오답을 받았다고 여겼습니다. 그럼에도 Java에 한해 수정 되어야할 억까 문제임은 변함이 없고, Java로 정답을 받은 사람들 대부분도 메모리 초과를 받고 시작이었습니다.
본 취지였던 실버 빨리 풀기랑은 멀어졌지만 값진 경험이었습니다.
'미니멀 개발일기' 카테고리의 다른 글
| local port와 rest-assured port 동기화 (0) | 2025.01.05 |
|---|---|
| ParameterizedTest 적용해보기 (0) | 2024.12.16 |
| Test Data Builder Class를 적용하기 전의 고찰 (0) | 2024.12.10 |
| Junit5 디펜던시 추가에 4시간을 쓴 경험 (0) | 2024.12.04 |
| [VM/Ubuntn] 양방향 클립보드 공유 (0) | 2024.07.15 |