알고리즘)[JAVA] 프로그래머스_해시_완주하지 못한선수(Level 1)

문제 설명

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

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

 

제한사항

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

 

 

 

 

 

두가지 방법으로 해결을 하였다.

 

첫번째는 해시맵을 사용하지 않고 자바에서 지원하는 배열의 정렬을 이용해서 쉽게해결했지만, 해시맵을 사용해서 풀어 보고 싶어서 더 고민해보았다.

 

 

public static String solution(String[] participant, String[] completion) {
		Arrays.sort(participant);// 오름차순정렬
		Arrays.sort(completion);// 오름차순정렬
		String result = "";
		for (int i = 0; i < completion.length; i++) {// 완주자 길이만큼 반복
			if (completion[i].equals(participant[i])) {

			} else {// 정렬되었기때문에 두배열의 같은 인덱스에 다른값이 있으면 완주하지 못한 사람임
				result = participant[i];
				break;
			}
		}
		if (result.equals("")) {
			result = participant[completion.length];
		}
		return result;
	}

 

첫번째 풀이이다.

1. 참가자목록과 완주자목록 두 가지를 Array.sort()함수를 사용해서 자동으로 오름차순 정렬을 시킴

 

2. 완주자 목록의 길이 기준으로 for문을 돌려서 참가자 목록과 각 인덱스를 비교한다.

 

3. 두 배열은 정렬되어있기때문에 같은 인덱스에 다른값이 들어있다면 참가자쪽에 완주하지 못한 사람이 있다는 뜻.

 

4. 반복문이 끝날때까지 result가 비었다면 참가자 목록의 가장 마지막 사람이 완주하지 못한 사람임

 

 

 

public static String solution(String[] participant, String[] completion) {
	     String result = "";
		 HashMap<String, Integer> completionHm = new HashMap<String, Integer>();//해시맵선언
		 for(int i =0; i< completion.length; i++) {//완주자를 모두 해시맵에 넣어놓음
			 int count = completionHm.getOrDefault(completion[i], 0);//동명이인 카운트, 해시맵에 완주자가 등록되어있지 않으면 0
			 completionHm.put(completion[i], count+1);//처음등록이면 1 두번째등록이면 2 이렇게 중복체크를해줌
		 }
		 
		 for(int i =0; i < participant.length; i++) {//참가자 길이만큼 반복
			 if(completionHm.getOrDefault(participant[i], 0)== 0) {//완주자목록에 없으면 0을반환하고 그즉시 리턴
				 result = participant[i];
				 return result;
			 }else {//완주자목록에 있을시 동명이인 카운트를 하나씩 줄여가며 다시 put해줌(덮어쓰기)
				 completionHm.put(participant[i], completionHm.get(participant[i])-1);
			 }
		 } 
		 
		 return result;
	 }

 

해시맵을 사용한 두번째 풀이이다.

 

1. 해시맵을 선언하고 첫번째 for문에서 모든 완주자를 해시맵에 등록하는데 이때 동명이인의 중복확인을 위해서 value값을 동명이인 카운트로 사용한다.//key에 그 이름이 들어간게 처음이면 1 아니면 value+1

 

2. 두번째 포문에서 참가자목록의 길이를 기준으로 for문을 돌림 여기서 두가지 분기점으로 나뉨

 

3. 참가자이름을 key값으로 value를 받아와서 그것이 0이 아니라면 value-1해서 다시 덮어씌움

 

4. value가 0이라면 그 이름을 가진 사람이 완주하지 못했다는 의미이기때문에 return