알고리즘 자료구조 / 다중 포인터 패턴

📌 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝, 양쪽 지점을 향해 이동시키는 것

 

 

sumZero

 

 

 

📂 다중 포인터 패턴 sumZero O(n)

---

더해서 0이 되는 두 요소를 가지는 배열을 리턴한다.
인풋 배열은 오름차순이고 정렬 되어 있음.

sumZero([-3,-2,-1,0,1,2,3]) // [-3, 3]
sumZero([-2,-1,0,1,3]) //undefined
sumZero([1,2,3]) //undefined

 

 

📎  풀이 과정 축약

왼쪽 끝과 오른쪽 끝에서 가운데로 이동하는 방식.

정렬이 되어 있으니 양쪽 끝에서부터 숫자를 더해서 0인 두 요소를 찾는다.

 

 

📌  자세한 풀이

left = 0, right = arr.length-1
arr[left], arr[right]는 arr의 양쪽 끝 숫자이다.
arr[left] + arr[right] 이 0이라면 두 요소를 리턴한다.
arr[left] + arr[right] 이 양수라면 right-1,
arr[left] + arr[right] 이 음수라면 left + 1 해준다.

---

더해서 양수가 나오면 오른쪽 끝 숫자를 arr[arr.length-1-1] 로 바꾸고 또 더한다.
또 양수가 나오면 다시 arr[arr.length-1-1-1],
음수가 나오면 왼쪽 끝 숫자를 오른쪽으로 하나 옮김(큰 숫자로 옮김) arr[0+1]
이렇게 두 요소를 더한 숫자가 음수이면 왼쪽 숫자를 한칸 오른쪽으로 바꾸고,
양수이면 오른쪽 숫자를 한칸 왼쪽으로 바꿔가며 더해줌

 

 

📎  레퍼런스 코드

function sumZero(arr){
let left = 0;
let right = arr.length -1;
while(left < right){
	let sum = arr[left] + arr[right];
    if(sum === 0) {
    	return [arr[left], arr[right]];
      } else if (sum > 0) {
      		right--;
      } else {
      		left++;
      }
  }
}

 

 

 

 

 

 

📂 연습문제 countUniqueValues 

---

입력된 배열의 숫자 중 고유한 숫자의 개수를 구하라

 

countUniqueValues([1,2, 2, 2, 3, 3, 4, 4, 5, 5]) // 5

countUniqueValues([0, 0, 5]) //2

countUniqueValues([ ]) // 0

 

 

 

📌 내가 쓴 코드

   i를 기준으로 앞에서부터 정렬. j가 배열의 마지막에 닿을 때, i+1은 고유 값의 개수
  
   arr[0], arr[1] 에서 i, j 포인터가 시작된다.
   arr의 길이 만큼 j ++ 하며 반복한다.
   arr[i] !== arr[j]일 때 i++, arr[i]= arr[j]
   arr[i] === arr[j] 이면 그냥 가던 길 감 (for)
   반복문 끝나면 고유 숫자만 정렬되어 있고, 마지막 정렬 숫자에 i 포인터가 있다.
   i+1은 고유한 숫자의 개수(i는 0부터 시작되니까 개수를 구하려면 +1하기)
   
   + 빈 배열이 전달 되어도 i+1로 1이 리턴되기 때문에 시작할 때 빈 배열인 경우에 0이 리턴되도록 해준다.

function countUniqueValues(arr){
if(arr.length === 0) return 0;

let i = 0;
  for(let j = 1; j<arr.length; j++){
      if(arr[i] !== arr[j]){
          i++;
          arr[i] = arr[j];
      }
  }
  return i + 1;
}

 

맞았다. 예에~~!