본문 바로가기

Algorithm

프로그래머스 - (Java) 해시

728x90

프로그래머스에 있는 문제 분류별에 있는 해시 문제를 풀어보았다. 

https://github.com/mjung1798/Algorithm/tree/master/algorithm_JAVA/src/com/jyami/programmers/hash

 

mjung1798/Algorithm

My Algorithm Source Code Storage :). Contribute to mjung1798/Algorithm development by creating an account on GitHub.

github.com

 

1. HashMap<T, K>의 유용한 method .getOrDefault(T key, K defaultValue)

완주하지 못한 선수를 풀면서 새로운 메소드를 알게 되었다.

public String solution(String[] participant, String[] completion) {
	HashMap<String,Integer> map = new HashMap();

	for(String part : participant){
		Integer integer = map.get(part);
		if(integer == null) {
			map.put(part, 1);
			continue;
		}
		map.put(part, ++integer);
	}
}

이렇게 되어있는 코드였는데 map.get  해서 null이 아닐경우 (= 새로 들어오는 키 값일 경우에는 0을 put 하고 싶은 경우) 다른 key 값을 insert 한다. 이 코드를 getOrDefault()를 이용하면 간단하게 만들수 있는데,

public String solution(String[] participant, String[] completion) {
	HashMap<String,Integer> map = new HashMap();

	for(String part : participant){
		Integer integer = map.getOrDefault(part, 0);
		map.put(part, ++integer);
	}
}

이렇게 코드가 깔끔해 진다.

 

2. HashMap<T, K>의 유용한 method .putIfAbsent(T key, K value)

위 예제 코드를 만들다가, 새로운 메소드를 알게되었는데,

for(String part : participant){
	Integer num = map.get(part);
	if(num == null){
		map.put(part, 1);
	}
}

 만약 이런 경우라면, 메소드 하나로 간소화할 수 있었다.

for(String part : participant){
	Integer num = map.putIfAbsent(part, 1);
}

map에 part에 해당하는 key-value 쌍이 없는지 key에 대한 null 체크를 한 후 put하겠다는 의미이다.

 

3. String 클래스 - prefix 체크, 앞 글자 체크

.startsWith(@NotNull() String prefix, int toOffset)

전화번호부 문제를 풀다가 앞 글자를 체크해야하는 로직이 있어서 regex를 쓸까 하다가 String 클래스를 찾아보았다.

String.java 클래스 안에 있는 boolean startsWith(@NotNull() String prefix, int toOffSet) 함수이다.

String str1 = "hello world";
String str2 = "hello";
String str3 = "ello";

System.out.println(str1.startsWith(str2)); // true
System.out.println(str1.startsWith(str3)); // false

System.out.println(str1.startsWith(str3, 1)); // true

toOffset을 사용하지 않았을 경우에는, 문자열의 제일 앞에서부터 비교해서 prefix가 메소드를 호출한 value와 모두 대응되면 true를 리턴한다.
toOffset을 사용하는 경우에는, 해당하는 index에서부터 비교해서 prefix가 메소드를 호출한 value와 모두 대응되면 true를 리턴한다.

이때, 안에 String.java 파일을 살펴보니 빠른 비교를 위해, string을 하나하나 비교하기 전,
toOffset이 음수이거나, value보다 value.length - prefix.length 가 toOffset보다 작으면 (value보다 prefix의 길이가 더 긴 경우) 바로
false를 리턴하고, 그렇지 않은경우에는 문자열을 (toOffset의 위치부터 시작해) 앞에서부터 하나씩 비교해서 boolean을 판단한다.

 

4. Collections 클래스 - Comparable vs Comparator

베스트 앨범 문제를 풀면서 다시 한번 정리한다. 자바에서 알고리즘은 Collections 클래스를 얼마나 잘 쓰느냐에 있는 듯.

class Album {
	int plays;
	int number;

	Album(int plays, int number) {
	this.plays = plays;
	this.number = number;
	}
}

다음과 같은 클래스를 정렬한다고 생각하고 두가지 인터페이스를 비교해보겠다.

 

4-1. Comparator

Comparator은 이 클래스의 정렬을 여러개의 Comparator중에 지정한 것으로 정렬한다.
compare의 로직을 해당 클래스 안이 아니라 새로운 Comparator 클래스를 선언하여 구현한다는 특징이 있고,
두 개의 argument 사이의 비교를 이용한다.

[정의]

class AlbumCompare implements Comparator<Album> {
	@Override
	public int compare(Album o1, Album o2) {
		return Integer.compare(o1.plays, o2.plays);
	}
}

[사용]

public static void main(){
	List<Album> albums = Arrays.asList(new Album(10,0),new Album(20,1), new Album(30,2));
    albums.sort(new AlbumCompare());
}

.sort 메소드 안 parameter로는 Comparator를 넣게 되어있어서 새로 정의한 클래스를 객체로 정의해서 넣으면 된다.

 

4-2. Comparable

Comparable은 이 클래스의 default 정렬을 정의할 때 사용한다.
compareTo의 로직을 해당 클래스 안에 구현한다는 특징이 있고, this와 prameter로 들어온 argument와 비교한다.

