[알고리즘] 완주하지 못한 선수

자료구조와 알고리즘을 공부하기 위해서 프로그래머스에서 문제를 풀기 시작했다. 많은 개발자들이 '매일 한문제씩 꼭 풀어야지!'라는 생각을 할 것이다. 나도 예전부터 그런 생각이 들었고 실행에 옮기게 되었다.

자바와 파이썬으로 둘다 시도했다.

1. 실패한 java code

   import java.util.*;
   class Solution {
     public String solution(String[] participant, String[] completion) {
            List<String> p = new ArrayList<>();
    //        List<String> p = new ArrayList<>(Arrays.asList(participant));
    //        List<String> c = new ArrayList<>(Arrays.asList(completion));
            List<String> c = new ArrayList<>();
            for (String s : participant) {
                p.add(s);
            }
            for (String s : completion) {
                c.add(s);
            }
   
            p.removeAll(c);
   
            return p.get(0);
        }
      }

• removeAll을 쓰면 중복된것까지모두 제거되어 버린다.

2. 수정한 java code

   import java.util.*;
   class Solution {
     public String solution(String[] participant, String[] completion) {
   	
       // 참가자
       List<String> p = new ArrayList<>();
       // 완주자
         List<String> c = new ArrayList<>();
       // 동명이인을 확인할 수 있도록 map을 만든다.
       // key는 참가자 이름, value는 같은 이름인 사람의 숫자
         Map<String,Integer> count = new HashMap<>();
         // map에 사람이 있으면 value에 1을 더하고
         // map에 사람이 없으면 새롭게 추가한다. 이때 value는 1이다.
         for (String s : participant) {
             if(count.containsKey(s)) count.put(s,count.get(s)+1);
             else count.put(s,1);
         }
         //완주자자들을 제거할 것이다.
         for (String s : completion) {
         // 완주자 명단에 이름이 있으면 제거한다.
         // 1. map에 한명만 남아있으면 map에서 지운다.
         // 2. map에 여러명이 있으면 value를 1 뺀다.
             if(count.containsKey(s)) {
                 if(count.get(s)==1){
                     count.remove(s);
                 }else if(count.get(s) > 1){
                     count.put(s,count.get(s)-1);
                 }
             }
         }
   	// 반드시 한명만 완주하지 못했으니 map에 남아있는 사람이 완주하지 못한 사람의 이름이다.
         for (String s : count.keySet()) {
             return s;
         }
         return "";
     }
   }

   파이썬

   def solution(participant, completion):
     participant.sort()
     completion.sort()
     n = len(completion)
   
     for i in range(n) :
         if participant[i] != completion[i] : 
         	return participant[idx]
     return participant[n]

• 파이썬은 개발에 입문하기 전에 본적이 있어서 기억을 되살리며 풀었다.

후기

• 다른 사람의 풀이에서 참신한 생각과 메소드들을 보았다. doc파일들을 보면서 유용한 메소드들을 사용하려고 노력해야겠다.