Two Sum - 리트코드

https://leetcode.com/problems/two-sum

평가

결과 : 1회 실패 후 성공
풀이시간 : 11분

또!!! 수도코드 써놓고 놓쳤다.
정렬을 해야 하는데 깜빡했다.
마음을 자꾸 급하게 먹어서 그러는걸까, 왜그러는걸까...
이런 실수 정말 하지 말자.

아이디어

두 개의 값으로 하나의 결과를 만드는 문제입니다.
이런 문제에는 투포인터 알고리즘을 사용할 수 있습니다.
설명은 아래 수도코드에 적어두겠습니다.

수도코드

1. 배열을 오름차순으로 정렬한다
2. 배열의 가장 왼쪽, 가장 오른쪽에 포인터를 두 개 위치시킨다.(left, right)
3. while 문을 돌면서 선택한 두 개의 값으로 target을 만들 수 있는지 확인한다.
3-1. left와 right를 더한 값 > target 이면, right를 1 줄여준다.
	(left랑 right를 더한 값을 더 작게 만들어줘야 하니까)
3-2. left와 right를 더한 값 < target 이면, left를 1 키운다.
	(left랑 right를 더한 값을 더 크게 만들어줘야 하니까)
3-3. 값이 일치하면 left와 right의 인덱스를 반환한다.

정답 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int idx = 0;
        List<Node> nodes = new ArrayList<>(nums.length);
        for(int num: nums) {
            nodes.add(new Node(num, idx++));
        }

        // 오름차순 Sort
        nodes.sort(new Comparator<>() {
            @Override
            public int compare(Node n1, Node n2) {
                return n1.val - n2.val;
            }
        });
    

        // 투포인터로 target을 만들 수 있는 두 Node를 찾는다
        int left = 0;
        int right = nodes.size() - 1;

        while(true) { // 어차피 정답 있음
            int sum = nodes.get(left).val + nodes.get(right).val;
            if (sum == target) {
                return new int[] { nodes.get(left).idx, nodes.get(right).idx };
            } else if (target < sum) {
                right -= 1;
            } else {
                left += 1;
            }
        }
    }

    static class Node {
        int val;
        int idx;

        public Node(int val, int idx) {
            this.val = val;
            this.idx = idx;
        }
    }
}