[Programmers]완주하지 못한 선수(JAVA)-Level 1

< 문제 설명 >

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

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

---

< 제한 조건 >

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

---

< 코드 및 풀이 >

*Programmers에서도 정확성 테스트 통과, eclipes에서 결과를 출력한 코드

1. 단 한 사람만 완주 하지 못했다는 점을 생각하면 문제는 쉬어진다. 배열을 오름차 순으로 정리한 후 idx의 값이

같지 않다면 완주한 사람에 해당되지 않으니 완주하지 못한 사람이다. 또한 completion 배열을 다 비교해도 완주하지 못한

사람이 없다면 마지막사람인 것도 생각해 for문을 다나가면 cnt 된 i번째를 불러오면된다.

 

package codingtest;
import java.util.*;

public class Playersnotcomplete {
    public static String solution(String[] participant, String[] completion) {
    	Arrays.sort(participant);
    	Arrays.sort(completion);
    	String answer;
    	int i;
    	for(i=0; i<completion.length;i++) {
    		if(!participant[i].equals(completion[i])) {//i번째 요소가 같다면
    			answer = participant[i];
    		}
    	}
    	answer = participant[i];
    	return answer;
    }
	public static void main(String[] args) {
			String[] participant = {"leo", "kiki", "eden"};
			String[] completion = {"eden", "kiki"};
			System.out.println("전체 선수는 "+Arrays.toString(participant)+"가 있고 완주한 선수는"+Arrays.toString(completion)+"입니다.");
			System.out.println("완주하지 못한 선수는 "+solution(participant, completion)+"입니다.");
	}
}

2.  hash를 이용하면 다양한 길이를 가진 데이터를 고정된 길이로 매핑해 비교해 찾을 수 있다. 또한 내부적으로 배열을 사용해 데이터가 저장되 검색 속도가 빨라 만약 참가자가 많아진다면 hash를 이용하는 것이 더 효율적으로 찾을 수 있다. 이점을 고려해 name이라는 새로운 hash를 만들어 모든 참가자의 이름에 key값을 +1해주고 완주한 사람의 이름엔 다시

키값에 -1을 해 결론적으로 완주하지 못한 사람은 key값을 0을 가지게 하는 형식으로 구성했다.

package codingtest;
import java.util.*;

public class Playersnotcomplete {
    public static String solution(String[] participant, String[] completion) {
    	String answer="";
    	HashMap<String,Integer> name = new HashMap<>(); //해시 만들기
    	for(String a:participant)name.put(a, name.getOrDefault(a, 0)+1);//name 해시에 다 키값 +1
    	for(String a:completion)name.put(a, name.get(a)-1);//만약 완주했으면 키값에 -1
    	for(String key:name.keySet()) {
    		if(name.get(key)!=0) { //즉 완주한 name은 1-1=0이되니 0이 아니면 완주 못한 이름
    			answer = key;
    		}
    	}
    	return answer;
    }
	public static void main(String[] args) {
			String[] participant = {"leo", "kiki", "eden"};
			String[] completion = {"eden", "kiki"};
			System.out.println("전체 선수는 "+Arrays.toString(participant)+"가 있고 완주한 선수는"+Arrays.toString(completion)+"입니다.");
			System.out.println("완주하지 못한 선수는 "+solution(participant, completion)+"입니다.");
	}
}

<실행 화면>

---

<알게 된 사실 & 중요한 점>

sort 함수를 통해 정렬 후 구해내는 첫 번째 알고리즘을 통해 쉽게 해결했다. 하지만 만약에 전체 선수들이 너무 많은 경우 첫 번째 알고리즘은 효율성이 너무 떨어지겠다 싶어서 다른 사람의 코드들을 보며 공부를 하다 hash라는 개념을 알게 되 데이터 접근 속도가 빠른 hash로 코드를 구현해 보았다. hash 자체를 처음 접해서 개념과 문법을 잡기 위해 조금 더 공부 했다. 그 결과 1번 보다 더 효율적인 코드를 구현할 수 있었다.

---

1. .sort 메소드 = 배열의 오름차순 정렬

2. .equals 메소드 = 비교하고자 하는 대상의 내용자체를 비교, 동일하면 참

 

3. for( a : b) -> b의 객체를 차례대로 꺼내 a에 집어 넣는다.

 

4. Hash 

   다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값

   특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.

   내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색속도를 갖는다.

   특정 데이터가 저장되는 인덱스를 그 데이터만의 고유한 위치로 정하여서 데이터 추가/삭제시

   데이터의 이동이 없도록 만들어진 구조

   문법

    - HashMap<타입,타입> 변수 이름 = new HashMap<타입,타입>();//HashMap생성

    - 변수 이름.put(key,value); -> hash에 추가, HashMap에 설정해준 타입과 같은 타입의 Key와 Value값을 넣어야 하며 만      약 입력되는 키 값이 HashMap 내부에 존재한다면 기존의 값은 새로 입력되는 값으로 대치

    - getOrDefault(Object key, V DefaultValue) -  찾는 키가 존재하면 찾는 키 값을 반환, 없다면 기본 값을 반환하는 메서드

    - entrySet(), keySet() -> map 전체 값 출력

       ->entrySet() 메서드는 key와 value의 값이 모두 필요할 때 사용하고, keySet() 메서드는 key의 값만 필요한 경우 사용