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

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

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

mjung1798/Algorithm

 

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)
구현 장소	클래스 외부	클래스 내부