hash - 완주하지 못한 선수

첫 번째 풀이

 Scanner sc = new Scanner(System.in);
 HashMap<Integer, String> mapP = new HashMap<>();

 for (int i = 0; i < 4; i++) mapP.put(i, sc.next());

 String[] c = new String[mapP.size() - 1];

 for (int i = 0; i < mapP.size() - 1; i++) c[i] = sc.next();

 for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 4; j++) {
          if (c[i].equals(mapP.get(j))) {
              mapP.remove(j);
                 break;
           }
      }
  }

 for (String value : mapP.values()) System.out.println(value);
 

가관이다.
for 문의 범위는 내가 직접 입력을 받았기 때문에 저렇게 지정을 했다.
participant는 map에 다시 넣어주고,
이중 for문을 사용하여 completion과 값을 비교해서 일치하면 제거해줬다.

제출결과 정확성100, 효율성0 으로 원하는 결과는 나오지만 효율성이 많이 떨어지는 것을 알 수 있다

이중 for문을 사용했으므로 한 눈에봐도 O(n^2) 이상의 시간복잡도 이고, 효율성이 마찬가지로 매우 안좋은 것을 알 수 있다.

두 번째 풀이

문제를 한 번에 풀지 못한것을 나를 탓해야지 누굴 탓하겠냐
이제 제대로 자료구조와 알고리즘을 공부하는 것이니 너무 낙담하지는 말자

이번에는 hash라는 틀에 갖히지 않고 자유롭게 생각을 해봤다.
그 결과 정렬을 해서 앞에서부터 비교하며 어떨까?

public String solution(String[] participant, String[] completion) {

	Arrays.sort(participant); 
	Arrays.sort(completion); 

	int count = 0;

	if(completion.length==0) return participant[0];

	for (int i = 0; i < participant.length; i++) {
        if (participant[i].equals(completion[i])) {
            count++;
        }else{
            return participant[i];
        }
        if (count == completion.length) {
            return participant[participant.length - 1];
        }
    }

    return "test";
}

위 코드처럼 completion의 길이가 0으로 예외인 경우를 제외하고 for문을 한 번만 돌려서 구현을 했다.
안에 조건문을 간단히 할 수 있을 것 같지만, 문제유형이 요구하는 방식(해시) 대로 풀지는 않았으니 다른방법을 찾아보는것이 더 효율적인 공부법 인 것 같다.

위 코드는 정확성과 효율성 모두 100점으로 통과를 했다.

세 번째 풀이

이 풀이방법은 구글링을 참고하여 작성하였으므로 모든 코드를 작성하지는 않고
핵심 로직만 적어보겠다.

for (String p : participant) 
        map.put(p, map.getOrDefault(p, 0) + 1);
        
for (String p : completion) 
        map.put(p, map.get(p) - 1);

getOrDefault api는 처음봤다.
p 라는 Key에 해당하는 Value가 존재하면 가져오고, 없으면 0을 Default로 사용한다는 의미이다.

아래 for문은 값이 존재할 경우 -1로 한 명씩 제거해준다는 의미이다.

이후 map 에서 value값이(Integer) 1인 경우를 찾으면 해당 key값 (String) 이 완주하지못한 선수가 될 것이다.