투 포인터 - Two Pointers

2022. 1. 4. 19:00

https://blog.naver.com/nagne2011/222612468600

2. 투 포인터 - Two Pointers

 

 

#twoPointers #투포인터스

 

두번째 문제.

아래 내용을 구현하시오

 

대표사진 삭제

사진 설명을 입력하세요.

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        
        int length = numbers.Length;
        int[] result = new int[2];
        
        for(int i=0; i<length; i++)
        {
            for(int k=0; k<length; k++)
            {
                if(i==k)
                     continue;                
                if((numbers[i] + numbers[k]) == target)
                {
                    result[0] = i+1;
                    result[1] = k+1;
                    
                    if(i>k)
                    {
                        int temp=-1;
                        temp = result[0];
                        result[0] = result[1];
                        result[1] = temp;
                    }                    
                    break;
                }
            }
        }        
        return result;
    }
}

 

간단하게, 이중for문 돌면서 각각 더해서 결과값이 나올때까지 돌리...

니까 시간제한에 걸린다

배열의 모든 값에 접근하기 *2 상황이다보니까 배열이 커지면 너무 오래걸리는 문제

 

그래서 새로운 탐색 알고리즘을 짜야된다

(다른 해답으로는, 이전에 만들었던 이진탐색 응용해서 이중으로 이진탐색하는 방법도 있다)

이럴때 사용하는게 투포인트

 

원리자체는 간단하다

사진 삭제

사진 설명을 입력하세요.

이렇게 한칸씩 확인하면서 거꾸로 역순하는것

 

코드로 확인하면 아래와 같다

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        
        int length = numbers.Length;
        int[] result = new int[2];
        
         if (numbers == null || numbers.Length < 2) return result;
        
        int start = 0;
        int end = numbers.Length -1;
        
        while(start < end)
        {
            if(numbers[start] + numbers[end] > target)
            {
                end--;
            }
            else if (numbers[start] + numbers[end] < target)
            {
                start++;
            }
            else
            {
                result[0] = start +1;
                result[1] = end +1;
                break;
            }
        }
        
        return result;
    }
}

 

시작, 끝점을 시작으로 하나씩 비교하면서 범위를 좁혀가며 계산한다

 

같은방식으로, 배열의 순서를 뒤집는 알고리즘에도 활용할 수 있다

 

사진 삭제

사진 설명을 입력하세요.

양끝 데이터를 서로 바꾸고 중간값에 도달할때까지 반복하면 중간값을 기준으로 좌우가 바뀌게되는 방식

 

public class Solution {
    public void ReverseString(char[] s) {        
        int start = 0;
        int end = s.Length - 1;        
        while(start < end)
        {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            
            start++;
            end--;
        }        
    }
}