Two Pointers : while 문으로 맛있게 풀기

 

 

문제의 유형을  two pointers 라고 주어졌다 . 

이것은 이중 반복문을 사용하여  , n! 로 접근을 하는 방식이 아니라 ,

하나의 탐색의 과정에서 두개 이상의 접근자 :index 를 조건에 맞추어 증감을 시키는 것이 포인트 이다  

 

Two pointer 의 기본 문제 유형을 먼저 보자.

 

125. Valid Palindrome

Valid Palindrome - LeetCode

 

Q. : S = "abba :  ac1 vd" 이 주어 졌을때 , 영어 숫자만 남긴 상황에서 앞뒤로 읽어도 같나 ?

 

-> Sting 에서 char 로 변환할 줄 알아야하며, char 비교 , 소문자 대문자 변환 , 알파벳 유무를 다루는 함수를 알아야한다.

 

StringBuilder 까지 사용하여 문제를 해결 할려고 하였지만,  두 번의 반복문의 실행으로 인하여 최적의 수행시간이 나오지는 않는다.

 

-> 그래도 제출자들 대비 평균의 성능 효율인 코드가 나오니 오답은 아니다.

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder answ = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char check = s.charAt(i);
            if (Character.isLetter(check)||Character.isDigit(check)) {
                char change = Character.toLowerCase(check);
                answ.append(change);
            }
        }
        String ans = answ.toString();
        int sizePal = ans.length();
        if(sizePal==0) return true;
        int maxC = (sizePal / 2) ;
        for(int i = 0 ; i < maxC ; i++ ) {
            if( ans.charAt(i) !=ans.charAt(sizePal - 1 - i)) return false;
        }
        return true;
    }
}

 

더 빠르고 더 효율적이게 작성을 해보자.

 

문자열의 양끝에서 동시에 접근을 하면서 O(N) 으로 처리 가능하게 작성을 하면 다음과 같다.

 

public class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;

        while (left < right) {
        	//좌측에서부터 조건에 맞는 단어 까지 탐색
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }

            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

 

167. Two Sum II - Input Array Is Sorted

 

저번에 푼 문제랑 동일 하다.

 

입력값이 정렬된 상태로 주어진다. 

 

위의 최적의 방식으로 풀면 다음과 같다. 

public int[] twoSum(int[] numbers, int target) {
        int left = 0 , right = numbers.length - 1;
        while (left < right){
            int sum = numbers[left] + numbers[right];
            if(sum == target) return new int[]{left+1,right+1};
            if(sum > target) right--;
            if(sum < target) left++;
        }
        return new int[]{};
    }

 

 

15. 3Sum

 

주어진 배열에서 3 개의 합이 0 이 되는 요소들을 찾는 문제이다.

 

위의 풀이 방식을 이용해서 풀어보자,

 

0 = nums[i] + nums[j] + + nums[k]

 

 

cf ) 추가로 이문제는 싱가폴 단기 어학연수 당시 구글러 분이 나한테 코딩 인터뷰 예시로 던저주신 문제와 상당히 상당히 유사하다.

-> 문제의 풀이가 떠오르는것도 좋지만.

"주어진 배열에서 3 개의 합이 0 이 되는 요소들을 찾는 문제" 를 받았을때의 접근을 다시 생각을 해보는 것 이 좋을 것 같다 . 

 

 public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int target = 0 ;

        int n = nums.length  ;
        int c = n - 1 ;
        Set<List<Integer>> ans = new HashSet<>();
        for(int i = 0 ; i  < n -1 ;i++) {
            int a = i ;
            int b = a + 1;
            while(c > b) {
                int sum = nums[a] + nums[b] + nums[c] ;

                if(sum == target)
                {
                    ans.add(List.of(nums[a],nums[b],nums[c]));
                    c--;
                    b++;
                } else if (sum > target) {
                    c--;
                }else {
                    b++;
                }
            }
        }

        List<List<Integer>> re = new ArrayList<>();
        re.addAll(ans);
        return re;
    }