티스토리 뷰

반응형

 

문제

해시 - 완주하지 못한 선수

 

 

문제 분석하기

굉장히 쉬운 문제예요!

머리 예열 겸 코딩 테스트 연습을 다시 풀고 있어요.

아쉽게도 지원 언어가 C++, Java, JavaScript, Python 뿐이고 Swift는 없어서, 저의 경우 Java, JavaScript, Python으로 풀었는데 이 글에서는 Python의 코드로만 설명해볼게요 :)

 

그리고 이 글을 쓰게 된 이유는 가장 아래 문제 풀이 고민에서 말해볼게요!

 

두 가지 배열이 주어지고, 앞선 배열인 participants는 반드시 뒤의 배열인 completion 보다 요소 1개를 더 가지고 있고 이 요소를 찾는 문제예요.

 

가장 단순하게는 participants를 for문으로 돌고, completion을 그 안에서 순회하면서 매칭 되는지 여부를 판단하면 쉽게 풀 수 있지만 이렇게 되면 O(N^2)의 복잡도로 효율성에서 문제가 생겨요.

 

그래서 메모리를 조금 더 사용해서 효율성을 높이려고 해요.

이때, 값의 저장을 딕셔너리라는 해시 형태로 하면 쉽게 요소를 판별할 수 있어요.

 

(개인적으로 이 문제를 풀 때 LeetCode - Two Sum 문제와 생각의 방식이 거의 동일하다고 느꼈어요.

이 문제와 함께 풀어보면 더 좋을 것 같아요!)

 

특히 파이썬은 dict라는 단순 딕셔너리도 있지만 defaultdict, Counter라는 특별한 형태의 해시가 있어요.

 

defaultdict 사용하기

Python에서 defaultdict는 collections에 있어요.

그래서 

from collections import defaultdict

의 형태로 불러와 사용 가능해요.

defaultdict가 필요한 상황을 가정해볼게요.

names = ["Bobby", "Kane", "Bob"]
cars = {"Bobby" : 1, "Kane": 2}

이름으로 3명이 들어있는 배열이 있고, cars는 보유한 자동차 개수예요.

만약 이 3명에게 차를 1대씩 준다고 하면 names를 순회하면서 그 이름을 cars의 key로 접근하면서 +1씩 해주면 돼요.

하지만 이럴 경우 단순한 dict를 사용한다면 "Bob"에 대한 정보는 cars에 포함되어 있지 않기 때문에 우선 cars에 names의 요소가 모두 key 값으로 존재하는지 판단해야 해요.

값이 없는 상태에서 코드를

for person in names:
    cars[person] += 1

처럼 작성해버리면 "Bob"에서 에러가 발생하기 때문이에요.

cars["Bob"]은 없는 값이니까요 :)

 

그래서 defaultdict를 사용하면 이름 그대로 "없는 키 값으로 접근할 경우 기본값을 제공" 해줘요.

cars = defaultdict(int)

위처럼 타입을 작성하면 그 타입의 가장 기본값을 dict의 기본값으로 인식해서

cars["Bob"] += 1

 

"Bob"은 현재 없지만 cars["Bob"]에 접근하는 순간 0을 할당해서 에러를 발생시키지 않아요. 

즉, cars.keys()에 name이 있는지 확인하는 if 조건 작업을 하지 않아도 돼요.

 

Counter 사용하기

defaultdict를 사용한다면 if 조건문을 생략해도 되는 편리함이 있지만 개수를 세는 작업에서 결국 for문으로 순회를 해야 돼요.

이것 마저도 생략 가능한 도구가 Counter에요.

이름 그대로 개수를 세는 도구이고, defaultdict처럼 collections에 있어서 아래와 같이 사용할 수 있어요.

from collections import Counter

Counter(names) # dict 객체가 아닌 Counter 객체

 

최종 코드

최종 코드는 3가지가 있어요.

# 최종 코드
def solution1(participant, completion):
    from collections import Counter
    participant_dict, completion_dict = dict(Counter(participant)), dict(Counter(completion))
    for runner in participant_dict.keys():
        if runner not in completion_dict.keys() or participant_dict[runner] != completion_dict[runner]:
            return runner

# defaultdict 사용
def solution2(participant: [str], completion: [str]) -> str:
    from collections import defaultdict
    people_list = defaultdict(int)
    for person in completion:
        people_list[person] += 1
    for person in participant:
        if people_list[person] > 0:
            people_list[person] -= 1
        else:
            return person
    return ""

# solution2를 단순히 Counter로 변경
def solution3(participant: [str], completion: [str]) -> str:
    from collections import Counter
    people_list = Counter(completion)
    for person in participant:
        if people_list[person] > 0:
            people_list[person] -= 1
        else:
            return person
    return ""

 

문제 풀이 고민

글 서문에 언급한 것처럼 이 고민이 이 글을 쓰게 된 이유예요.

로직은 너무나 단순한 문제이지만, 제가 푼 solution을 볼 때 위화감이 드는 부분이 있었어요.

def solution1(participant, completion):
    ...
    for runner in participant_dict.keys():
        if runner not in completion_dict.keys() or participant_dict[runner] != completion_dict[runner]:
            return runner # 반환값

def solution2(participant: [str], completion: [str]) -> str:
    ...
    for person in participant:
        if people_list[person] > 0:
            people_list[person] -= 1
        else:
            return person # 반환값
    return "" # 무의미한 return

def solution3(participant: [str], completion: [str]) -> str:
    ...
    people_list = Counter(completion)
    for person in participant:
        if people_list[person] > 0:
            people_list[person] -= 1
        else:
            return person # 반환값
    return "" # 무의미한 return

Python으로만 문제를 풀 때에는 별 생각이 없었는데 Swift로 생각하면 에러가 날 수 있는 로직이라 일부러 풀이마다 다른 형식으로 작성했어요. 

Swift의 경우 컴파일러가 메서드의 반환 값 타입을 이해하기 위해 Parameter 타입과 반환 타입을 의무적으로 명시해줘요.

반면에 파이썬은 컴파일러를 위해서가 아니라 코드 리더를 위해 명시적으로 작성해주는 기능이 추가되었을 뿐 실제 저 타입과 메서드의 반환 값이 매칭 되지 않아도 에러가 발생하지 않아요.

def test() -> str:
    return 1 # 반환값이 str이 아닌 int

print(test()) # 에러 발생 안함

또한 로직상 무조건 if 문 안에 들어갈 것이기 때문에 return을 if 안에서 처리한다고 해도, Swift의 경우 컴파일러 입장에서 if는 진입하지 않을 가능성이 항상 있기 때문에 else문이나 if문 바깥에 반드시 return이 존재해야 해요.

 

그래서 Swift였다면 solution2, solution3처럼 무의미한 return 값을 추가해주겠지만 Python은 solution1처럼 if 문 안에서만 처리해도 충분해요.

 

단, 위처럼 작성했을 때 입력 값이 예상 범위가 아니라면 틀린 답이 도출되는 게 아니라 아예 에러가 날 것이기 때문에 알고리즘 풀이에서만 사용 가능하다는 정도로 생각하고, 실제 코딩에서는 가능하더라도 사용하지 않으려고 해요!

반응형
댓글