거꾸로 했을때 동일

Changwook Yang·2023년 4월 8일

알고리즘 연습

목록 보기
41/41

    public static int solution(int[] numbers) {
        int count = 0;
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                long reverseI = reverseNumber(numbers[i]);
                long reverseJ = reverseNumber(numbers[j]);
                if (numbers[i] + reverseJ == numbers[j] + reverseI) { // 매직페어를 찾음
                    count++;
                }
            }
        }
        return count;
    }

	// 시간 복잡도 개선
    public static int solution(int[] numbers) {
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>(); // (numbers[i] - reverse(numbers[i])) 값과 그 개수를 저장할 맵
        for (int i = 0; i < numbers.length; i++) {
            int value = numbers[i] - (int) reverseNumber(numbers[i]); // (numbers[i] - reverse(numbers[i])) 값 계산
            int complementCount = map.getOrDefault(value, 0); // 현재 값의 보수(complement)가 몇 개 있는지 확인
            count = count + complementCount; // 현재 값의 보수와 매칭되는 개수를 카운트에 더함
            map.put(value, complementCount + 1); // 현재 값의 개수를 맵에 저장
        }
        return count;
    }
profile
멋있는 백엔드 개발자 / 꾸준히 의미있게!

0개의 댓글