프로그래머스 - (Java) 해시 | Programmers - (Java) Hash
프로그래머스에 있는 문제 분류별에 있는 해시 문제를 풀어보았다.
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)); // truetoOffset을 사용하지 않았을 경우에는, 문자열의 제일 앞에서부터 비교해서 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) |
| 구현 장소 | 클래스 외부 | 클래스 내부 |
I solved the hash problems from the category section on Programmers.
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. Useful method of HashMap<T, K> .getOrDefault(T key, K defaultValue)
I learned a new method while solving the "Runner Who Didn't Finish" problem.
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);
}
}This was the original code — when map.get returns null (i.e., when it's a new key and you want to put 0), it inserts a different key value. This code can be simplified using 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);
}
}And just like that, the code becomes much cleaner.
2. Useful method of HashMap<T, K> .putIfAbsent(T key, K value)
While writing the example code above, I came across another new method:
for(String part : participant){
Integer num = map.get(part);
if(num == null){
map.put(part, 1);
}
}
In a case like this, it can be simplified down to a single method call.
for(String part : participant){
Integer num = map.putIfAbsent(part, 1);
}This means it does a null check on the key to see if there's no key-value pair for part in the map, and only then performs the put.
3. String Class - Checking Prefixes and Leading Characters
.startsWith(@NotNull() String prefix, int toOffset)
While solving the phone book problem, I needed logic to check leading characters. I was about to use regex, but then I looked into the String class instead.
It's the boolean startsWith(@NotNull() String prefix, int toOffSet) method inside the String.java class.
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)); // trueWhen toOffset is not used, it compares from the very beginning of the string and returns true if the prefix fully matches the value the method was called on.
When toOffset is used, it compares starting from the given index and returns true if the prefix fully matches the value the method was called on.
Looking inside the String.java file, for faster comparison, before comparing each character one by one,
if toOffset is negative, or if value.length - prefix.length is less than toOffset (meaning the prefix is longer than the value), it immediately
returns false. Otherwise, it compares characters one by one from the front (starting at the toOffset position) to determine the boolean result.
4. Collections Class - Comparable vs Comparator
I'm organizing this once again while solving the Best Album problem. It seems like Java algorithm skills come down to how well you can use the Collections class.
class Album {
int plays;
int number;
Album(int plays, int number) {
this.plays = plays;
this.number = number;
}
}Let's say we want to sort instances of this class, and compare the two interfaces.
4-1. Comparator
Comparator sorts this class using a specified Comparator among multiple Comparators.
A key characteristic is that the compare logic is implemented not inside the class itself but in a separate Comparator class,
and it uses two arguments for comparison.
[Definition]
class AlbumCompare implements Comparator<Album> {
@Override
public int compare(Album o1, Album o2) {
return Integer.compare(o1.plays, o2.plays);
}
}[Usage]
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());
}The .sort method takes a Comparator as its parameter, so you just need to instantiate the newly defined class and pass it in.
4-2. Comparable
Comparable is used to define the default sorting order for a class.
A key characteristic is that the compareTo logic is implemented inside the class itself, and it compares this with the argument passed as a parameter.
[Definition]
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);
}
}[Usage]
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
}
}Here, Collections.sort(); uses the default Comparable defined inside the class,
while .sort() uses a Comparator. If you pass Album::compareTo as the argument to sort(), the overridden
compareTo() method from Comparable gets converted to a Comparator type, so you can use it both ways.
| Comparator | Comparable | |
| Sort Usage | object.sort(new Comparator()); | Collections.sort(object); object.sort(Object::compareTo); |
| Comparison Method | compare(Object o1, Object o2.) | compareTo(Object o) |
| Implementation Location | Outside the class | Inside the class |
댓글
Comments