Skip to content

Latest commit

 

History

History
58 lines (42 loc) · 2.69 KB

1814_java.md

File metadata and controls

58 lines (42 loc) · 2.69 KB

1814. Count Nice Pairs in an Array

Summary

🙇‍♂️ URL : https://leetcode.com/problems/count-nice-pairs-in-an-array/
🤷‍♂️ Difficulty: Medium
💆‍♂️ Submissions

  • RunTime: 232 ms, faster than 5.04% of Java online submissions
  • Memory Usage: 118.1 MB, less than 5.03% of Java online submissions

Source code

class Solution {
    public int countNicePairs(int[] nums) {
        int totalCount = 0;
        int mod = (int)Math.pow(10,9)+7;

        HashMap<Long, Integer> map = new HashMap<>();

        for(int i=0; i<nums.length; i++) {
            long value = nums[i] - getRev(nums[i]);
            if(map.containsKey(value)) {
                totalCount = (totalCount % mod + map.get(value) % mod) % mod;
            } 
            map.put(value, map.getOrDefault(value,0)+1);
        }

        // for(int i=0; i<nums.length-1; i++) {
        //     for(int j=i+1; j<nums.length; j++) {
        //         if(nums[i] == nums[j]) {
        //             totalCount+=1;
        //         }
        //     }
        // } 

        return totalCount;
    }

    public long getRev(int num) {
        StringBuffer sb = new StringBuffer(Integer.toString(num)); 
        String reversedStr = sb.reverse().toString(); 
        return Long.parseLong(reversedStr);
    }

How to Approach

이 문제를 통해 HashMap이 이정도로 빠르고 '생각보다 메모리의 부담을 별로 안갖는지' 알게 되었다.

nums[i] - rev(nums[j]) = nums[j] - rev(nums[i]) -> nums[i] - rev(nums[i]) = nums[j] - rev(nums[j]) 라는 것까지는 충분히 도출할 수 있었다. 그리고 주석과 같이 이 값들을 하나씩 찾아가면서 같은 값들이 나올때마다 카운트를 세어주는 방식으로 했다.

물론 이렇게 하면 O(n^2)이 될테지만, 그래도 해시맵에서 추가적인 메모리를 사용하는 것 보다는 빠를 것이라고 생각했는데.. 완전히 예상 밖이었다. 실제로 해시맵을 사용해서 훨씬 빨랐다(그럼에도 불구하고 시간복잡도는 별로 좋은 결과를 못 얻었지만).

추가로, 이 문제는 값이 커지는 것을 우려하여 10^9+7의 값으로 카운트를 모듈러(%)하라고 했다. 처음에 값이 제대로 나오지 않았는데, 이유는 끝까지 결과값을 계산하고 마지막 return에 모듈러 계산을 했기 때문이었다. 출력되는 모든 값에 대하여 모듈러 연산을 진행해줘야 문제에서 원하는 결과 값을 얻을 수 있었다.

참고로, 숫자 reverse는 문자열로 변환하여 다시 실수화시키는 방법으로 진행했다. 아마 이 부분을 바로 숫자로 변경했다면 속도가 조금 더 개선되었을 수도 있었을 것 같다.