#4알고리즘 연습- 완주하지 못한 선수/JAVA|벽에그린나의키

2019년 1월 12일 토요일

#4알고리즘 연습- 완주하지 못한 선수/JAVA

완주하지 못한 선수

문제 설명

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

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

제한사항

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

입출력 예

participant	completion	return
[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는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

출처

문제풀이 IDEA

해당 문제가 HASH를 이용한 문제라서 HASH를 쓰려고 했지만 이 문제가 처음으로 푸는 알고리즘 문제였고 hash를 사용하고 for문으로 remove를 통해 답을 구하려했었는데
remove의 시간복잡도가 O(n)이고 for문도 O(n)이므로 전체 시간 복잡도가 O(n^2)만큼 되어버려서 효율성 부분에서 문제가 생겼다

SORT를 이용해 문제 풀기
참가자와 완주자의 배열은 유사하므로 이를 정렬하게 되면

1. 배열의 시작과 중간에 포기자가 있는 경우 -- 참가자와 완주자의 이름이 다를것

예시 ) 참가자 [a,a,a,b,c] 완주자 [a,a,b,c] 일경우 index순서대로 비교해 나가다가
참가자의 두번째 index는 a인데 완주자의 두번째 index는 b이므로
참가자의 두번째 index a를 포기자로 출력해주면 된다

2. 배열의 마지막에 포기자가 있는경우 -- 참가자 배열의 마지막사람을 포기자로 출력

예시) 참가자 [a,b,c,d,e] 완주자[a,b,c,d] 이렇게 되면 a,b,c,d까지는 참가자와 완주자가
같은데 참가자 e같은 경우에는 비교할 완주자가 없기때문에 비교는 불가하다
하지만 앞서 모든 사람이 완주했는데 완주자 명단에 e가 없다는 것은 포기자이니
참가자의 마지막 원소를 출력해주면 된다

나의 풀이⭐

import java.util.*; 

class Solution {
    public String solution(String[] participant, String[] completion) {
         String answer = "";
        Arrays.sort(participant);    //참가자의 명단을 알파벳순으로 정렬
        Arrays.sort(completion);     //완주자의 명단을 알파벳순으로 정렬

        for (int i = 0 ; i< participant.length; i++){     //참가자의 모든 원소가 포기자가될수있으므로

                                                            for문의 length의 기준은 참가자가 된다
            if (i < participant.length - 1 ){             //참가자가 완주자보다 길이가 1길어서 마지막 원소는 비교대상이 없다

                                     ㅇㅁㄻㄴㅇㄹ           따라서 참가자 마지막 원소 전까지 비교를 해주어 bound exception을 방지

                        if(!(participant[i].equals(completion[i]))){ //참가자와 완주자의 이름이 다르면 if문 실행 (String 비교는 equals로)
                        answer = participant[i];                     //만약 다르다면 답은 지금 index의 참가자
       
                        break;                                       //만약 포기자를 색출했다면 반복문을 빠져나와 return해주면 된다

                    }                                                  break는 break를 둘러싸고있는 반복문을 탈출하는 애이다

            }
            else{                                                    //만약 참가자 배열의 끝-1까지 완주자와 동일하면

                  answer = participant[i];                             참가자의 마지막 원소가 포기자 따라서 답으로 넣어주고

                     break;                                            굳이 break를 안써도 마지막 원소이므로 for문이 끝나서 answer에는 변화가 없다
            }                                                          

        }
        return answer;
    }
}

HashMap풀이⭐

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>(); //String을 key값으로 Integer을 value값으로 하는 Hashmap hm 생성
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);

                                        //   참가자배열의 원소 하나하나 player로 가져와서

ㄹ                                           hm에 put(넣어주는데) 참가자이름이 key값이 되고 해당이름 사람수 value값이 되는데

                                             hm에서 참가자이름에 해당하는 value가 있으면 그 값을, 아니라면 default값으로 0을 가져와

                                             hm해쉬맵에 value값으로 넣어준다 즉 처음 해쉬맵은 null값이므로 0을 가져오고 1을 count해주는데

                                             그 이후부터는 해쉬맵에서 참가자 이름에 해당되는 해당이름 사람수(예를들면 1명) 을 가져오고 +1을 하여 증가시켜

                                             업데이트 시켜준다

for (String player : completion) hm.put(player, hm.get(player) - 1);
                                            // 완주자배열에서 이름을 가져와 그 이름(key)에 해당되는 value를 찾아와 완주를 했다는 의미에서 -1씩

                                               해서 다시 hashmap에 넣어준다
        for (String key : hm.keySet()) {     //해쉬맵의 key모음에서 key를 가져와 반복문 실행
            if (hm.get(key) != 0){           //그리고 key값으로 value(참가자 수)를 하나하나 검사하는데
                answer = key;                  완주를 했으면 참가자 - 완주자 = 0이 되어야 하는데 0이 아니라는것은
             }                                 해당이름이 포기했다는 것이므로 answer에 대입
        }
        return answer;
    }
}

눈여겨 볼만한 개념들

a.equals(b)

==을 안쓰고 equals를 쓰는 이유는 우리가 비교하고자 하는
String의 경우 참조 변수이고 ==을 쓰게 되면 참조하는 객체가 같은가를 비교하는 반면
equals를 쓰게되면 참조하고 있는 객체의 내용이 같은가를 비교해주는 메서드 이므로
equals를 사용해준다
(int와 같은 primitive type의 경우 ==로 비교)

Arrays.sort

JAVA의 arrays.sort메서드를 살펴보면 입력 값에따라 정렬 방법에 차이가 있는데
primitive type의 경우 dual-pivot-quicksort 를 사용해서 O(nlogn)의 성능을 가진다

non- primitive type의 경우에는 TimSort를 쓰는데
이는 merge sort와 insertion sort를 혼합해서 사용하는 것이다 최악의 경우 O(nlogn)의 성능

출처

HashMap

Map interface의 한 종류로 (key,value)로 이루어져있다
hashing을 사용하기때문에 많은양의 데이터를 검색하는데 뛰어난 성능을 보인다.
key값은 중복이 불가능하고 value에 null값도 사용가능하다

자바 멀티쓰레드를 쓸때는 hashTable을 사용한다
hashmap을 사용하면 문제가 될 수 있다.

hashmap 메소드 보러가기

HashMap에 대해 더 알아보기 <--해쉬함수의 구조와 충돌시에 대한 설명있습니다

출처:프로그래머스(https://programmers.co.kr)

벽에그린나의키

2019년 1월 12일 토요일