공부 기록

최소 거리를 구하는 방법보다는 최소 거리를 찍어놓고 그 거리가 가능한지 여부를 확인한다.

풀이 로직은 아래와 같다.

1. 이분탐색으로 가능한 거리 mid를 찍는다.

2. 없앨 돌의 수(remove)를 계산한다 - 돌 사이의 거리가 mid보다 짧으면 없애서 돌 사이의 거리를 늘린다.

3. 없앨 돌의 수가 n보다 큰 경우 돌 사이가 더 가깝다는 의미이므로 왼쪽탐색, n보다 작거나 같은 경우는 오른쪽을 탐색하면서 업데이트

import java.util.*;
import java.util.stream.Collectors;
class Solution {
	public int solution(int distance, int[] rocks, int n) {
		List<Integer> rock = Arrays.stream(rocks).boxed().collect(Collectors.toList());
		rock.add(0);
		rock.add(distance);
		Collections.sort(rock);

		int right = distance;
		int left = 0;
		int mid = 0;
		int answer = 0;

		while (left <= right) {
			mid = (right + left) / 2;
			int remove = 0;

			int i = 0;
			int j = 1;
			while (i < rock.size() && j < rock.size()) {
				if (rock.get(j) - rock.get(i) < mid) {
					remove++;
					j++;
				} else {
					i = j;
					j++;
				}
				if (remove > n) {
					break;
				}
			}

			if (remove <= n) {
				left = mid + 1;
				answer = Math.max(answer, mid);
			} else {
				right = mid - 1;
			}

		}

		return answer;
	}
}

1 ≤ n, m ≤ 1,000 이므로 브루트포스로 다 구해본다면 O(N^2M^2)로 시간 제한에 걸릴 것이다.

array를 무조건 한 번은 봐야하기 때문에 O(NM) * ???가 2초 안에 실행 되어야 한다.

DP로 풀어볼 수 있는 방법을 생각해 보자

dp[i][j]: (i,j)를 오른쪽 아래로 포함한 가장 크게 만들 수 있는 정사각형의 한 변 길이로 잡고, mat[i][j]==1일때 dp를 업데이트 한다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int row = in.nextInt();
		int col = in.nextInt();
		int mat[][] = new int[row][col];
		int dp[][] = new int[row][col];
		int maxLength = 0;

		for (int i = 0; i < row; i++) {
			String rowInput = in.next();
			int j = 0;
			for (char ch : rowInput.toCharArray()) {
				mat[i][j] = ch - '0';
				dp[i][j] = ch - '0';
				maxLength = ch - '0' > 0 ? 1 : 0;
				j++;
			}
		}

		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				if (mat[i][j] != 0) {
					dp[i][j] = findMinValueBetweenThree(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
					maxLength = Math.max(maxLength, dp[i][j]);
				}
			}
		}
		System.out.println(maxLength * maxLength);
	}

	public static int findMinValueBetweenThree(int a, int b, int c) {
		return Math.min(a, Math.min(b, c));
	}
}

import java.util.*;

public class Main {
	public static int henry(int a, int b) {
		int n = b / a;
		if (n * a >= b) {
			return n;
		}
		return n + 1;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int testcase = in.nextInt();

		for (int i = 0; i < testcase; i++) {
			int a = in.nextInt();
			int b = in.nextInt();

			while (true) {
				int x = henry(a, b);
				
				if (a * x == b) {
					System.out.println(x);
					break;
				}
				
				a = a * x - b;
				b = b * x;
			}
		}
	}
}

dp[n]: n원을 낼 수 있는 가짓수로 정의한다.

class Solution {
	public int solution(int n, int[] money) {
		int dp[] = new int[n + 1];
		dp[0] = 1;

		for (int coin : money) {
			for (int i = 1; i <= n; i++) {
				if (i - coin >= 0) {
					dp[i] += dp[i - coin];
				}
			}
		}

		return dp[n];
	}
}

왜 2중for문의 안과 밖이 바뀌면 중복된 값, 예를 들어 [10, 20, 10]과 [10, 10, 20]을 다른 경우로 체크해서 더 많은 값이 나온다.

예시 1 답: (트리의 지름) - 1

예시 2 답: (트리의 지름)

1차 시도 - 시간초과

트리의 지름을 가지는 노드가 2쌍 이상이면 2번 예시에 들어가고, 한 쌍이면 1번 예시에 들어가게 된다.

트리의 지름을 구하는 방법은

1. 임의의 노드에서 가장 먼 거리의 노드을 찾는다.

2. 찾은 노드에서 또 가장 먼 거리의 노드를 찾는다. => 이 값이 트리의 지름, 두 노드가 트리의 끝점이다.

class Solution {
	public static int radius = 0;
	public static HashSet<NodePair> endPoints = new HashSet<NodePair>();