[정의]

class Album implements Comparable<Album>{
	int plays;
	int number;

	Album(int plays, int number) {
		this.plays = plays;
		this.number = number;
	}

	@Override
	public int compareTo(Album o) {
		return Integer.compare(this.plays, o.plays);
	}
}

[사용]

public static void main(){
	List<Album> albums = Arrays.asList(new Album(10,0), 
		new Album(20,1), new Album(30,2));
		Collections.sort(albums);	//방법 1
		albums.sort(Album::compareTo);	//방법 2
	}
}

이때 Collections.sort(); 는 해당 클래스 안에 default로 정의된 Comparable을 이용하는 방법이고, 
.sort() 메소드는 Comparator를 이용하는 방법이다. sort()인자로 Album::compareTo를 넣으면, Comparable의 override인
compareTo()메소드가 Comparator 타입으로 변하게 되어서 두가지 방법으로 사용할 수 있다.

  Comparator Comparable
sort 사용법 object.sort(new Comparator()); Collections.sort(object);
object.sort(Object::compareTo);
비교 메소드 compare(Object o1, Object o2.) compareTo(Object o)
구현 장소 클래스 외부 클래스 내부

 

  • norman 2020.01.09 17:04 댓글주소 수정/삭제 댓글쓰기

    잘봤습니다. Map의 putIfAbsent 메서드는 computeIfAbsent 메서드와 비교하는 글도 읽어보면 좋을거 같습니다. ㅎㅎ
    ```
    var theKey = "Fish";
    //Even though if the key is present, the callExpensiveMethodToFindValue will get called
    productPriceMap.putIfAbsent(theKey, callExpensiveMethodToFindValue(theKey));
    //The callExpensiveMethodToFindValue will never get called if key is already present
    productPriceMap.computeIfAbsent(theKey, key -> callExpensiveMethodToFindValue(key));
    ```
    출처 : https://dzone.com/articles/how-to-use-java-hashmap-effectively?fbclid=IwAR1ZMb6aImx-7Ry-GD6S-YfxdDkrRvlSo-SlSVL08gRDxWP_zilcVnuXXtM

    • 와 좋은자료 감사합니다! 덕분에 하나 더 알아가네요. computeIfAbsent는 value 부분에서 람다식 등을 이용해서 한번더 계산을 할 수 있고, putIfAbsent는 오로지 값 자체만 넣을 수 있는 걸로 이해했는데 맞나요?

  • norman 2020.01.10 14:48 댓글주소 수정/삭제 댓글쓰기

    네 ㅎㅎ 맞습니다.

    ```
    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
    public V putIfAbsent(K key, V value)
    ```

    그리고 저도 다시 보면서 기존 방식에 비해 computeIfAbsent 메서드가 얼마나 효율적인지 궁금해서
    StopWatch로 간단히 비교해봤습니다. 제 로컬컴퓨터에서는 computeIfAbsent 메서드 쓰는 방식이 오히려 시간이 더 걸리네요 ㅎㅎㅎ
    ```
    @Test
    public void fibonacciTest() {
    Fibonacci fibonacci = new Fibonacci();
    StopWatch stopWatch = new StopWatch("TEST";);

    stopWatch.start("fibonacci v1";);
    fibonacci.fibonacciV1(1000);
    stopWatch.stop();

    stopWatch.start("fibonacci v2";);
    fibonacci.fibonacciV2(1000);
    stopWatch.stop();
    System.out.println("TotalTimeMillis : " + stopWatch.getTotalTimeMillis());
    System.out.println(stopWatch.prettyPrint());
    }

    static class Fibonacci {
    private Map<Integer, BigInteger> memoizeHashMap = new HashMap<>();

    Fibonacci() {
    memoizeHashMap.put(0, BigInteger.ZERO);
    memoizeHashMap.put(1, BigInteger.ONE);
    memoizeHashMap.put(2, BigInteger.ONE);
    }

    private BigInteger fibonacciV1(int n) {
    if (memoizeHashMap.containsKey(n)) {
    return memoizeHashMap.get(n);
    } else {
    BigInteger result = fibonacciV1(n - 1).add(fibonacciV1(n - 2));
    memoizeHashMap.put(n, result);
    return result;
    }
    }

    private BigInteger fibonacciV2(int n) {
    return memoizeHashMap.computeIfAbsent(n,
    (key) -> fibonacciV2(n - 1).add(fibonacciV2(n - 2)));
    }
    }
    ```
    ```
    TotalTimeMillis : 35
    StopWatch 'TEST': running time (millis) = 35
    -----------------------------------------
    ms % Task name
    -----------------------------------------
    00002 006% fibonacci v1
    00033 094% fibonacci v2
    ```

    • 오우 실험까지!!! 맞아요ㅠㅠ 사실 알고리즘 풀다보면 stream이나 자바 collection api가 편하긴하지만 내부적으로 어떻게 동작하는지 모르니까 시간이 항상 궁금하더라구요🧐