[LC150] Array/String - 1

이번주는 리트코드 Top Interview 150 문제 리스트에서 Array/String 문제 5개를 풀었다.

 

✅ Merge Sorted Array

난이도: ★★

이미 배열이 정렬되어 있기 때문에 Two pointer 방법을 사용해서 풀 수 있다. 특이점은 nums1 배열에 정렬된 요소를 넣어야 해서 배열 맨 끝에 있는 요소부터 비교해서 채워넣으면 된다. Merge sort를 구현할 수 있으면 어렵지 않게 풀 수 있는 문제.

 

✅ Remove Element

난이도: ★★★★★

이 문제는 진짜 easy 레벨인데 쉽게 생각을 못해서 아래처럼 풀려고 했다. start, end로 start는 조건에 맞는 요소가 들어갈 위치를 가르키고 end는 조건에 맞는 요소를 찾는 방식이였는데 또 내가 생각한대로 코드를 구현하는 것에 막혀서 (조건 체크하는 부분이 너무 많이 들어감) 혼자 구현은 못하고 결국 솔루션을 찾아봄. 

내가 원래 생각한 로직

 

예를 들어, nums = [3, 2, 2, 3], val = 3이 input으로 주어질 경우 start와 end의 위치는 각각 시작과 끝을 가르킨다.

맨 처음 start와 end의 위치

 

start와 end의 이동방향

 

while(start <= end) 조건은 start가 end보다 작거나 같을 경우 계속 반복된다. 0번째 위치에서 시작한 start가 end보다 더 커질 경우 즉 start와 end가 배열의 모든 요소를 탐색을 완료했을 때 while문이 종료된다.

 

start 포인터가 가르치는 요소가 주어진 val과 같지 않으면 계속 한칸씩 오른쪽으로 이동한다. 결과적으로 while문이 종료됐을 때 start는 val과 같은 요소를 가르키고 있고 이 start의 위치는 val과 다른, remove 할 필요가 없는 요소가 들어갈 자리이다.

 

end 포인터는 한칸씩 왼쪽으로 이동하면서 val과 같지 않은 요소가 있는 위치에서 멈춘다. 

 

while문이 다 끝났을 때 start와 end의 위치는 다음과 같다. 

 

start는 remove 해야될 요소를 가리키고 있고 end는 필요한 요소의 위치를 가르키고 있기 때문에 값을 swap 해준다. 

 

여기까지 실행되면 val과 같은 값인 3과 val이 아닌 2의 값의 위치가 서로 바뀌고 start와 end도 한칸식 이동해서 서로 같은 곳을 가리킨다. while문의 종료 조건이 start <= end이기 때문에 start == end일 경우에도 동작한다. 

 

여기서 start 조건의 while문이 실행되고 나면 start <= end 조건이 false가 됨으로 end의 while문은 실행되지 않고 start와 end의 위치는 다음과 같다. 

start는 remove 해야 될 값, end는 remove 하지 않아야 할 값을 가르키고 있기 때문에 이 두 값을 swap 해주었지만 만약 start가 end보다 같으면 불필요한 swap을 하지 않아도 되고, start가 end보다 크다면 이미 초록색 부분 nums[0...start) 까지는 val 값이 제거된 요소들만 들어가 있기 때문에 swap을 하지 않아야 한다. 

start index-1까지는 val값이 들어있지 않다.

 

그래서 결과적으로는 start 값을 리턴해주면 이렇게 풀 수도 있다. 하지만 while문 안의 각각의 while문도 break조건 및 index범위 체크하는 로직이 필요하고 swap도 start < end일때만 가능하도록 조건을 넣어줘야 했는데 이러한 조건들을 작성하는 것이 어려웠다. 

 

 

 

이건 내가 작성한 코드보다 간결한데 start는 앞에서 end는 뒤에서부터 확인하는데 start의 값이 val일 경우 이 값은 remove되어야 하니까 뒤에서 값을 넣어주고 한칸씩 앞으로 이동한다. 그런다음 start값이 val이 아니면 한칸씩 옆으로 이동한다. 

 

이 문제는 while문보다 for문으로 구현된 코드가 훨씬 직관적이다. 

 

for문으로 작성하면 i가 모든 원소를 순회하면 값을 확인하고 index변수로(val이 아닌 값이 들어갈 위치를 기록) val이 아닌 값을 넣어준다. 이 유튜브를 보면 배열을 그림으로 보여줘서 코드가 어떻게 동작하는지 이해하기 쉽다. 

 

 

 

✅ Remove Duplicates from Sorted Array

난이도: ★★

removeElement 문제를 잘 풀었으면 쉽게 풀 수 있다. 

 

✅ Remove Duplicates from Sorted Array 2

난이도: ★★

위 문제를 문제를 잘 풀었으면 쉽게 풀 수 있다. count변수를 활용할 수 있다는데 나는 그냥 이전 요소를 비교해서 품.

 

✅ Majority Element

난이도: ★★★★★

이 문제는 hashmap을 사용해서 풀면 정말 간단히 풀 수 있는 문제이지만 space complexity를 O(1)로 푸는 건 또 다른문제라 저번에도 O(1)으로 푸는 방법을 봤는데 다시 풀면 생각이 안난다....

majority element를 space O(1)으로 푸는 방법

 

 

 

 

 

 

 

 

 

 

 

 

 

va