자바와 관련된 다양한 문제 해결 과정이 있었다.
Programmers에서 진행했고 대부분 해결하기 어려운 문제는 아니었지만 그래도 몇가지 알게된 점이 있어서 기록이 필요할 것 같다.
1. 숫자 짝궁
문제 설명
두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.
제한사항
3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
X, Y는 0으로 시작하지 않습니다.
X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.
입출력 예
| X | Y | result |
|---|---|---|
| "100" | "2345" | "-1" |
| "100" | "203045" | "0" |
| "100" | "123450" | "10" |
| "12321" | "42531" | "321" |
| "5525" | "1255" | "552" |
문제 설명부터 어질어질한데 사실 뜯고보면 별거 없다. 두 문자열에 겹친 숫자를 모아서 결과를 출력해야한다. 가장 큰 정수로 만들라는 의미도 내림차순 하라는 건데 이걸 한 글자씩 내림차순 하는 것은 지극히 비효율 적이다. 어차피 공통된 숫자를 찾아서 하나씩 쌓아야 한다면 9부터 찾아서 결과값에 붙이면 내림차순 할 필요가 없을것이다.
처음 접근한 방법은 이렇다.
class Solution {
public String solution(String X, String Y) {
String answer = "";
String[] xcs = X.split("");
String[] ycs = Y.split("");
int[] xcnt = new int[10];
int[] ycnt = new int[10];
for (String s : xcs) {
xcnt[Integer.parseInt(s)]++;
}
for (String s : ycs) {
ycnt[Integer.parseInt(s)]++;
}
for (int i = 9; i >= 0; i--) {
String num = String.valueOf(i);
for (int j = 0; j < ((xcnt[i] > ycnt[i]) ? ycnt[i] : xcnt[i]); j++) {
answer += num;
}
}
return (answer.length() > 0) ? ((answer.charAt(0) == 48) ? "0" : answer) : "-1";
}
}코드를 이렇게 짰는데 각 문자열 x와 y를 한 글자씩 보고 배열에 값을 증가시킨다. 배열[n]은 n의 개수...와 같은 방법이다. 그래서 마지막에는 배열의 길이가 짧은 쪽을 기준으로 결과값 문자열에 더해서 넣는 방식이다.
마지막 return에서 결과값의 길이가 0이면 -1을 반환해야한다.
그리고 맨 앞자리가 0이면 이는 결과 정수값이 0이란 의미이기 때문에 "0"을 반환한다.
이 과정이 다 아니면 문자열을 넘기게 된다.
결과는 시간 초과... 여러 부분에서 코드를 고치고 어디가 문제인지 찾아봤는데 도저히 찾을 수가 없었다. 입력 문자열이 엄청 길기 때문에 나타나는 문제점이 어디일까 찾아봤더니...
answer += num;여기가 문제였다... 이유는 다음과 같다.
String은 불변한다!
String은 참조 변수에 해당한다. 즉 실제 값은 힙에 있고 String 변수는 참조를 위한 주소값에 해당한다. String을 더하는 변수는 단순한 값 변경이 아니라 두 String의 길이를 합친 새로운 공간을 만들게 된다. 이런 String은 "불변"한다고 표현한다.
▲ 다음과 같은 선언은 Heap 영역에 값을 저장하고 주소값을 만들게 된다.
▲ 이후에 값을 수정하는것처럼 보이지만 사실 새로운 공간을 만들고 주소값을 변경한다.
이러한 점 때문에 String 덧셈은 두 문자열의 길이에 합과 동일한 새로운 문자열을 만드는 행위와 같다. 이러한 문제점은 내가 만든 코드처럼 많이 반복되면 비효율은 극적으로 올라가는데
기존 배열을 끊임없이 다시 선언하게 된다는 것이다. 10의 공간을 차지하는 String을 300번 더하도록 하면 총 생산해야 하는 공간은 약 45만 정도 된다. 이를 끊임없이 지우고 새로 써야한다는 것은 좋지 않다.
그래서 등장한 StringBuilder
StringBuilder는 따로 라이브러리를 추가하지 않아도 쓸 수 있다.
StringBuilder stringBuilder = new StringBuilder();
다음과 같은 선언으로 StringBuilder를 쓸 수 있다.
sb.append("문자열");다음과 같은 append()를 통해 값을 추가할 수 있다.
sb.toString();toString()을 사용하면 append를 했던 모든 값들이 하나의 문자열로 더해진다.
사용법을 종합하면 다음과 같다.
-
문자열 추가 및 수정:
append(String str): 문자열을 추가합니다.insert(int offset, String str): 특정 위치에 문자열을 삽입합니다.replace(int start, int end, String str): 지정한 범위 내의 문자열을 대체합니다.delete(int start, int end): 지정한 범위 내의 문자열을 삭제합니다.deleteCharAt(int index): 지정한 위치의 문자를 삭제합니다.setCharAt(int index, char ch): 지정한 위치의 문자를 대체합니다.
-
문자열 정보:
length(): 현재 문자열의 길이를 반환합니다.capacity(): 현재 버퍼의 용량을 반환합니다.charAt(int index): 지정한 위치의 문자를 반환합니다.toString():StringBuilder객체의 문자열 표현을 반환합니다.
수정된 코드
class Solution {
public String solution(String X, String Y) {
StringBuilder sb = new StringBuilder();
String answer = "";
String[] xcs = X.split("");
String[] ycs = Y.split("");
int[] xcnt = new int[10];
int[] ycnt = new int[10];
for (String s : xcs) {
xcnt[Integer.parseInt(s)]++;
}
for (String s : ycs) {
ycnt[Integer.parseInt(s)]++;
}
for (int i = 9; i >= 0; i--) {
String num = String.valueOf(i);
for (int j = 0; j < ((xcnt[i] > ycnt[i]) ? ycnt[i] : xcnt[i]); j++) {
sb.append(num);
}
}
answer = sb.toString();
return (answer.length() > 0) ? ((answer.charAt(0) == 48) ? "0" : answer) : "-1";
}
}완성된 코드는 StringBuilder를 사용해서 시간 제한을 넘기지 않았다!
여전한 의문점
그렇다면 Collections 클래스에 add, LinkedList와 같은 구성들은 어떻게 가변적인 크기를 활용할 수 있을까? 아마 내부 구성 요소를 뜯어볼 필요가 있을 것 같다...
