programmers.co.kr/learn/courses/30/lessons/42626

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        
        // 전처리 ,입력
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int answer = 0;
        for ( int i : scoville ){
            pq.add(i);
        }
        
        // 계산
        int a, b;
        try{
            while (pq.peek() < K ){
                a = pq.poll();
                b = pq.poll();
                pq.add(a + 2 * b);
                answer++;
            }
        } catch(Exception e){
            return -1;
        }
        return answer;
    }
}

프로그래머스에서 기본 연습문제로 제공하는 Heap 문제

우선순위 큐를 사용해서 첫번째와 두번째 값을 가져오는데 특정 값 K가 만족 되지 않으면 계속 반복하는데 while(true)를 사용하면 불가능한 경우에도 출력하려다가 NullPointException을 발생시키게 된다. 그 에러 케이스를 이용해서 return -1을 사용하여 문제 해결

Java에서 동치성을 확인 할 때 equals()와 hashCode() 두 개의 메서드로 확인하는 데 예전에 공부했던 기억은 있는데 정확하게 기억이 안나서 다시 보기로 했다.

Java API에서 hashCode()와 equals() 메서드의 정의는 java.lang.Object에 있다.

docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--

해시코드

This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the Java™ programming language.

해시코드 메서드는 따로 오버라이딩을 하지 않으면 객체의 내부 주소를 정수형으로 반환한다.

따로 객체를 만들고 오버라이딩 하지 않은 후 System.identityHashCode()를 사용해서 비교해봤다.

public class A{
	priavte int a;
    
	A(int a){
		this.a = a;
	}
}


public class Main(String[] args){
	A a = new A(1);
	A b = new A(1);

	System.out.println("address of a\t: " + System.identityHashCode(a));
	System.out.println("hashCode of a \t: " + a.hashCode());
		
	System.out.println();
	System.out.println("address of b\t: " + System.identityHashCode(b));
	System.out.println("hashCode of b \t: " + b.hashCode());

	System.out.println();
	System.out.println("a.equals(b) : " + a.equals(b));
}

당연히 해시코드를 따로 선언해주면 잘 돌아간다.

public class A{
	priavte int a;
    
	A(int a){
		this.a = a;
	}
    
    @Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + a;
		return result;
	}
}

해시코드하면 떠오르는 게 있는데 HashMap, HashSet, HashTable들이다.

해시코드를 키로 사용하는 애들이니까 hashCode()만 오버라이드하면 같은 객체로 인식하지 않을까 테스트 해봤다.

import java.util.HashMap;

public class Main(String[] args){

	HashMap<A, Integer> hm = new HashMap<>();
	A a = new A(1);
	A b = new A(1);
    
	hm.put(a, 1);
	hm.put(b, 1);
    
	System.out.println("address of a\t: " + System.identityHashCode(a));
	System.out.println("hashCode of a \t: " + a.hashCode());
		
	System.out.println();
	System.out.println("address of b\t: " + System.identityHashCode(b));
	System.out.println("hashCode of b \t: " + b.hashCode());

	System.out.println();
	System.out.println("a.equals(b) : " + a.equals(b));

	System.out.println("HashMap Size : " + hm.size());
}

해시맵 사이즈를 보면 해시코드값만 같다고 키값이 같은건 아니란걸 알 수 있다.

자세히 알아본 결과 해시 구조를 사용한 자료구조에서는 HashCode를 먼저 비교한 후에 해시코드가 동일하면 equals()를 통해서 동치성을 확인한다는 내용이었다.

잘찾아보면 친절하게 설명도 해주신다

docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#get-java.lang.Object-

More formally, if this map contains a mapping from a key k to a value v such that (key==null ? k==null : key.equals(k)), then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

여기서 K가 의미하는 자료형이 해시코드라는걸 생각한다면 해시구조에서 동치성을 확인 할 때 해시코드를 먼저 비교하고 해시코드가 같으면 equals()로 동치성을 확인한다는걸 알았다.

만약에 해시코드만 다르다? 동치성은 확인조차 못하고 넘어간다.

# Reference Type의 경우는 위에서 서술한 Object Class에서 상속받은 HashCode()와 equals()를 오버라이딩 하거나 시메모리 기본 메서드를 활용해서 동치성을 확인하지만 Primitive Type은 어떻게 동치성 ( == )을 확인할 수 있는 이유는 다음과 같다.

변수 선언부는 JVM의 Runtime Data Areadptj JVM Stack에 저장되고 기본형 타입의 데이터는 스택에 바로 저장하는 것이 아니라 Method Area 내부에 상수를 저장해둔 공간의 주소를 point 한다.

그래서 각 기본형 타입의 변수는 Method Area에 저장된 상수값을 불러오는 것이도 동치성을 확인하는 작업 ( == ) 에서는 상수의 주소를 비교해서 동치성을 체크하게 된다.