[알고리즘] 프로그래머스 | 완주하지 못한 선수, 과일 장수

완주하지 못한 선수

#해시

 

답: 

# 해시로 풀이하기 key값에 hash값 넣어주기
def solution(participant, completion):
    answer = ''
    temp = 0
    parti_dic = {}
    for p in participant:
        parti_dic[hash(p)] = p
        temp += int(hash(p))
    for c in completion:
        temp -= hash(c)
    answer = parti_dic[temp]

    return answer

 

 

 

***

hashMap은 보통 value 값에 숫자를 넣고 key값에는 string을 넣어주므로
value에 hash를 넣는 방식으로 수정해보았다.

#해시로 풀이하기  value에 해시값 넣어주기
def solution(participant, completion):
    answer = ''
    temp = 0
    parti_dic = {}
    for p in participant:
        parti_dic[p] = hash(p)
        temp += int(hash(p))
        # print(parti_dic[p])
    for c in completion:
        temp -= hash(c)
    answer = [key for key, value in parti_dic.items() if value == temp]

    return answer[0]

 

key값에 hash를 넣는것과 같은 방식이지만, python에서는 value값으로 Key값을 따로 찾는 방법이 없으므로
for문 혹은 key, value값을 reversed한 dictionary를 사용해야한다고 한다..  

그래스 .items와 if문으로 answer를 찾도록 하였음!

 

 

 

문제 분석 및 해석

 

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주
참여한 선수들의 이름이 담긴 배열 participant, 
완주한 선수들의 이름이 담긴 배열 completion
완주하지 못한 선수의 이름을 return

 

>> 풀이생각

completion완주 선수 문자열로 출전 선수 명단을 검사하여 없는 1명을 찾아내기 

 

 

 

 

과정1.

for문과 if문으로 검사, remove를 하는 방식으로 진행

 

def solution(participant, completion):
    answer = ''
    for person in completion:
        if person in participant:
            participant.remove(person)
    return participant[0]

 

정확성 검사는 통과했지만 시간유효성 검사를 모두 실패하였음.

 

어떻게 시간을 줄일 수 있을까?

for문과 remove를 안쓰고 풀이할 수 있는 방법이 있을까?

 

 

*** 해시 문제였다!

해시는 앞 글자부터 검사하여 맞는 것을 확인하는 방식임

 

HashMap 만들기

HashMap이란 Key-Value의 Pair로 데이터를 관리하는 방식. 

보통 Key는 String 형태, Value는 Integer 형태로 정의한다.

 

 

 

 

해시맵으로 풀이한 과정2.

 

1) 해싱을 통해 해시맵(dict형태)으로 만들기

 

Key는 참가 선수에 각각에 대한 hash() 번호를 부여하고,

Value를 참가 선수 Participant들의 이름으로 한다

 

temp에 hash한 수를 함께 더해놓아 이후 계산을 편리하게 한다

 

def solution(participant, completion):
    answer = ''
    temp = 0
    parti_dic = {}
    for p in participant:
        parti_dic[hash(p)] = p
        temp += int(hash(p))
    # print(temp)
    # print(parti_dic) 
    # -304541699303906125
    # {2741692151764039179: 'leo', 3389273533360313803: 'kiki', -6435507384428259107: 'eden'}

 

temp에 hash한 수를 함께 더해놓아 이후 계산을 편리하게 한다.

 

 

 

2) 완주한 사람들을 해싱하면서 temp에서 빼준다

 

for c in completion:
    temp -= hash(c)

 

 

3) 남아있는 수가 key가 되어 value 값을 찾을 수 있게 된다

 

answer = parti_dic[temp]

 

 

 

> 리뷰 : 여전히 어려운 해시맵... 공부하면서 익숙해지자!

 

 

---

과일 장수

답: 

이번 풀이

def solution(k, m, score):
    apple_box = []
    answer = 0
    # score를 내림차순으로 정렬
    score = sorted(score, reverse=True)
    # m개씩 잘라 배열에 담기
    for i in range(0, len(score), m):
        apple_box.append(score[i:i+m])
    # 자른 배열의 길이 확인
    # 배열의 가장 낮은 값을 확인 / min() or [-1]
    for i in range(len(apple_box)):
        if len(apple_box[i]) == m:
            # 해당 값과 상자 속 사과 개수(m)를 곱하고 금액을 더해 return
            answer += apple_box[i][-1] * m
            
    return answer

 

 

같은 방식을 문자열로 풀어보기  *** 단점 : 시간이 엄청엄청 오래걸렸다

# 뻘짓 : 문자열로 풀어볼까?
def solution(k, m, score):
    apple_box = []
    answer = 0
    # score를 내림차순으로 정렬하고 문자열로 만들기
    score = sorted(score, reverse=True)
    apples = ''.join(str(s) for s in score)  # "3322111"
    # 앞에서부터 m개만큼 자르면서 [-1]에 m을 곱하고 더해주기
    while m <= len(apples):
        a = apples[:m]
        answer += int(a[-1]) * m
        apples = apples[m:]
    return answer

 

 

 

 

이전에 풀이한 적이 있어 풀이 기록

def solution(k, m, score):
    result = []
    answer = 0
    score.sort(reverse=True)
    for i in range(0,len(score),m):
        if len(score[i:i+m]) == m :  
           result.append(score[i:i+m])    
    for idx,value in enumerate(result):
        answer += result[idx][-1] * m
    return answer

 

 

문제 분석 및 해석

 

사과는 상태에 따라 1~k점, k점이 최상품 1점은 최하품

한 상자에 사과를 m개 담고,
해당 상자에서 가장 낮은 가격의 점수를 상자의 사과 개수와 곱한 것이 해당 상자의 가격 
과일 장수가 얻을 수 있는 최대 이익을 구하시오 (**남는 사과는 버림)

 

 

>> 풀이생각

score를 내림차순으로 정렬
m개씩 잘라 배열?문자열?에 담기
자른 배열의 가장 낮은 값을 확인 / min() or [-1]
해당 값과 상자 속 사과 개수(m)를 곱하고 
금액을 더해 return

 

 

리뷰.

어느시점이든 상자의 사과의 개수가 맞는지 확인!

문자열로 풀이해본 것도 새로웠다