[Programmers] L1. 추억 점수 (Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

photo 에서 한 행씩 꺼내고, 해당 행의 열을 하나씩 꺼내서 이름 리스트에 이름이 있는 경우 점수에 누적시킨다.

한 행을 다 돌았으면 점수를 결과 리스트에 추가한다.

 

Solution

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

 

현재 코드는 name.index(j)를 통해 리스트에서 이름의 인덱스를 찾는데, 리스트 검색이 반복적으로 수행되어 비효율적일 수 있다. 특히, photo의 크기가 커질수록 성능이 저하될 가능성이 크다.

 

개선할 점

• 딕셔너리를 사용하여 검색 시간 단축
  리스트를 매번 검색하지 않고, name과 yearning을 매핑한 딕셔너리를 사용하면 검색 시간이 상수 시간(O(1))으로 줄어든다.
• 코드 가독성 향상
  변수를 적절히 네이밍하고 반복문을 간소화하면 가독성이 좋아진다.

개선된 코드

def solution(name, yearning, photo):
    # 이름과 그리움 점수를 딕셔너리로 매핑
    yearning_dict = dict(zip(name, yearning))
    
    answer = []
    for people in photo:
        # 각 사진 속 인물의 점수를 계산
        score = sum(yearning_dict.get(person, 0) for person in people)
        answer.append(score)
    
    return answer

 

시간 복잡도

• 기존 코드
  • photo의 각 사진마다 j in name과 name.index(j)를 수행하므로 최악의 경우 O(N * M * K) (N: photo 길이, M: 사진 속 이름 수, K: name 길이).
• 개선 코드
  • 딕셔너리를 사용하여 점수 조회가 O(1)이 되므로, 전체 시간 복잡도는 O(N * M).

 

dict.get()

딕셔너리에서 존재하지 않는 키를 조회할 때 기본값(여기서는 0)을 반환하도록 설정하여 예외 처리를 간소화한다.

---