수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
※ 제한사항 ※
* 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
* completion의 길이는 participant의 길이보다 1 작습니다.
* 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
* 참가자 중에는 동명이인이 있을 수 있습니다.
List 활용
처음에는 List에 참여선수를 다 넣었다가 완주선수를 다 빼면 한 명 남으니까 그렇게 하면 되겠다고 생각했다. 정확성 테스트는 다 통과였는데 효율성 테스트에서 1, 2, 3, 4, 5번이 다 실패했다.
효율성 테스트 실패 이유 분석
왜 효율성 테스트에서 다 실패했을까 생각해보다 List의 remove 메서드는 어떻게 돌아가는지 궁금해서 자바 공식 문서를 찾아봤다.
헉! remove의 return값이 있었다니?? 포함하면 true를 return한다니??
오.. 신기한 발견. 메서드 설명을 더 자세히 보니list에서 Object o를 지울 때는 첫번째로 발견한 o와 같은 원소를 지운다는 것 같다. 그 말은 첫번째 원소부터 이거 같은건가? 아니네 같은건가? 같네 그럼 지워. 이런 매커니즘으로 돌아가는 걸까? remove 메서드의 시간복잡도는 어떻게 되는 걸까 하고 찾아보니
앞에서부터 순차적으로 해당 객체와 동일한 객체를 찾고 index 뒤쪽의 element들을 앞으로 한칸씩 이동하므로 시간복잡도는 배열의 원소의 갯수 N에 비례하여 O(n)이다.
라고 한다. 그럼 나는 그 remove를 for문에 넣고 돌린 것이므로 O(n2)이 되어서 최악으로 따지면 10만*10만 = 100억번이 돌아간다. 그러니까 효율이..똥망..
해결 방안 찾기
효율도를 높이려면 뭔가 다른 자료구조형을 써야 할 것 같았다. 문제 분류를 보니 해시로 되어 있었다. !! 알고리즘 문제구나!! 해시 알고리즘에 대해 찾아보니 정확히 이해는 하지 못했지만 key, value로 이루어진 자료구조인 것 같았다. list처럼 원소를 하나하나 다 검증해 보는게 아니고 key에 맞는 value만 찾는 매커니즘으로 돌아가는 거니까 훨씬 빠를 것 같았다. 자바의 Map이 key, value 자료구조이니까 Map을 이용하면 될 것 같았다.
코드 짜보기
Map 메서드는 주로 key값을 이용한 메서드가 많으므로 key값에 선수들의 이름을 넣어서 해결하자.
1) containsKey 메서드 이용
key값에 완주선수의 이름을 다 넣고 key값에 없는 참여자의 이름을 확인하여 완주하지 못한 선수를 찾는다. >> 동명이인의 문제를 해결하지 못한다. key값은 같을 수 없기 때문.
2) replace 메서드 이용
key값에 참여자들의 이름을 넣고 value값에 1을 준다. 이미 key값에 참여자의 이름이 있으면(동명이인) value값에 1을 더해준다. replace 메서드를 이용하여 참여자의 키에 따른 value를 1씩 빼준다. 값이 1인 key를 찾아 return한다.
HashMap에 replace 메서드가 있길래 자바 공식 문서로 찾아보니 Map에도 HashMap에도 없길래 구글에 java map replace method oracle 라고 검색해보니 Interface Map<K,V> 페이지에 있었다.
Map에서 값을 수정할 때는 put() 메서드도 replace() 메서드도 많이 사용되는데 put() 메서드는 수정하려는 key값이 없으면 map에 새로운 매핑을 하나 만들고, replace() 메서드는 수정하려는 key값이 없으면 아무 행동도 하지 않는다.
이 문제에서는 둘 다 써도 문제가 없으므로 공부 삼아(?) 좀 덜 익숙한 replace 메서드를 써보기로 했다.
public String solution( String[] participant, String[] completion ) {
Map< String, Integer > partMap = new HashMap<>();
for ( int i = 0 ; i < participant.length ; i++ ) {
if ( partMap.containsKey( participant[i] ) ) {
partMap.replace( participant[i], partMap.get( participant[i] ) + 1 );
} else {
partMap.put( participant[i], 1 );
}
}
for ( int i = 0 ; i < completion.length ; i++ ) {
partMap.replace( completion[i], partMap.get( completion[i] ) - 1 );
}
for ( String key : partMap.keySet() ) {
if ( partMap.get( key ) == 1 ) {
return key;
}
}
return "";
}
내 생각보다 for문을 너무 많이 쓴 거 같아서 통과가 될지 안될지 조마조마..
통과!!!
다른 사람 코드 리뷰
1번째.
나는 참여자의 그룹을 key값에 넣을 때 if문을 하나 써서 이미 참여자가 있으면 1 더해주세요. 를 썼는데 Map에 getOrDefault 메서드가 있어서
partMap.put( participant[i], partMap.getOrDefault( participant[i], 0 ) + 1 );
이렇게 했으면 5줄을 1줄로 쓸 수 있었다!!
getOrDefault 메서드는
key가 이미 매핑되어 있으면 value를 return해주고, 매핑되어 있지 않으면 defaultValue를 return해주는 메서드이다.
새로운 메서드를 알게 됨!
2번째.
첫번째, 두번째 for문을 향상된 for문으로 썼으면 좀 더 가독성이 좋았을 것 같다.
3번째.
3번째 for문에서 keySet()과 get() 메서드를 사용하는 것이 아닌 entrySet()과 entry.getKey() 메서드를 사용하는 것이 더 효율적이라고 한다. HashMap의 케이스에서 keySet()을 사용하는 경우 get() 메서드를 호출할 때마다 value를 찾기 위해 hashcode()와 equals() 메서드가 요구되어진다.
하지만 entrySet()과 .getKey()나 getValue()를 사용하는 경우 위와 같이 요구되어지는 메서드를 요구하지 않고 entry 속성 값을 바로 가져온다.
entrySet()의 사용법은 다음과 같다.
Map< Integer, String > map = new HashMap<>();
for(Map.Entry entry : map.entrySet()){
Object key = entry.getKey();
Object value = entry.getValue();
}
코드를 고쳐보자.
public String solution( String[] participant, String[] completion ) {
Map< String, Integer > partMap = new HashMap<>();
for ( String part : participant ) {
partMap.put( part, partMap.getOrDefault( part, 0 ) + 1 );
}
for ( String comp : completion ) {
partMap.replace( comp, partMap.get( comp ) - 1 );
}
for ( Map.Entry entry : partMap.entrySet() ) {
if ( entry.getValue().equals( 1 ) ) {
return entry.getKey().toString();
}
}
return "";
}
[참고한 페이지들]
- https://chunsubyeong.tistory.com/81
- https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/
- https://medium.com/humanscape-tech/%EC%BD%94%EB%93%9C%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0-b67dd8625966
- https://javakong.tistory.com/133
- https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9C
- https://devlogofchris.tistory.com/41
- https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#replace-K-V-%EF%BB%BF
- https://stackoverflow.com/questions/3870064/performance-considerations-for-keyset-and-entryset-of-map
'STUDY > JAVA' 카테고리의 다른 글
[TIL] 프로그래머스 - 신규 아이디 추천 (0) | 2023.05.28 |
---|---|
[TIL] 다형성 코드로 익혀보기 (0) | 2023.05.27 |
[TIL] 프로그래머스 - 체육복 (0) | 2023.05.23 |
[TIL] 프로그래머스 - 숫자 짝꿍 (0) | 2023.05.22 |
[TIL] 약수의 개수 구하기 빠른 방법 (0) | 2023.05.14 |