출처 : 프로그래머스

문제는 여기에

문제

• 그리워하는 사람의 이름이 담긴 배열 name 이 주어진다
• 각 사람별 그리움 점수가 담긴 배열 yearning 이 주어진다.
• 각 사진에 찍힌 인물의 이름을 담은 이차원 문자열 배열 photo 가 주어진다.
• 사진 속에 나오는 인물의 그리움 점수를 모두 합산한 값이 해당 사진의 추억 점수가 된다.
• 사진들의 추억 점수를 photo 에 주어진 순서대로 배열에 담아 return 하는 solution 함수를 완성해라

제한사항

입출력 예

접근

1. name에 나온 사람의 추억점수가 yearning에 순서대로 입력되어 있으니 for문과 딕셔너리를 이용해서 이름:점수 로 만들어야겠다.
2. for문을 돌며 photo에 있는 사람들이 딕셔너리의 키의 값에 존재한다면, 그 키에 해당하는 값을 answer에 추가해야겠다.

코드

def solution(name, yearning, photo):
    dic = {}
    answer = [0 for i in range(len(photo))]
    
    for i in range(len(name)):
        dic[name[i]] = yearning[i]
        
    for i in range(len(photo)):
        for j in range(len(photo[i])):
            if photo[i][j] in dic.keys():
                answer[i] += dic[photo[i][j]]
            else:
                continue
    return answer

고찰

우선 불필요한 코드가 있는 것 같다.

1. 리스트를 0으로 초기화를 해야 할 필요가 있을까?    <= 초기 코드 작성할 때, append를 사용해보니 인덱스 오류가 나서 바꾼 것이다.

2. 이중 배열을 for문 돌때, photo[i][j]와 같이 하지 않아도 된다.

    첫 for문에서 리스트 형식으로 반복하고, 두 번째 for문에서 리스트 내의 원소를 반복하면 된다.

3. 접근 (1)에서 사람의 이름과 점수가 순서대로 입력되어 있으니 사전을 만들지 않아도 된다. 인덱스가 같다는 것으로 접근하면 더 쉽다.

수정한 코드

def solution(name,yearning,photo):
    answer = []
    
    for i in photo:
        score = 0
        for j in range(len(name)):
            if name[j] in i:
                score += yearning[j]
        answer.append(score)
    return answer

이렇게 이중 배열인 photo 자체를 반복시키면 i에는 (단일?) 배열이 들어간다. if 문에서도 보면 사진에 있는 사람들이 그리운 사람 명단에 있는지를 보는 것이 아니라 그 반대인 그리운 사람 명단이 그 사진에 들어가 있는지로 기준을 바꾸면 더 쉬워지는 것을 알게 되었다.

배열의 인덱스 순서가 같은 관계가 있어도 딕셔너리를 생각하기보단 같은 인덱스로 접근한다고 생각해보자.

마지막으로 엄청난 사람의 코드 2개를 보고 마무리 하겠다. . .

다른 사람의 코드

def solution(이름, 점수, 사진):
    return [sum(점수[이름.index(j)] for j in i if j in 이름) for i in 사진]

def solution(name, yearning, photo):
    answer = []
    for x in photo:
        answer.append(sum([ yearning[name.index(y)] for y in x if y in name]))
    return answer

def solution(name, yearning, photo):
    score_dict = dict(zip(name,yearning))
    return [sum(map(lambda x: score_dict[x] if x in score_dict else 0,p)) for p in photo]

이렇게 짧게 쓰는 사람들은 평소에 뭐 먹고 지내는지 궁금하다.

dict함수와 zip함수는 추후에 개념 정리를 해야한다고 느꼈다.

출처 : 프로그래머스

문제는 여기에

문제

• 사과는 상태에 따라 1점부터 k점까지의 점수로 분류한다. (k점 = 최상품 사과, 1점 = 최하품 사과)
• 한 상자에 사과를 m개씩 담아 포장한다.
• 상자에 담긴 사과 중 가장 낮은 점수가 p점인 경우, 사과 한 상자의 가격은 p * m 이다. (1<= p<= k)
• 즉, (최저 사과 점수) X (한 상자에 담긴 사과 개수) X (상자의 개수)
• 사과는 상자 단위로만 판매하며, 남는 사과는 버린다.
• 사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score 가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해라

제한사항

• 3 <= k <= 9
• 3 <= m <= 10
• 7 <= score 의 길이 <= 1,000,000
  • 1<= score[i] <= k
• 이익이 발생하지 않는 경우에는 0을 return

입출력 예

접근

1. list 하나를 더 선언하고, score 에서 가장 큰 점수를 list에 추가하고(append), score에서는 삭제하자(remove)

2. list의 원소가 m가 같아질 경우, 이익을 계산

3. 계산 후 (남은 score의 원소의 개수를 m으로 나눈 몫) <= 0 이면 이익을 return한다.

4. (3)에서 나눈 몫이 >= 0 이면, list를 초기화하고, 다시 (1) 반복

= > 시간초과 ㅠㅠ

