99클럽 코테 스터디 5일차 TIL 완주하지 못한 선수

 

# 오늘의 학습 키워드 

해시

 

# 오늘의 문제 

문제 설명

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

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

 

제한사항

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

 

# 나의 풀이방식 

1. 첫번째 문제풀이 

이중 for문으로 풀었다. 참여선수 배열에서 완주선수 배열과 매칭되는 선수를 지우는 방식으로 코드를 짰다. 정확도는 테스트케이스에서 모두 성공이었는데 효율성에서는 시간초과로 전부 실패였다. sort를 적용해서 했더니 효율성 테스트케이스에서 몇개는 성공이 뜨긴 했는데 성능 개선을 더이상 할수 없더라... 후우...  

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
       List<String> list = new ArrayList(Arrays.asList(completion));
        int partLength = participant.length;
       
    for(int i=0; i<partLength; i++){
       
        String person = participant[i];
        Boolean result = false;
        int length = list.size();
        
        for(int j = 0; j<length; j++){
            
            String winner = list.get(j);
           if(person.equals(winner )){
               list.remove(j);
               result = true;
               break;
           }
        }
        
        if(result == false){
            answer = person;
            break;
        }
    }
    
        return answer;
    }
}

 

 

2. 두번째 문제풀이 

이번에는 정렬 후 배열 비교로 진행했고 드디어 전체 효율성 테스트케이스에서 성공이 떴다. 

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        // 효율성 개선방법
        // 1.정렬
        Arrays.sort(completion);
        Arrays.sort(participant);
       
        int i;
        
        // 2. 2중 for문 대신 배열 비교
        for(i=0; i<completion.length; i++){
 
            if(!completion[i].equals(participant[i])){
             return participant[i];   
            }
        }
       
        return participant[i];
    }
}

 

# 오늘의 회고 

잊지말자 시간복잡도!

알고리즘 문제를 풀면서 정확도만 생각했지 효율성까지 생각하지 못했는데

오늘 문제를 풀면서 시간복잡도를 고려해야겠다는 생각이 들었다.