leetcode: 4sum

문제 조건

배열이 중복되면 안됨 -> 그럼 hashset을 쓸까?

list 내의 원소들이 순서를 바꾸어도 같은 객체로 인식해야하기 때문에 정렬을 해서 넣어주도록 했다.

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
	public static List<List<Integer>> fourSum(int[] nums, int target) {
		int length = nums.length;
		HashSet<List<Integer>> answer = new HashSet<List<Integer>>();

		for (int i = 0; i < length; i++) {
			for (int j = i + 1; j < length; j++) {
				if (i == j) {
					continue;
				}

				for (int k = j + 1; k < length; k++) {
					if (i == k || j == k) {
						continue;
					}

					for (int l = k + 1; l < length; l++) {
						if (i == l || j == l || k == l) {
							continue;
						}

						if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
							List<Integer> subAnswer = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
							Collections.sort(subAnswer);
							
							answer.add(subAnswer);
						}
					}
				}
			}
		}
		System.out.println(answer.size());
		return answer.stream().collect(Collectors.toList());
	}
}

 

최적화

투 포인터를 이용해서 O(N^4)를 줄여보자

public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    return kSum(nums, target, 0, 4);
}
public List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
    List<List<Integer>> res = new ArrayList<>();
    if (start == nums.length || nums[start] * k > target || target > nums[nums.length - 1] * k)
        return res;
    if (k == 2)
        return twoSum(nums, target, start);
    for (int i = start; i < nums.length; ++i)
        if (i == start || nums[i - 1] != nums[i])
            for (var set : kSum(nums, target - nums[i], i + 1, k - 1)) {
                res.add(new ArrayList<>(Arrays.asList(nums[i])));
                res.get(res.size() - 1).addAll(set);
            }
    return res;
}
public List<List<Integer>> twoSum(int[] nums, int target, int start) {
    List<List<Integer>> res = new ArrayList<>();
    int lo = start, hi = nums.length - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        if (sum < target || (lo > start && nums[lo] == nums[lo - 1]))
            ++lo;
        else if (sum > target || (hi < nums.length - 1 && nums[hi] == nums[hi + 1]))
            --hi;
        else
            res.add(Arrays.asList(nums[lo++], nums[hi--]));
    }
    return res;
}

 

 

배운점

비슷하게 hashset안에 int[]를 넣어서 해봤을 때에는 왜 틀릴까?

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
	public static List<List<Integer>> fourSum(int[] nums, int target) {
		int length = nums.length;
		HashSet<int[]> answer = new HashSet<int[]>();

		for (int i = 0; i < length; i++) {
			for (int j = i + 1; j < length; j++) {
				if (i == j) {
					continue;
				}

				for (int k = j + 1; k < length; k++) {
					if (i == k || j == k) {
						continue;
					}

					for (int l = k + 1; l < length; l++) {
						if (i == l || j == l || k == l) {
							continue;
						}

						if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
							int[] subAnswer = new int[4];
							subAnswer[0] = nums[i];
							subAnswer[1] = nums[j];
							subAnswer[2] = nums[k];
							subAnswer[3] = nums[l];
                            
                            Arrays.sort(subAnswer);

							answer.add(subAnswer);
						}
					}
				}
			}
		}
		return answer.stream()
				.map(i -> Arrays.stream(i).boxed().collect(Collectors.toList()))
				.collect(Collectors.toList());
	}
}

결과 - HashSet이 같은 배열임을 인식하지 못한다. (지금 생각해보면 당연한 소리임...)

 

 

 

 

 

일단 hashSet 클래스를 보면 결국 HashMap을 이용해서 push하는 것과 같다.  

private transient HashMap<E,Object> map;

     /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element {@code e} to this set if
     * this set contains no element {@code e2} such that
     * {@code Objects.equals(e, e2)}.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns {@code false}.
     *
     * @param e element to be added to this set
     * @return {@code true} if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

HashMap의 put 함수는 아래와 같이 구현되는데, 같은 객체인지 판단할 때 hashCode를 사용함을 알 수 있다.

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with {@code key}, or
     *         {@code null} if there was no mapping for {@code key}.
     *         (A {@code null} return can also indicate that the map
     *         previously associated {@code null} with {@code key}.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    
    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    
    
    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

 

ArrayList 컬렉션에서는 이 hashCode를 오버라이드 하고 있었기 때문에,

오버라이드 된 해시코드를 사용하여 값이 같으면 동일 객체임을 판별할 수 있었던 것이다.

    /**
     * {@inheritDoc}
     */
    public int hashCode() {
        int expectedModCount = modCount;
        int hash = hashCodeRange(0, size);
        checkForComodification(expectedModCount);
        return hash;
    }

ArrayList hashCode docs

ArrayList에서는 해시코드를 entity의 해시코드의 합으로 정의하고 있다.

즉, ArrayList<Integer>의 해시코드는 Integer 의 해시코드들을 사용하여 만드는데, Integer에서 정의된 해시코드의 경우

값이 같은 경우 같은 해시코드를 갖게 된다.

    /**
     * Returns a hash code for an {@code int} value; compatible with
     * {@code Integer.hashCode()}.
     *
     * @param value the value to hash
     * @since 1.8
     *
     * @return a hash code value for an {@code int} value.
     */
    public static int hashCode(int value) {
        return value;
    }

 

결론적으로, ArrayList<Integer>의 경우 순서가 동일하고, 같은 값을 가진 리스트의 경우 같은 해시코드 값을 갖게 되어 hashSet에 들어갈 때 중복제거가 가능하다.

 

이와 달리 int[]의 경우 hashCode가 정의되어 있지 않기 때문에 부모 클래스, 즉 Node에 정의되어 있는 hashCode를 사용하게 된다.