def solution(k, m, score):
    answer = 0
    list = []
    for i in range(len(score)):
        list.append(max(score))
        score.remove(max(score))
        if len(list) == m:
            answer += min(list) * m
            if (len(score) // m) <= 0:
                return answer
            else: 
                del list[:]

고찰

위의 코드를 작성할 때 새로운 리스트를 하나 더 만들어야하나 싶긴했다.

내가 간과했던 것이 있다면, range의 3번째 인자는 증감을 나타낼 수 있다는 것이다.

원래 주어진 score 를 내림차순으로 정렬하자. (내림차순으로 정렬하면 내려 갈수록(뒤로 갈수록) 작아진다.)

코드

def solution(k, m, score):
    answer = 0
    score = sorted(score, reverse = True)

    for i in range(0, len(score), m):
        tmp = score[i:i+m]

        if len(tmp) == m:
            answer += min(tmp) * m

    return answer

성공이다 ^^

성공하자마자 다른 사람의 풀이를 봤는데

ㅎ.......

다른 사람의 코드

def solution(k, m, score):
    return sum(sorted(score)[len(score)%m::m])*m

아찔하다. . .

문제 출처 : 프로그래머스

문제는 여기에

문제

• 학생들은 각자 정수 번호를 가지고 있다.
• 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 한다.
• 학생들의 번호를 나타내는 정수 번호 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요

제한사항

• 3 <= number 의 길이 <= 13
• -1,000 <= number 의 각 원소 <= 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있습니다.

입출력 예

접근

 처음에는 깊게 생각하지 않고 for문을 세 번 돌리면 모든 경우에 대해 합이 3이 되는지 검사를 할 수 있겠다고 생각을 했다.

그런데 시간 초과가 발생할 것 같아 좀 더 고민해보았는데 다른 방식으로 해결하기에는 어려움이 있어 for 반복문을 세 번 돌리는 코드를 작성했는데 정답이 되었다. :>

def solution(number):
    cnt = 0
    for i in range(len(number)-2):
        for j in range(i+1, len(number)-1):
            for k in range(j+1, len(number)):
                if number[i] + number[j] + number[k] == 0:
                    cnt += 1
    return cnt

고찰

이렇게 무지성으로 for문 돌리는 것은 배울 것이 없어 고등학교 수학시간에 배운 조합(Combination)을 사용하여 문제를 풀어볼 것이다.

조합을 사용하기 위해 itertools 라는 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리의 

Combination 클래스를 사용할 것이다.

def solution(number):
    from itertools import Combination
    cnt = 0
    for i in Combination(number, 3):    # 순서에 상관없이 가능한 모든 3가지 조합을 i에 할당
        if sum(i) == 0:
            cnt += 1
    return cnt

삼총사 문제로부터 코딩테스트에서 사용하면 유용한 itertools 라이브러리의 Combination 클래스 사용 법을 터득했다!

문제 출처 : 프로그래머스

문제는 여기에

문제

• 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부른다.
• 2등인 선수의 이름을 부른다면 그 선수는 1등이 되었다는 것
• 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players 를 매개변수로 준다
• 해설진이 부른 이름을 담은 문자열 배열 callings를 매개변수로 준다.
• 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해라

제한사항

• 5 <= players 의 길이 <= 50,000
• players[i]는 i번째 선수의 이름을 의미합니다.
• players의 원소들은 알파벳 소문자로만 이루어져 있습니다.
• players에는 중복된 값이 들어가 있지 않습니다.
• 3 <= players[i]의 길이 <= 10
• 2 <= callings 의 길이 <= 1,000,000
• callings는 players의 원소들만 이루어져 있습니다.
• 경주 진행중 1등인 선수의 이름은 불리지 않습니다.

입출력 예

접근

처음에 시도 했을 때는 시간 초과로 실패했었다.

1. 불린 선수의 이름이 players의  몇 번째 인덱스에 있는지 조사
2. (1)에서 조사한 인덱스와 바로 전 인덱스와의 교환

풀이

def solution(players, callings):
    
    for i in callings:
        k = players.index(i)
        players[k-1], players[k] = players[k], players[k-1]

    return players

테스트 9 ~ 13에서 시간 초과가 나온다

고찰

위 코드에서 비효율적인 부분은 호명된 선수의 idx 하나를 구하려면 1,000,000 X 50,000 번을 왕복해야한다.

아마 이 부분이 시간 초과의 원인일 것이다.

선수의 인덱스를 어떻게 빨리 찾을 수 있을까? 생각해봤는데 딕셔너리를 이용하면 쉽게 풀 수 있다고 하여 시도해보았다.

접근2

1. {선수:등수}, {등수:선수} 의 두 딕셔너리를 만든다.
2. calling을 반복문으로 돌며, 해당 선수와 앞 등수의 선수 두 딕셔너리를 모두 수정해준다. 
3. 등수 딕셔너리 키의 값만을 출력한다.

풀이

def solution(players, callings):
    idx = {i:player for i, player in enumerate(players)}  # {등수:선수} 딕셔너리 생성
    p = {player:i for i, player in enumerate(players)}  # {선수:등수} 딕셔너리 생성
    
    for i in callings:
        loc = p[i]  # 호명된 선수의 현재 등수
        pre = idx[loc-1]  # 앞 선수
        
        idx[loc] = pre  # 앞 선수의 등수를 다운
        idx[loc-1] = i   # 호명된 선수를 앞 등수로 업
        
        p[i] = loc-1
        p[pre] = loc
        
    return list(idx.values())

무사 통과!

딕셔너리 배우기만 하고 문제에 적용해보지를 못했는데, 완벽하게 이해는 못해도 경험했다는 것에 만족!