[프로그래머스] 해시 1단계 : 완주하지 못한 선수 (JAVA)

문제 설명

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

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

제한사항

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

입출력 예

participantcompletionreturn

["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

풀이과정 👀

시도한 방법
1. 배열을 정렬한다. (Arrays.sort메소드)
2. 해쉬맵 객체를 만들고 participant 데이터를 넣는다.
3. participant에서 completion과 비교하여 중복이면 삭제한다.

 

- 하지만 과도한 for문과 remove 사용은 코드 효율성이 낮은 결과를 보임.

- 코드의 효율성을 높이기 위해 시간복잡도에 대한 고민이 필요함.

 

시간복잡도 줄이는 방법

1. sort를 먼저 사용하고 for문을 1번 사용한다.
2. remove를 사용하지 않는다.

 

• 예외 상황에 대해 생각해보기  <- 결정적이였음.

- 동명이인이 참가자명단 중간에 있을떄 
participant : [ana, mislav, mislav, stanko]
completion : [ana, mislav, stanko]

- 동명이인이 참가자명단 앞에 있을떄 
participant : [ana, ana, mislav, stanko]
completion : [ana, mislav, stanko]

- 동명이인이 참가자명단 마지막에 있을떄 
participant : [ana, mislav, stanko, stanko]
completion : [ana, mislav, stanko]

- 동명이인이 모두 완주했을 떄
participant : [ana, mislav, stanko, stanko]
completion : [ana, stanko, stanko]

 

규칙성이 발견됨!!
-> participant이 completion과 다를 때 다른값이 정답이라는 것을 확인

 

해결방법!!
1. participant와 completion을 sort를 사용하여 정렬

2. completion 길이만큼 participant와 completion를 비교할 때
participant이 completion이 다르면 participant[i] 리턴

3. completion의 길이만큼 서로 비교해도 다른값이 없으면
participant 마지막값 리턴

 

public static String solution(String[] participant, String[] completion) {
                
        // 1. 두 배열을 정렬한다. 
        Arrays.sort(participant);
        Arrays.sort(completion);
            
        // 2. 해쉬맵 객체 생성
        Map<Integer, String> map = new HashMap<>();
		
        // 3. 해쉬맵에 데이터 넣기
        
        // 1) completion이 participant보다 1 작으므로 
        //    completion길이 만큼 i의 값 설정
        // 2) map에 participant의 데이터를 넣는다.
        
        String answer = null;
        for(int i = 0; i < completion.length; i++) {
            map.put(i, participant[i]); 
            
            // 3) 만일 map의 i(participant) 값과 
            //    completion[i]이 같지 않으면 <- 둘이 같은 인덱스
            // 4) map의 i값을 answer에 집어넣고 리턴
            
            if(!(map.get(i).equals(completion[i]))){
                answer = map.get(i);
                return answer;
            } 
        }
        
        5) participant의 i값과 completion[i] 값이 모두 같으면  
           participant의 마지막 인덱스값을 리턴한다.
        answer = participant[participant.length - 1];
        return answer;
    }
}