	public int solution(int n, int[][] edges) {
		int[] distanceFromNodeOne = new int[n + 1];

		LinkedList<Integer> connectedNodes[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			connectedNodes[i] = new LinkedList<Integer>();
		}
		for (int i = 0; i < edges.length; i++) {
			int start = edges[i][0];
			int end = edges[i][1];

			connectedNodes[start].add(end);
			connectedNodes[end].add(start);
		}

		findRadius(1, connectedNodes, n, true);
		
		int maxSize = 0;
		for(NodePair nodepair:endPoints) {
			if(radius<=nodepair.distance) {
				maxSize++;
			}
		}

		if (maxSize >= 2) {
			return radius;
		}
		return radius - 1;
	}

	public void findRadius(int startPoint, LinkedList<Integer> connectedNodes[], int n, boolean isFirstTurn) {
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(new Node(startPoint, 0));

		int maxDistance = 0;
		int distanceFromNodeOne[] = new int[n + 1];

		// 1번 노드에서 가장 먼 노드 구하기
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			distanceFromNodeOne[node.name] = node.distance;
			maxDistance = Math.max(maxDistance, node.distance);

			LinkedList<Integer> connection = connectedNodes[node.name];
			for (int nextNode : connection) {
				if (distanceFromNodeOne[nextNode] == 0 && nextNode != startPoint) {
					queue.add(new Node(nextNode, node.distance + 1));
				}
			}
		}

		LinkedList<Integer> maxNodes = new LinkedList<Integer>();
		for (int i = 1; i <= n; i++) {
			if (distanceFromNodeOne[i] == maxDistance) {
				maxNodes.add(i);
			}
		}

		if (!isFirstTurn) {
			for (int nextPoint : maxNodes) {
				if (radius <= maxDistance) {
					endPoints.add(new NodePair(Math.min(startPoint, nextPoint), Math.max(startPoint, nextPoint),
							maxDistance));
					radius = maxDistance;
				}
			}
			return;
		}

		HashSet<Integer> nodeSet = new HashSet<Integer>();
		nodeSet.addAll(endPoints.stream().map(nodepair -> nodepair.node1).collect(Collectors.toSet()));
		nodeSet.addAll(endPoints.stream().map(nodepair -> nodepair.node2).collect(Collectors.toSet()));
		for (int nextPoint : maxNodes) {
			if (!nodeSet.contains(nextPoint)) {
				findRadius(nextPoint, connectedNodes, n, false);
			}
		}
	}
}

class Node {
	int name;
	int distance;

	public Node(int name, int distance) {
		this.name = name;
		this.distance = distance;
	}

	public String toString() {
		return name + " " + distance;
	}
}

class NodePair {
	int node1;
	int node2;
	int distance;

	public NodePair(int node1, int node2, int distance) {
		this.node1 = node1;
		this.node2 = node2;
		this.distance = distance;
	}

	public String toString() {
		return node1 + "-" + node2 + " " + distance;
	}
}

정확성: 84.6

합계: 84.6 / 100.0

시간초과가 난 이유는 아무래도 nodeSet을 계속 계산해 주어서가 아닐까 생각해본다.

2차 시도 - nodeSet을 static으로 빼기, 쓸데없는 객체 안쓰기 => 테스트케이스19 TL

import java.util.*;
class Solution {
	public static int radius = 0;// 트리의 지름
	public static HashSet<Integer> nodeSet = new HashSet<Integer>();// 지름이 되는 노드의 집합

	public int solution(int n, int[][] edges) {
		// 인접 노드 전처리
		LinkedList<Integer> connectedNodes[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			connectedNodes[i] = new LinkedList<Integer>();
		}
		for (int i = 0; i < edges.length; i++) {
			int start = edges[i][0];
			int end = edges[i][1];
			connectedNodes[start].add(end);
			connectedNodes[end].add(start);
		}
		findRadius(1, connectedNodes, n, true);
		if (nodeSet.size() == 2) {
			return radius - 1;
		}
		return radius;
	}

