[leetcode - Java] 167. Two Sum II - Input Array Is Sorted

1. 문제

---

- 오름차순으로 정렬된 배열에서 두 수를 합하여 target을 만들어라.

2. 의사 코드

---

1. 투 포인터 및 결과 담을 배열 설정
    int left = 0;
    int right = numbers.length-1;
    int[] result = new int[2];
2. 
    while (left < right) {
        2-1 배열 왼쪽과 오른쪽 요소를 더해 target과 일치 검사
        2-2 target보다 크다면 right 감소, 작다면 left 증가
        2-3 target과 일치했을 때 result 배열에 해당 요소의 순서 저장
    }

3. 시도

---

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
        int[] result = new int[2];

        // 반복문 내부에도 동일한 if가 있었지만 
        // numbers: [-1,0]
        // target: -1 
        // 위 상황에서 [1, 2]가 출력되야 하지만 [0, 0]이 출력된다.
        if (numbers[left] + numbers[right] == target) {
            result[0] = left+1;
            result[1] = right+1;
        }  

        while (left < right) {
            if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }

            if (numbers[left] + numbers[right] == target) {
                if (left == right) {
                    result[0] = left;
                    result[1] = right+2;
                    break;
                }
                result[0] = left+1;
                result[1] = right+1;
                break;
            }
        }

        return result;
    }
}

문제 풀이에 대한 방향은 맞은 것 같다. 하지만 아래 이미지와 같은 성공하지 못한 한 두개의 테스트 케이스 때문에 비슷한 조건이 생기게 되었고 불필요한 if도 생긴 것 같아 개선의 여지가 보인다.

4. 개선

---

작성한 코드를 계속 보다보니 조건문 if의 순서를 제대로 인식하지 못해 일어나는 문제라고 의심이 되었다.

반복문 위의 중복된 if를 지우고 반복문 내부의 if 순서를 바꾸며 else if로 수정.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
        int[] result = new int[2];

//         if (numbers[left] + numbers[right] == target) {
//             result[0] = left+1;
//             result[1] = right+1;
//         }  

        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                if (left == right) {
                    result[0] = left;
                    result[1] = right+2;
                    break;
                }
                result[0] = left+1;
                result[1] = right+1;
                break;
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }

        return result;
    }
}

코드 실행에 문제는 없었고 가독성 또한 높아졌다. 이전 코드에서는 numbers 배열의 left와 right 합이 target보다 큰 경우 right를 감소시키고, 작은 경우라면 left 포인터를 증가시킨 이후로 합이 target과 동일한지 검사했다. 포인터를 항상 먼저 움직였기에 조건문에서 꼬인 것 같았다.

완성된 코드는 아래와 같다.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
        int[] result = new int[2];

        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                result[0] = left+1;
                result[1] = right+1;
                break;
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }

        return result;
    }
}

조금 더 수정 한다면 반복문 내부에 아래와 같은 코드를 추가할 수 있을 것이다.
int sum = numbers[left] + numbers[right];