📌 문제 : Leet Code 1768
📌 문제 탐색하기
word1, word2 : 입력되는 2개의 단어 ()
문제 풀이
2개의 단어 word1, word2가 주어졌을 때, word1부터 한 글자씩 번갈아 넣어 만든 문자열을 출력하는 문제이다.
이 때, 더 긴 단어일 경우 사이에 들어갈 문자가 없으므로 그냥 바로 넣는다.
word1부터 시작하므로 결과 리스트에 word1은 짝수 번째, word2는 홀수 번째에 들어갈 것이다.
이를 활용해 만들어질 문자열의 길이부터 구하고 그 길이만큼 결과 리스트를 정의해서 그 안에 하나씩 값을 채워 넣는 방식으로 구현한다.
가능한 시간복잡도
for 루프 →
join →
최종 시간복잡도
최악의 경우 이므로 충분히 동작할 수 있다.
알고리즘 선택
- 반복문으로 단어 한글자씩 넣기
📌 코드 설계하기
- 만들 수 있는 문자열의 최대 크기 정의
- 만들 수 있는 문자열 저장할 리스트 정의
- 각 단어의 현재 인덱스 정의
- 값 넣기
- 리스트를 한 단어로 합치기
📌 시도 회차 수정 사항
1회차
- 각 단어를 리스트화하고 길이가 더 긴쪽 리스트에 아무것도 남은 게 없을 때까지
pop해서 교차로 한 글자씩 새로운 리스트에 넣으려고 햇는데Memory Limit Exceeded가 발생했다. - 짧은 단어가 먼저 다 pop되면 리스트에 공백을 넣도록 했는데 그 부분에서 무한으로 도는 문제가 발생한 것 같다.
📌 정답 코드
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
# 만들 수 있는 문자열의 최대 크기 정의
max_length = max(len(word1), len(word2)) * 2
# 만들 수 있는 문자열 저장할 리스트 정의
words = [''] * max_length
# 각 단어의 현재 인덱스 정의
i1, i2 = 0, 0
# 값 넣기
for i in range(max_length):
# 짝수번째엔 word1
if i % 2 == 0:
# 단어 길이가 최대 길이보다 짧아서 제한
if i1 < len(word1):
words[i] = word1[i1]
# 인덱스 증가
i1 += 1
# 홀수번째엔 word2
else:
if i2 < len(word2):
words[i] = word2[i2]
# 인덱스 증가
i2 += 1
# 리스트를 한 단어로 합치기
words = ''.join(words)
return words
- 결과
👍 다른 풀이
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
# 결과 저장 리스트
res=[]
# 2개의 포인터를 각 단어의 인덱스로 초기화
p1,p2=0,0
# 두 포인터 중 하나라도 끝까지 도달할 때까지 반복
while p1<len(word1) or p2<len(word2):
# word1에 문자 추가 조건
if p1<len(word1):
res.append(word1[p1])
p1+=1
# word2에 문자 추가 조건
if p2<len(word2):
res.append(word2[p2])
p2+=1
return "".join(res)
- Runtime : 14ms
- 투 포인터를 활용해 문자열을 한 번씩만 순회해 직접 병합하여 최소한의 메모리와 시간 사용으로 효율적
- 내 풀이는 고정 크기 리스트에 인덱스를 대입해 푼 방법인데 미리 빈 값을 많이 채워야 해서 메모리 낭비가 발생할 수 있고 인덱스로 바로 접근하는데에 실수가 있을 수도 있어서 일반적으로 동적 리스트를 더 널리 사용한다고 한다.
✏️ 회고
- 아이디어는 바로 떠올랐는데 구현이 어려운 문제였다. 처음엔 while문으로 긴 단어가 다 없어질 때까지 반복하면 되겠다라고만 생각해서 구현했더니 메모리 초과가 났다. 두번째엔 두 단어가 번갈아 들어간다는 것은 인덱스가 짝수인지 홀수인지에 따라 넣으면 되겠다는 생각이 들어서 해결할 수 있었다. 단, 각 리스트의 인덱스를 다룰 때 투 포인터를 활용할 수 있다는 것은 떠올리지 못했다. 알고리즘의 중요성을 매번 느끼게 된다.
