99클럽 코테 스터디 1일차 TIL + HashMap

✨ 문제 

완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

 

처음에는 파라미터로 받은 participant 배열을 리스트로 변환한 뒤에 forEach문으로 completion에 존재하는 원소들을 participant 리스트에서 remove하도록 하였다.

배열을 리스트로 변환하는 과정에서 오류가 발생했는데 알고보니  Arrays.asList를 사용해서 배열을 생성하면 원본 배열에 대한 뷰를 반환하기 때문에 리스트의 크기가 고정되어 있다고 한다.

아무튼 리스트를 사용해서 코드를 완성하였는데 실행은 되었지만 효율성 테스트에서 통과하지 못했다. 아무래도 해시를 사용해서 풀어야하는 것 같아 다시 해시맵을 사용해서 풀어보았다. 

 

 

✨ 개념

Map

- Map은 키와 값으로 구성된 Map.Entry 객체를 저장하는 구조를 갖고 있다.

- Entry는 Map 인터페이스 내부에 선언된 중첩 인터페이스이다.

- 키와 값은 기본 타입을 사용할 수 없고 클래스 및 인터페이스 타입만 사용 가능하다.

- 또한 키는 중복 저장될 수 없지만 값은 중복 저장되며, 동일 키로 새로운 값을 저장하면 기존의 값이 대체된다.

 

Hash

- 해시 함수를 사용해 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑한 값

 

HashMap

- Hash를 활용한 Map.

- 해싱을 사용해 키를 해시 코드로 변환 후 이를 사용해 값이 저장될 인덱스를 결정.

- 상수 시간 복잡도O(1)로 매우 빠른 연산 속도가 장점.

 

 

✨ 최종코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> participantMap = new HashMap<>();

        for(String str : participant)
            participantMap.put(str, participantMap.getOrDefault(str, 0) + 1);

        for(String str : completion)
            participantMap.put(str, participantMap.get(str) - 1);

        for (Map.Entry<String, Integer> entry : participantMap.entrySet()) {
            if (entry.getValue() != 0)
                return entry.getKey();
        }

        return null;
    }
}

 

- getOrDefault

map에서 값을 가져올 때 값이 null일 경우를 대비해 값이 null이면 0을 반환하는 메소드.

 

 

이렇게 hashMap을 사용해서 효율성 테스트까지 통과하였다. 사실 gpt가 처음부터 hashmap을 사용하는 방법을 알려줬는데 결국은 gpt 답변과 거의 유사한 코드를 작성하게 되었다 . . 자료구조는 배열, 리스트를 제외하고는 거의 사용해보지 않았는데 이번에 99클럽에 참여하면서 여러 자료구조들을 사용해보고 각각 어떤 장단점이 있고 어떤 문제에서 어떤 자료구조를 사용하는 것이 효율적인지를 배우는 기회가 되었으면 좋겠다.