	/*
	 * 1. 임의의 노드에서 가장 먼 거리의 노드을 찾는다. 
	 * 2. 찾은 노드에서 또 가장 먼 거리의 노드를 찾는다. => 값이 트리의 지름, 두 노드가 트리의 끝점이다.
	 */
	public void findRadius(int startPoint, LinkedList<Integer> connectedNodes[], int n, boolean isFirstTurn) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(startPoint);
		int maxDistance = 0;// startPoint에서 가장 먼 길이
		int distanceFromStartNode[] = new int[n + 1];// startPoint에서 다른 노드들까지 거리
		// startPoint 노드에서 가장 먼 노드 구하기 - bfs
		LinkedList<Integer> maxNodes = new LinkedList<Integer>();// 가장 먼 노드의 집합
		while (!queue.isEmpty()) {
			int node = queue.poll();

			// 가장 먼 노드 집합 업데이트
			if (maxDistance < distanceFromStartNode[node]) {
				maxDistance = distanceFromStartNode[node];
				maxNodes.clear();
				maxNodes.add(node);
			} else if (maxDistance == distanceFromStartNode[node]) {
				maxNodes.add(node);
			}
			LinkedList<Integer> connection = connectedNodes[node];
			for (int nextNode : connection) {
				if (distanceFromStartNode[nextNode] == 0 && nextNode != startPoint) {
					queue.add(nextNode);
					distanceFromStartNode[nextNode] = distanceFromStartNode[node] + 1;
				}
			}
		}
		if (!isFirstTurn) { // 첫번째 턴이 아니면 = 지름 다 구했으니 리턴
			if (radius < maxDistance) {
				nodeSet.clear();
				nodeSet.add(startPoint);
				radius = maxDistance;
				for (int nextPoint : maxNodes) {
					nodeSet.add(nextPoint);
				}
			} else if (radius == maxDistance) {
				nodeSet.add(startPoint);
				radius = maxDistance;
				for (int nextPoint : maxNodes) {
					nodeSet.add(nextPoint);
				}
			}
			return;
		}
		
		// 첫번째 턴이면 여기서 다시 가장 먼 노드를 구한다
		for (int nextPoint : maxNodes) {
			if (!nodeSet.contains(nextPoint)) {
				findRadius(nextPoint, connectedNodes, n, false);
			}
		}
	}
}

채점 결과

정확성: 96.2

합계: 96.2 / 100.0

3차 시도 - 첫번째 턴에서 구한 모든 노드에서 다시 가장 먼 노드를 구할 때 중복된 연산이 존재한다는 것을 깨달았다.

그래서 기존 로직에서 살짝 바꿔서 트리의 지름이 될 수 있는 쌍이 몇쌍인지 먼저 생각해 보기로 했다.

1. 임의의 노드 A 에서 가장 먼 거리의 노드을 찾는다.

2. 찾은 노드 B 에서 또 가장 먼 거리의 노드 C 를 찾는다. => 이 값이 트리의 지름, 두 노드가 트리의 끝점이다.

    => C 노드가 2개 이상 == 예시 2

3. C 노드가 1개인 경우 다시 가장 먼 거리의 노드 D 를 찾는다 => D 노드가 2개 이상 == 예시 2 / 1개 == 예시 1

class Solution {
	public static int radius = 0;

	public int solution(int n, int[][] edges) {
		LinkedList<Integer> connectedNodes[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			connectedNodes[i] = new LinkedList<Integer>();
		}
		for (int i = 0; i < edges.length; i++) {
			int start = edges[i][0];
			int end = edges[i][1];

			connectedNodes[start].add(end);
			connectedNodes[end].add(start);
		}

		boolean isonepair = isOnePair(1, connectedNodes, n, 0);

		if (isonepair) {
			return radius - 1;
		}
		return radius;
	}

	public boolean isOnePair(int startPoint, LinkedList<Integer> connectedNodes[], int n, int turn) {

		int[] distanceFromStartPoint = calculateDistanceBFS(startPoint, connectedNodes, n);
		int maxNode = findMaxNode(distanceFromStartPoint, n);

		if (turn >= 1) {
			int maxNodeNum = 0;
			radius = Math.max(radius, distanceFromStartPoint[maxNode]);
			for (int i = 1; i <= n; i++) {
				if (distanceFromStartPoint[maxNode] == distanceFromStartPoint[i]) {
					maxNodeNum++;
				}
			}

			if (maxNodeNum >= 2) {
				return false;
			}

			if (turn > 1) {
				return true;
			}

			return isOnePair(maxNode, connectedNodes, n, 2);
		}

		return isOnePair(maxNode, connectedNodes, n, 1);
	}

	public static int findMaxNode(int[] distance, int n) {
		int maxNode = 1;
		for (int i = 1; i <= n; i++) {
			if (distance[i] > distance[maxNode]) {
				maxNode = i;
			}
		}
		return maxNode;
	}

	public static int[] calculateDistanceBFS(int startPoint, LinkedList<Integer> connectedNodes[], int n) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(startPoint);

		int distanceFromNode[] = new int[n + 1];
		while (!queue.isEmpty()) {
			int node = queue.poll();

			LinkedList<Integer> connection = connectedNodes[node];
			for (int nextNode : connection) {
				if (distanceFromNode[nextNode] == 0 && nextNode != startPoint) {
					queue.add(nextNode);
					distanceFromNode[nextNode] = distanceFromNode[node] + 1;
				}
			}
		}

