LeetCode 1768. Merge Strings Alternately 풀이 복기
문제 이해
이번에 푼 문제는 Merge Strings Alternately이다.
문제 자체는 어렵지 않았다.
두 문자열이 주어지고, 첫 번째 문자열의 문자부터 시작해서 두 문자열의 문자를 번갈아가며 합치면 된다.
예를 들어 다음과 같은 입력이 있다고 하자.
word1 = "abc";
word2 = "pqr";결과는 다음과 같다.
a p b q c r그래서 최종 결과는 다음과 같다.
"apbqcr"만약 두 문자열의 길이가 다르면, 짧은 문자열이 끝난 뒤에 긴 문자열의 남은 문자를 그대로 붙이면 된다.
예를 들어 다음과 같은 입력이 있다.
word1 = "ab";
word2 = "pqrs";이면 a, p, b, q까지 번갈아 붙이고, word2에 남은 r, s를 뒤에 붙이면 된다.
결과는 다음과 같다.
"apbqrs"알고리즘 분류
이 문제는 문자열 처리 문제이다.
두 문자열을 같은 인덱스 기준으로 번갈아 확인하면서 새로운 문자열을 만들어야 한다.
따라서 배열이나 문자열을 순서대로 순회하는 기본적인 문제에 가깝다.
세부적으로는 두 문자열을 각각 가리키는 인덱스를 사용한다는 점에서 투 포인터의 기초 형태로도 볼 수 있다.
다만 복잡한 포인터 이동 조건이 있는 문제는 아니고, 단순히 같은 인덱스 i를 기준으로 word1, word2를 차례대로 확인하는 문제이다.
사용한 자료구조는 결과 문자열을 만들기 위한 StringBuilder이다.
문제 유형: 문자열 처리
세부 주제: 문자열 병합, 인덱스 순회, 투 포인터 기초
난이도: Easy
자료구조: String, StringBuilder처음 풀이
처음에는 두 문자열 중 더 긴 길이를 구한 다음, 그 길이만큼 반복문을 돌렸다.
class Solution {
public String mergeAlternately(String word1, String word2) {
String answer = "";
int a = word1.length();
int b = word2.length();
int c = a > b ? a : b;
for (int i = 0; i < c; i++) {
if (a > i) {
answer += word1.charAt(i);
}
if (b > i) {
answer += word2.charAt(i);
}
}
return answer;
}
}처음 생각은 단순했다.
두 문자열을 같은 인덱스 기준으로 하나씩 확인하면서, 해당 위치에 문자가 있으면 결과 문자열에 붙이면 된다고 생각했다.
그래서 word1.length()와 word2.length()를 각각 구하고, 둘 중 더 긴 길이만큼 반복문을 돌렸다.
int a = word1.length();
int b = word2.length();
int c = a > b ? a : b;그리고 반복문 안에서는 현재 인덱스 i가 각 문자열의 길이보다 작은지 확인했다.
if (a > i) {
answer += word1.charAt(i);
}
if (b > i) {
answer += word2.charAt(i);
}이렇게 하면 한쪽 문자열이 먼저 끝나도 에러가 나지 않고, 남아 있는 문자열의 문자만 계속 붙일 수 있다.
예를 들어 word1 = "ab", word2 = "pqrs"라면 흐름은 이렇게 된다.
i = 0
word1[0] = a 추가
word2[0] = p 추가
i = 1
word1[1] = b 추가
word2[1] = q 추가
i = 2
word1은 더 이상 문자가 없음
word2[2] = r 추가
i = 3
word1은 더 이상 문자가 없음
word2[3] = s 추가결과적으로 "apbqrs"가 만들어진다.
풀이 로직 자체는 맞았고, 제출도 가능했다.
다만 다른 풀이를 보면서 Java에서 문자열을 반복해서 더할 때는 String +=보다 StringBuilder를 사용하는 게 더 좋다는 것을 다시 정리하게 됐다.
String +=가 아쉬운 이유
내 처음 풀이에서는 결과 문자열을 만들 때 이렇게 작성했다.
String answer = "";
answer += word1.charAt(i);
answer += word2.charAt(i);처음 볼 때는 그냥 answer에 문자를 하나씩 붙이는 것처럼 보인다.
하지만 Java의 String은 불변 객체라서, 한 번 만들어진 문자열의 내용은 바뀌지 않는다.
그래서 +=로 문자열을 붙인다고 해서 기존 문자열 뒤에 바로 문자가 붙는 게 아니다.
실제로는 새로운 문자열이 계속 만들어진다.
예를 들어 이런 코드가 있다고 하자.
String answer = "";
answer += "a";
answer += "p";
answer += "b";
answer += "q";내가 생각하기에는 answer 하나에 계속 문자가 붙는 느낌이지만, 실제로는 이런 식으로 동작한다.
처음 answer = ""
answer += "a"
→ 새로운 문자열 "a" 생성
answer += "p"
→ 새로운 문자열 "ap" 생성
answer += "b"
→ 새로운 문자열 "apb" 생성
answer += "q"
→ 새로운 문자열 "apbq" 생성즉, 중간에 "a", "ap", "apb" 같은 문자열들이 계속 만들어진다.
물론 더 이상 사용하지 않는 문자열은 나중에 GC가 정리하겠지만, 반복문 안에서 이런 식으로 계속 문자열을 만들면 불필요한 객체 생성이 많아질 수 있다.
이번 문제는 문자열 길이가 최대 100이라서 사실 String +=로 풀어도 큰 문제는 없다.
하지만 Java에서 반복문으로 문자열을 조립해야 하는 상황이라면 StringBuilder를 쓰는 게 더 좋은 습관이라고 느꼈다.
StringBuilder로 개선한 풀이
그래서 StringBuilder를 사용하면 다음과 같이 작성할 수 있다.
class Solution {
public String mergeAlternately(String word1, String word2) {
StringBuilder answer = new StringBuilder();
int a = word1.length();
int b = word2.length();
int c = Math.max(a, b);
for (int i = 0; i < c; i++) {
if (i < a) {
answer.append(word1.charAt(i));
}
if (i < b) {
answer.append(word2.charAt(i));
}
}
return answer.toString();
}
}기존 풀이와 전체 흐름은 거의 같다.
달라진 부분은 결과 문자열을 만드는 방식이다.
기존에는 String을 사용했다.
String answer = "";
answer += word1.charAt(i);개선 풀이에서는 StringBuilder를 사용했다.
StringBuilder answer = new StringBuilder();
answer.append(word1.charAt(i));StringBuilder는 String처럼 매번 새로운 문자열을 만드는 방식이 아니라, 내부에 문자를 계속 추가하는 방식이다.
그래서 반복문 안에서 문자열을 조립할 때 더 적합하다.
마지막에는 StringBuilder를 그대로 반환할 수 없기 때문에 toString()으로 문자열로 변환해서 반환한다.
return answer.toString();그리고 두 문자열 중 더 긴 길이를 구하는 부분도 삼항 연산자 대신 Math.max()를 사용했다.
int c = Math.max(a, b);기존 코드의 아래 코드와 같은 의미다.
int c = a > b ? a : b;다만 Math.max()가 더 큰 값을 구한다는 의도가 더 잘 보이는 것 같다.
시간복잡도
이 문제는 결국 두 문자열의 문자를 한 번씩 확인한다.
문자열 word1의 길이를 n, word2의 길이를 m이라고 하면 시간복잡도는 다음과 같다.
O(n + m)반복문은 두 문자열 중 더 긴 길이만큼 돌지만, 실제로 결과 문자열에 추가되는 문자의 총 개수는 n + m개이다.
결국 두 문자열의 모든 문자를 한 번씩 처리하므로 O(n + m)으로 볼 수 있다.
공간복잡도
결과 문자열을 저장하기 위해 StringBuilder를 사용한다.
최종 결과 문자열의 길이는 word1.length() + word2.length()이다.
따라서 공간복잡도는 다음과 같다.
O(n + m)입력 문자열을 제외하고, 결과를 만들기 위한 추가 공간이 필요하기 때문이다.
정리
이번 문제는 알고리즘 자체보다는 Java에서 문자열을 다루는 방식에 대해 다시 생각해볼 수 있는 문제였다.
처음 풀이처럼 String +=를 사용해도 문제는 풀린다.
특히 입력 크기가 작으면 성능 차이가 크게 느껴지지 않을 수도 있다.
하지만 Java의 String은 불변 객체이기 때문에 반복문 안에서 +=를 사용하면 새로운 문자열 객체가 계속 생성될 수 있다.
그래서 반복적으로 문자열을 만들어야 하는 경우에는 StringBuilder를 사용하는 것이 더 적절하다.
이번 문제를 풀면서 기억할 점은 다음과 같다.
1. 문자열을 번갈아 합칠 때는 같은 인덱스를 기준으로 접근하면 된다.
2. 한쪽 문자열이 먼저 끝날 수 있으므로 인덱스 범위 체크가 필요하다.
3. Java의 String은 불변 객체다.
4. 반복문에서 문자열을 계속 붙일 때는 StringBuilder를 사용하는 것이 좋다.
5. StringBuilder로 만든 결과는 마지막에 toString()으로 변환해서 반환한다.처음에는 단순히 문제를 맞히는 데 집중했는데, 풀이를 다시 보면서 String +=와 StringBuilder의 차이를 정리할 수 있었다.
앞으로 반복문 안에서 문자열을 조립해야 하는 문제가 나오면 StringBuilder를 먼저 떠올려야겠다.
