알고리즘 문제풀이 [#1] 완주하지 못한 선수

이미 해답지가 인터넷에 다 있어 저도 올리지만,

이미 다 풀어주신 분만 밑으로 봐주시길 바랍니다.

 

문제 설명 이후에 답안 나옵니당.

 

지인과 알고리즘 같이 풀어보기로 했는데..

이번에 나도 한 문제 풀어보았다. 

(아 주말에 더 풀어볼걸 그랬나 싶은;;)

 

=================================

 

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다

 

문제는 이곳에서 보실 수 있다. 

programmers.co.kr/learn/courses/30/lessons/42576?language=java

코딩테스트 연습 - 완주하지 못한 선수

 

밑으로 해답 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

enum Action {
        UP(1), DOWN(-1);
        Integer number;
        Action(Integer num) {
            this.number = num;
        }
    }

    void handleMap(Map<String, Integer> result, String key, Action action) {
        Integer value = result.get(key);
        if (value == null) {
            result.put(key, action.number);
            return;
        }
        Integer processed = value + action.number;
        if (processed == 0) {
            result.remove(key);
        } else {
            result.put(key, processed);
        }
    }

    @Override
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> result = new HashMap<>();
        for (int i = 0; i < participant.length; i++) {
            handleMap(result, participant[i], Action.UP);
            if (i < participant.length - 1)
                handleMap(result, completion[i], Action.DOWN);
        }
        return result.keySet().iterator().next();
    }

( 사실 자기전에 코딩하다가 result 에서 다시 포문 열어서 첫번째값 돌렸는데 이터레이터가 있었지..;;  마지막 한줄은 남의 코드보고 고쳤다 ㅋㅋ )

 

근데 뭐 풀면 어떻게든 풀긴하는데..

맨 처음에 그냥 생각나는 list remove 형태는 효율성이 하나도 안나와서 고민하다가 

그냥 오기로 빨리 풀어버림 ( ;ㅅ; )

흠 머리가 굳긴했나 싶기도하고.. 

 

 

 

제일 따봉 많이 받은 정답이랑 비교해봤는데.. 비슷한 코드같다. 

 

public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }

 

개인적으로 재미있었던 코드 

 

알고리즘 테스트는 구식문법으로 돌려야 제맛이지라는 생각이었는데 현대적이다. 효율성도 100점

public String solution(String[] participant, String[] completion) {
        Map<String, Long> participantMap = Arrays.asList(participant).stream()
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        for(String name : completion) {

            Long value = participantMap.get(name) - 1L;

            if(value == 0L) {
                participantMap.remove(name);
            } else {
                participantMap.put(name, value);
            }
        }

        return participantMap.keySet().iterator().next();
    }

 

끝으로 이건... 나중에 뭐하는 건지 좀 봐야겠다;; 

 

public class Solution {

    int bucketSize;
    List<Entry>[] bucket;

    public String solution(String[] participant, String[] completion) {
        bucketSize = (completion.length / 5)+1;
        bucket = new List[bucketSize];

        for (int i = 0; i < completion.length; i++) {
            Entry entry = get(completion[i]);
            entry.value += 1;
        }

        for (int i = 0; i < participant.length; i++) {
            Entry entry = get(participant[i]);
            if (entry != null && entry.value > 0) {
                entry.value -= 1;
            } else {
                return entry.key;
            }
        }
        throw new RuntimeException("error");
    }

    private Entry get(String s) {
        int idx = hash(s);
        List<Entry> list = bucket[idx];
        if (list == null) {
            list = new List<Entry>();
            Entry entry = new Entry(s, 0);
            list.add(entry);
            bucket[idx] = list;
            return entry;
        } else {
            Entry entry = list.get(s);
            if (entry == null) {
                entry = new Entry(s, 0);
                list.add(entry);
            }
            return entry;
        }
    }


    private int hash(String s) {
        int num = 0;
        for(int i=0; i<s.length(); i++) {
            num += s.codePointAt(i) * 31 + s.codePointAt(i);
        }
        return num % bucketSize;
    }

    class Entry {
        String key;
        int value;

        public Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    class List<T extends Entry> {
        Node head;

        public void add(T entry) {
            Node nn = new Node(entry, null);

            if (head == null) {
                head = nn;
            } else {
                Node last = head;
                while (last.next != null) {
                    last = last.next;
                }
                last.next = nn;
            }
        }

        public <T extends Entry> T get(String s) {
            Node node = head;
            while (node != null) {
                if (node.data.key.equals(s)) {
                    return (T) node.data;
                }
                node = node.next;
            }

            return null;
        }

        class Node<T extends Entry> {
            T data;
            Node next;

            public Node(T data, Node next) {
                this.data = data;
                this.next = next;
            }
        }
    }

    public static void main(String[] args) {
        String[] p = {"mislav", "stanko", "mislav", "ana"};
        String[] c = {"stanko", "ana", "mislav"};
        Solution s = new Solution();
        String answer = s.solution(p, c);
        System.out.println(answer);
    }

}

======

세상에 나쁜 코드는 없다.

친절히 코드로 이야기하려합니다 by 아라한사