[프로그래머스] 완주하지 못한 선수

/  제출 1회 차  /

 

정확성 100%

효율성 0% : 시간 초과

 

이유 추측 : 
participant 범위가 1 <= part.. <= 100,000에

completion 범위는 0 <= comp.. <= len(participant) -1 이므로

모든 participant 마다 for...in completion으로 일일이 찾아주고 비교를 했으니 시간 초과가 당연히 생겼다.

그리고 문제를 잘 못 읽어 완주하지 못하는 모든 선수들을 고려해 코드를 작성했다. 댓츠 노노

---

문제 첫 줄부터 꼼꼼히 안 읽었다. 다시 읽으니 조건 하나가 더 눈에 띄더라.
" 단, 한 명의 선수 제외하고 모두 들어올 것. " 

그리고 알파 조건 "단, 동명이인 있을 수 있다."

---

 

이러면 찾아야 하는 해답의 범위가 엄청 좁아진다. 딱 한 예외 케이스만 찾아내면 되는 것. 

 

주어지는 값이 모두 문자열인 것에서 아이디어를 착안해 풀었다.

단 한 명만 제외되었다는 것에서 힌트를 가졌는데,

딱 그 예외 경우만 찾으면 되겠다 싶었다.

1) sort() 함수는 O(nLogn) 중에서도 최적화가 잘 된 내장 함수이므로 2번을 각각 리스트에 사용해도 시간 초과가 나지 않을 것이라고 생각했고.

2) 앞서 말한 딱 그 예외 경우는 모든 값이 같은 두 리스트의 (sort 하면 순서도 같아진다.) 달라지는 지점을 찾으면 된다.

3) 인덱스 확인은 더 짧은 completion기준으로 잡고 그때까지 없으면 마지막 선수라는 뜻이니(정렬 기준 상 마지막) 그 선수를 리턴하면 된다.

이를 구현한 것이 다음 제출 2회 차

---

/  제출 2회 차  /

def solution(participant, completion):
    answer = ''
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            answer = participant[i]
            break
    if answer == '':
        answer = participant[-1]
    return answer

 

정확성 100%

효율성 100%

 

프로그래머스 모든 풀이 상위 기준 3번째 풀이였다.

 

---

[ 다른 분들 풀이 ]

---

1)

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

 

정말 간단해서 처음 보고 당황했다. 
내장 함수에 덜 익숙해서 봐도 딱 들어오지 않았다.

그래서 collections라이브러리 다시 보고 넘어가기로 했다.

 

 

-  복습 : python collections Counter  -

 

1. collections의 Counter 클래스는 들어오는 데이터의 문자 별 개수는 count 하여 리턴한다.

 

2. Counter 클래스에도 메서드가 있다. 예를 들면 most_common(n)은 리턴 값을 count개수가 큰 순서대로 정렬해 (n개 지정 option) 리턴하기도 한다. 이외에도 subtract(), elements(), subtract(), total(), fromkeys(), update()

 

 

더 많은 내용 파이썬 공식문서 참조 : https://docs.python.org/3/library/collections.html#collections.Counter

collections — Container datatypes — Python 3.10.5 documentation

 

 

- 굉장히 놀라운 건 Counter()로 받아온 딕셔너리 객체 간에 뺄셈이 가능하다.(동일 값이 지워지는 셈) 

 

- 풀이 댓글을 보니 Counter() 클래스를 사용하면 사실상 전 원소에 접근하기 때문에, 내가 푼 풀이처럼 이상 값을 만나면 멈추도록 하는 식으로 하는 게 더 효율적일 수도 있는 것도 알아두고 간다.

 

---

 

2) 

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer

 

: 해당 문제가 "해시" 카테고리인 것을 생각해봤을 때 그 목적에 잘 맞는 코드 구현인 것 같다.

두 리스트 중 매칭 안 되는 값이 단 하나라는 것을 이용해서 접근한 아이디어다. 

 

특정 키워드를 넣었을 때, 나오는 해시값을 temp에 넣어주고 딕셔너리에 해당 키:밸류를 저장한다.

다음 리스트에서 동일 값이 있다면 그를 빼주는 가감식으로 찾고자 하는 값을 찾아낸다. 그 해시값에 해당하는 밸류를 찾아주는 식.

 

이것도 마찬가지로 전체 리스트 아이템을 접근해야 한다.

 

 

파이썬 공식 문서 Hash() 함수 참조 : https://docs.python.org/3/library/functions.html?highlight=hash#hash 

 

Built-in Functions — Python 3.10.5 documentation

 

 

해시 개념은 오랜만이다. 사실. 정보보안 강의 수강 시 깊게 들어갔던 내용인데 오래간만에 봐서 재밌게 아티클도 몇 개 더 읽었다. 일단 코딩 테스트에 집중해야 하니 개념 정리는 조만간 다시 하기로.

 

---

 

 

공개 글에 다른 프로그래머스 유저들 답안 공개 가능한 건지 모르겠습니다.

 

문제 있다면 바로 지우거나 비공개로 돌리겠으니 댓글로 알려주시는 분이 있다면 감사할 것 같습니다.