[프로그래머스 / 완주하지 못한 선수 / JAVA / 해시]

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

프로그래머스

 

문제 접근

첫 접근은 HashMap을 이용하면서 풀어나갔다.

그러나 Map은 중복을 거르기 때문에 동명이인 부분을 해결하려니 머리가 깨질 거 같더라

그래서 다 갈아엎고 그냥 String 배열 그 자체로 풀기로 하였다.

 

String 배열로 하니 짧게 적고 해결했으나,이 방법으론 정확성 테스트는 통과했으나 효율성 테스트에선 시간 초과로 걸렸다. 

정확성 테스트 O, 효율성 테스트 X

class Solution {
    public String solution(String[] participant, String[] completion) {
    
String answer = "";

for(int i=0; i<participant.length; i++) {
	for(int j=0; j<completion.length; j++) {
		if(participant[i].equals(completion[j])) {
			participant[i] = "";
			completion[j] = "";
		}
	}
}

for(String s : participant) {
	if(s != "") {
		answer = s;
		break;
	}
}

return answer;
  }
}

 

질문하기 코너에서 본인의 지식을 공유해주신 분의 댓글을 보니 내 방법은 모든 곳을 다 탐색하는 방법이라 낭비되는 연산이 있는 방법이라고 하시더라

그 분의 말론 

A = { b, a, f }

B = { f, a }

로 되있는 배열을 정렬해줘서

A = { a, b, f }

B = { a, f }

로 만들어주면 하나의 반복문에서 처음부터 비교하다가 다른 값이 나오면 그게 완주하지 못한 선수란 것

 

그걸 보고 작성한 코드

정확성 테스트 O, 효율성 테스트 X

import java.util.*;

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

        String answer = "";
		
		Arrays.sort(participant);
		Arrays.sort(completion);
		
		for(int i=0; i<completion.length; i++) {
			if(!participant[i].equals(completion[i])) return participant[i];
		}
        return participant[participant.length-1];
    }
}

정렬해주니 반복문 하나로 처리가 가능해졌다.

 

다른 사람 풀이

Map으로도 이렇게 짧게 풀 수 있다.

getOrDefault() 메서드는 해당 메서드 앞의 키 값이 있으면 키 값을 반환, 없으면 뒤에 지정한 값을 반환

getOrDefault()로 동명이인도 한 번에 해결됨

keySet() 메서드는 해당 Map의 key들을 출력해주는 메서드

반복문 내에서 완주한 선수들은 값이 0이 되었기에 0이 아닌 선수를 반환해줌

import java.util.*;

class Solution {
	public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}