1. 완주하지 못한 선수(프로그래머스, 해시 Level 1)

* 문제 설명
 - 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 
 - 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
 - 마라톤에 참여한 선수들의 이름이 담긴 배열은 participant, 완주한 선수들의 이름이 담긴 배열은 completion
 - 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

* 제한사항
 - 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
 - completion의 길이는 participant의 길이보다 1 작습니다.
 - 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
 - 참가자 중에는 동명이인이 있을 수 있습니다.

 

아무 생각 없이 접근하였던 문제 입니다.
그래서 평소에 하던데로 반복문과 비교문만 활용하여서 접근을 해 보았습니다.

1. 참가한 배열 값에서, 완주한 배열값을 비교합니다.
2. 만약 참가한 배열값에서 완주한 배열값이 있으면 참가한 배열값을 null처리 합니다.
3. 2개의 반복문이 동작한 이후에 다시 반복문을 통해서 결과를 확인 합니다.

위 내용을 작성하여보면,

    public static String simple(String[] participant, String[] completion){
    	String answer = "";
    	participant = new String[]{"mislav", "stanko", "mislav", "ana"};
    	completion = new String[]{"stanko", "ana", "mislav"};
  
    	for(String target : completion){
    		for(int index = 0; index <participant.length ; index++){
    			if(target.equals(participant[index])){
    				participant[index] = null;
    				break;
    			}
        	}
    	}
    	for(String data : participant){
    		if(data != null){
    			answer = data;
    		}
    	}
    	System.out.println("answer : " + answer);
    	return answer;
    }

 

어렵지 않게 완성된 것을 볼 수 있습니다.

그러나, 해당 내용을 가지고 테스트는 성공했지만 채점 및 제출하였을때의 결과는..

정확성은 좋으나 효율성은 최악이네요..

 

소수의 인원일 경우에는 사실 위 코드는 아무 문제가 없습니다.

그런데 여기서 문제점은 10만명 이상이 참가할 수 있다는 점 입니다.

반복문이 위 코드처럼 2중으로 동작해야 한다면 최소 몇억번 단위의 반복문이 동작해야 하기 때문입니다.

결국 오래 동작해야 하므로 좋지않는 코드라는 것 입니다.

 

그래서 고민을 해 본 것이 반복문을 최소화 하는 것 입니다.

그리고 여기서 참석한 사람이라는 대상을 key로 활용 해 보면 어떨까 하는 것 입니다.

이를 위해 HashMap을 통해서 제거할 대상을 담아두기 위한 변수를 만들어 주었습니다.

public static String solution(String[] participant, String[] completion) {
    String answer = "";
    HashMap<String, Integer> remover = new HashMap<>();
    for(int index = 0;index < participant.length ;index++){
        String arg = participant[index];  //대상을 가져옵니다.
        remover.put(arg, index);	//참가한 사람을key, 배열순서를 value로 넣어줍니다.
    }
}

 

이제 참석한 사람 이름을 key값으로 하여 배열순서값(Int)을 가진 HashMap이 탄생 하였습니다.

그런데 위 내용으로 적용을 하면 문제되는 점이 바로 "동명이인" 입니다.

"동명이인" 인 경우에는 key값에 의해서 value가 덮어씌워지기 때문 입니다.

그러므로 value가 n개인 경우를 대비해야 합니다.

public static String solution(String[] participant, String[] completion) {
    String answer = "";
    HashMap<String, ArrayList<Integer>> remover = new HashMap<>();
    for(int index = 0;index < participant.length ;index++){
        String arg = participant[index];  //대상을 가져옵니다.
        if(remover.get(arg) != null){  //이미 추가되었다면
            remover.get(arg).add(index);  
        } else {  //처음이라면
            ArrayList<Integer> list = new ArrayList<>();  //ArrayList를 생성하여
            list.add(index);  //최초값을 넣어줍니다.
            remover.put(arg, list);	        
        }
    }
}

 

여기까지 하고나면 참석한 사람 이름이 key값을 기준으로하여 데이터가 묶이게 됩니다.

묶여진 HashMap데이터에서 완주한 배열값을 통해 데이터를 제거하며 정리하여 줍니다.

public static String solution(String[] participant, String[] completion) {
    String answer = "";
    HashMap<String, ArrayList<Integer>> remover = new HashMap<>();
    for(int index = 0;index < participant.length ;index++){
        String arg = participant[index];  //대상을 가져옵니다.
        if(remover.get(arg) != null){  //이미 추가되었다면
            remover.get(arg).add(index);  
        } else {  //처음이라면
            ArrayList<Integer> list = new ArrayList<>();  //ArrayList를 생성하여
            list.add(index);  //최초값을 넣어줍니다.
            remover.put(arg, list);	        
        }
    }
    
    for(String arg : completion){  //완주한 대상
        remover.get(arg).remove(0);  //완주했으면 제거하여 줍니다.
    }
}

 

완주한 대상의 배열의 반복문을 통해서 데이터가 제거가 되고 나면, 남는 데이터는 완주를 안한사람만 남을 것 입니다.

public static String solution(String[] participant, String[] completion) {
    String answer = "";
    HashMap<String, ArrayList<Integer>> remover = new HashMap<>();
    for(int index = 0;index < participant.length ;index++){
        String arg = participant[index];  //대상을 가져옵니다.
        if(remover.get(arg) != null){  //이미 추가되었다면
            remover.get(arg).add(index);  
        } else {  //처음이라면
            ArrayList<Integer> list = new ArrayList<>();  //ArrayList를 생성하여
            list.add(index);  //최초값을 넣어줍니다.
            remover.put(arg, list);	        
        }
    }
    
    for(String arg : completion){  //완주한 대상
        remover.get(arg).remove(0);  //완주했으면 제거하여 줍니다.
    }
    
    for( String key : remover.keySet() ){
        if(remover.get(key).size() > 0){  //데이터가 남아있다면
            answer = key;  //해당 값은 완주를 안한 사람 입니다.
            break;  //그만돌아!
        }
    }    
    return answer;
}

 

이렇게 완성된 코드를 적용해 보면,

통과했네..ㅠ

 

동작도 잘하고 나름 괜찮은 소스코드가 만들어 졌습니다.

배열을 정렬(sort) 해서 비교하는 방법도 괜찮았던 것 같습니다.

위 내용 말고도 고수(?) 분들의 코드를 보며 많은 생각을 해 보았던 것 같습니다.

다음 문제는 조금 더 생각하고 접근해 보아야 겠습니다.