[프로그래머스] 추억 점수 - 파이썬/python

문제

https://school.programmers.co.kr/learn/courses/30/lessons/176963

프로그래머스

그리워하는 사람의 이름과 사람별 그리움 점수가 주어질 때, 각 사진을 기반으로 추억 점수를 계산하는 문제다.

 

제한사항

• 3 ≤ name의 길이 = yearning의 길이≤ 100
  • 3 ≤ name의 원소의 길이 ≤ 7
  • name의 원소들은 알파벳 소문자로만 이루어져 있습니다.
  • name에는 중복된 값이 들어가지 않습니다.
  • 1 ≤ yearning[i] ≤ 100
  • yearning[i]는 i번째 사람의 그리움 점수입니다.
• 3 ≤ photo의 길이 ≤ 100
  • 1 ≤ photo[i]의 길이 ≤ 100
  • 3 ≤ photo[i]의 원소(문자열)의 길이 ≤ 7
  • photo[i]의 원소들은 알파벳 소문자로만 이루어져 있습니다.
  • photo[i]의 원소들은 중복된 값이 들어가지 않습니다.

 

예시

Example 1:

name: ["may", "kein", "kain", "radi"]
yearning: [5, 10, 1, 3]
photo: [["may", "kein", "kain", "radi"],["may", "kein", "brin", "deny"], ["kon", "kain", "may", "coni"]]
result: [19, 15, 6]

 

Example 2:

name: ["kali", "mari", "don"]
yearning: [11, 1, 55]
photo: [["kali", "mari", "don"], ["pony", "tom", "teddy"], ["con", "mona", "don"]]
result: [67, 0, 55]

 

Example 3:

name: ["may", "kein", "kain", "radi"]
yearning: [5, 10, 1, 3]
photo: [["may"],["kein", "deny", "may"], ["kon", "coni"]]
result: [5, 15, 0]

 

풀이

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

• 각 사진을 순차적으로 탐색한다.
• 각 사진의 추억 점수를 계산하기 위해 score 변수를 초기화한다.
• 사진 속 친구들을 탐색한다.
  • 사진에 있는 친구가 추억 점수가 있는 친구라면 해당하는 추억 점수를 더한다.
    - index() 사용
• 사진 한 장에 대한 추억 점수를 정답 리스트에 추가한다.
• 모든 사진에 대한 추억 점수를 반환한다.

 

다른 사람의 풀이

위의 방법은 name.index(j)로 인덱스를 찾는 부분은 시간 복잡도가 O(n)이라, name 배열이 커질수록 성능 저하가 있을 수 있다. 이를 개선하기 위해 name과 yearning을 딕셔너리 형태로 매핑하면 탐색 시간을 O(1)로 줄일 수 있다.

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