		return distanceFromNode;
	}
}

규칙

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

1차시도 - 가장 먼저 떠오른 풀이로는 배정된 방 리스트를 해시맵에 넣어두고 있으면 다음 번호를 리턴해주면 되지 않을까 생각했다.

아래 코드를 설명해 보자면, 이미 예약된 호텔의 경우 해시 맵에 넣고 해시맵에 있으면 다음 번호를 확인하는 식이다.

import java.util.*;
class Solution {
	public long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		HashSet<Long> reservedRoomNumber = new HashSet<Long>();
		
		for(int i=0;i<room_number.length;i++) {
			answer[i] = getRoomNumber(room_number[i], reservedRoomNumber);
		}
		
		return answer;
	}

	public long getRoomNumber(long target, HashSet<Long> reservedRoomNumber) {
		if(reservedRoomNumber.contains(target)) {
			long emptyRoom = getRoomNumber(target+1, reservedRoomNumber);
			return emptyRoom;
		}
		
		reservedRoomNumber.add(target);
		return target;
	}
}

결과는 효율성 테스트에서 전멸했다...ㅎㅎ

생각해보니 이렇게 짜면 남아있는 다음 방을 찾을 때

10번방 다음 번호로 가능한 방 번호가 100번이면 11~100번까지 순차적으로 모두 봐야하니 시간초과가 날 수밖에 없었음

=> 순차적으로 본다고 해도 다음에 같은 번호를 찾을 때에는 다시 안 보도록 어딘가 저장을 해 두자 => DP를 사용해 볼까?

2차시도 - 그렇다면 10번방 바로 다음 번호가 100번인걸 어떻게 바로 알려줄까 생각해봤다.

DP라고 하기엔 조금 애매하지만,

dp[roomNumber] = nextEmptyRoomNumber 이런식으로 저장해서 다음에는 이 배열만 access하면 되도록 만들어 봤다.

import java.util.*;
class Solution {
	public long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		long[] dp = new long[(int) (k + 1)];

		for (int i = 0; i < room_number.length; i++) {
			answer[i] = getRoomNumber(room_number[i], dp);
		}

		return answer;
	}

	public long getRoomNumber(long target, long[] dp) {
		if (dp[(int) target] == 0.0) {
			dp[(int) target] = target + 1;
			return target;
		}

		long nextRoom = dp[(int) target];
		long nextEmptyRoom = getRoomNumber(nextRoom, dp);
		dp[(int) nextRoom] = nextEmptyRoom + 1;
		return nextEmptyRoom;
	}
}

엄청 빠르다...!! 그치만 메모리 초과와 런타임 에러가 생겼다. 

왜 이런지 생각해 봤는데 일단 k는 1 이상 10^12 이하인 자연수이다. (java에서 선언할 수 있는 최대 배열 길이는 2^31 − 1이다.)

3차 시도 - Long을 key로 할 수 있는 HashMap에다가 넣자!

왜냐면 쓸데 없이 만들어진 뒤에 쓰지 않는 배열 원소가 있어서 OOME가 났기 때문이다. 풀이는 아래와 같다.

2차시도에서처럼 array를 직접 접근하지 않고 logn으로 계속 찾는 형식이기 때문에 시간은 훨씬 오래 걸리지만 통과..

hashmap 외에 treemap, linkedhashmap은 더 느리다는 것을 확인했다.

class Solution {
	public long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		HashMap<Long, Long> roomRemainNumber = new HashMap<Long, Long>();

		for (int i = 0; i < room_number.length; i++) {
			answer[i] = getRoomNumber(room_number[i], roomRemainNumber);
		}

		return answer;
	}

	public long getRoomNumber(long target, HashMap<Long, Long> roomRemainNumber) {
		if (!roomRemainNumber.containsKey(target)) {
			roomRemainNumber.put(target, target + 1);
			return target;
		}

		long room = roomRemainNumber.get(target);
		long emptyRoom = getRoomNumber(room, roomRemainNumber);
		roomRemainNumber.put(target, emptyRoom + 1);
		return emptyRoom;
	}
}

배운점

2020/12/19 - [Java] - Java HashMap vs LinkedHashMap vs TreeMap

class Solution {
    public static int maxArea(int[] height) {
		int left = 0;
		int right = height.length - 1;
		int max = calcArea(left, right, height);

		while (left != right) {
			if (height[left] < height[right]) {
				left++;
			} else {
				right--;
			}

			max = Math.max(max, calcArea(left, right, height));
		}
		return max;
	}

	public static int calcArea(int left, int right, int[] height) {
		return (right - left) * Math.min(height[left], height[right]);
	}
}

문제 조건

배열이 중복되면 안됨 -> 그럼 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에서는 해시코드를 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를 사용하게 된다.