알고리즘 6편 Hash 로 2개 배열 중복값 찾고 지우기 코틀린(kotlin) 으로 시작하는 문제해결방법

안녕하세요

앵과장입니다.

 

2021년 그것도 9월이네요

벌써 내 나이 40대 초반도 지나가고 있네요

 

오늘은 연휴 시작 토요일입니다. 

다들 즐거운 한가위 추석 되시고 놀지 말고 공부하세요

 

알고리즘 문제는 다양한 곳에서 찾아서 배울 수 있으니 시간 날 때마다 풀어보시기 바랍니다.

 

Hash

hash에 대한 문제를 풀기 전에 우선 우리가 소스에서도 많이 봐왔던 Hash에 대해서 가볍게 알고 넘어가도록 하겠습니다.

 

hash 많이 쓰잖아요?

 

HashMap

HashSet

HashTable
HashArray

 

Hash를 그토록 쓰는데 Hash에 대해서 설명을 해봐!?

어.. Hash 요? Key, Value로 이루어진 데이터 정도라고 설명할 수는 있는데 좀 더 이해할 수 있도록 설명 가능한 방법이 있을까요?

또 제가 좋아하는 노매드 코더 니 꼬샘이 유튜브에 설명을 해두셔서 첨부합니다.

https://www.youtube.com/watch?v=HraOg7W3VAM 

https://www.youtube.com/watch?v=S7vni1hdsZE&t=270s 

이분도 설명이 있는데 이분은 제가 좋아하는 스타일이 아니라서 링크만 남겨둡니다.

 

전 친절하고 자상한 니코 선생님이 좋아요

https://www.youtube.com/watch?v=67UwxR3ts2E&t=8s

Hash 관련된 링크가 또 있어서 이것도 걸어둡니다.

이토록 Hash는 중요한 자료구조 중 하나랍니다.

 

해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다. 해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색의 속도를 가속할 수 있다. 예를 들어서, DNA sequence에서 유사한 패턴을 찾는 데 사용될 수도 있다. 또한 암호학에서도 사용될 수 있다. 암호용 해시 함수는 매핑된 해싱 값만을 알아가지고는 원래 입력 값을 알아내기 힘들다는 사실에 의해 사용될 수 있다. 또한 전송된 데이터의 무결성을 확인해주는 데 사용되기도 하는데, 메시지가 누구에게서 온 것인지 입증해주는 HMAC를 구성하는 블록으로 사용된다. 해시 함수는 결정론적으로 작동해야 하며, 따라서 두 해시 값이 다르다면 그 해시값에 대한 원래 데이터도 달라야 한다. (역은 성립하지 않는다) 해시 함수의 질은 입력 영역에서의 해시 충돌 확률로 결정되는데, 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가하게 된다.

해시함수중에는 암호학적 해시함수(Cryptographic Hash Function)와 비암호학적 해시함수로 구분되곤 한다.

암호학적 해시함수의 종류로는 MD5, SHA계열 해시함수가 있으며 비암호학적 해시함수로는 CRC32등이 있다.

암호학적 해시함수는 역상(pre-image), 제2역상(2nd preimage), 충돌쌍(collision)에 대하여 안전성을 가져야 하며 인증에 이용된다 . 암호학적 해시함수는 임의의 길이를 입력 받기는 하지만 MD Strength Padding할 때 길이정보가 입력되므로 최대 길이에 대한 제한이 있다. 예를 들어 패딩시 하위 8비트에 길이정보가 입력 되는 경우에는 해시가능한 최대 길이는 0xFF가 되어 255바이트가 된다.(실제 길이정보는 패딩방식에 따라 다를 수 있다)

제일 중요한 포인트는 Key, Value라는 점 잊지 마세요

 

오늘의문제
출처 : 프로그래머스 샘플예제

package com.programmers.problem

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
 */
class Hash01 {
    fun solution(a: List<String>,b: List<String>): String {
        var aa = a.toMutableList()
        var bb = b.toMutableList()

        val iterator = a.iterator()
        while(iterator.hasNext()) {
            var n = iterator.next()
            if(n in bb) {
                aa.remove(n)
                bb.remove(n)
            }
        }
        return aa[0]
    }
}

방법은 다양합니다.

이 방법이 소스 레벨도 짧고 간결합니다. 이해도 빠르고 하지만 

Hash를 이용하기로 했으니 Hash로 풀어보도록 하겠습니다.

 

 fun solution(a: List<String>,b: List<String>): String {
        var answer = "";
        val map = HashMap<String, Int>()

        for (player in a) {
            map.put(player,map.getOrDefault(player,0)+1)
        }

        for (player in b) {
            map.put(player,map.get(player)!! -1)
        }

        for (key in map.keys) {
            if(map.get(key)!=0){
                answer = key
            }
        }
        return answer;
    }

첫 번째 a 배열을 생성한 Map에 담도록 합니다.

value는 
map.getOrDefault(player,0)+1 

이렇게 사용했는데 

 

getOrDefault 

매개 변수 : 이 메서드는 두 개의 매개 변수를 허용합니다.

• key : 값을 가져와야 하는 요소의 키입니다.
• defaultValue : 지정된 키로 매핑된 값이 없는 경우 반환되어야 하는 기본값입니다.

반환 값 : 찾는 key가 존재하면 해당 key에 매핑되어 있는 값을 반환하고, 그렇지 않으면 디폴트 값이 반환됩니다.

 

map.get(player)!!

a == b 같다면 이라는 거와 동일합니다.

 

사용한 이유는 동명 2인인 경우 value 를 1이 아닌 +1증가된 2로 들어가야 아래에서 동명2인일경우 1명을 반환할수 있기 때문입니다.

 

두 번째 배열에서는 

선수, 1 또는 선수, 2 로들아건 Map에서 -1을 해서 1이 남아있는 사람만 리털 할 수 있도록 만들어줍니다.

 

어때요 간단하죠!!

하나씩 풀어간다면 여러분도 쉽고 재미있게 이해할 수 있습니다.

 

추석 연휴 잘 보내시고 항상 즐거운 코딩 생활하세요


알고리즘 7편 클릭클릭

알고리즘 7편 Hash 난이도2 key value 위장 의상경우의수 코틀린(kotlin) 으로 시작하는 문제해결방법