[twoSum]

출처: 리트코드 grind75

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

해석:정수 배열 nums와 정수 target이 주어졌을 때, 두 숫자의 인덱스를 반환하세요. 이때 두 숫자를 더하면 target이 됩니다. 각 입력에는 정확히 하나의 해결책이 있다고 가정할 수 있으며, 동일한 요소를 두 번 사용해서는 안 됩니다.
답은 어떤 순서로든 반환할 수 있습니다.

 

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

 

 

public class Grind75_day1_TwoSum_problem {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 배열 입력 (한 줄로 받음)
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = st.countTokens();  // 토큰 개수로 배열 크기 결정

        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        // 타겟 값 입력
        int target = Integer.parseInt(br.readLine().trim());

        // Two Sum 알고리즘 실행
        int[] result = twoSum(nums, target);

        // 결과 출력
        System.out.println(result[0] + " " + result[1]);

        br.close();
    }
    public static int[] twoSum(int[] nums, int target) { // Two Sum 문제를 해결하는 메소드
        Map<Integer, Integer> numMap = new HashMap<>(); // 값과 인덱스를 저장할 해시맵 생성

        for (int i = 0; i < nums.length; i++) { // 배열을 순회하는 반복문
            int complement = target - nums[i]; // 현재 숫자와 더해서 타겟이 되는 보수 계산

            if (numMap.containsKey(complement)) { // 보수가 해시맵에 이미 있는지 확인
                return new int[] {numMap.get(complement), i}; // 있다면 보수의 인덱스와 현재 인덱스 반환
            }

            numMap.put(nums[i], i); // 현재 숫자와 인덱스를 해시맵에 저장
        }

        // 해답이 없는 경우 (문제 조건상 이 경우는 발생하지 않음)
        return new int[] {}; // 빈 배열 반환 (이 경우는 문제 조건상 발생하지 않음)
    }
}