[코딩테스트] 프로그래머스 - 완주하지 못한 선수 (Lv1) in Python3 / JS

프로그래머스 (programmers.co.kr) 에서 코딩 테스트 연습을 시작했다. 갈 길이 멀구나...!

그래도 다른 분들의 간결하고 효율적인 코드를 보면서 새로운 것을 배우는 과정이 재밌다.

 

혹시 문제가 있을까봐 나의 코드만 기록해두겠다!

 

Python3

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

 

JavaScript

function solution(participant, completion) {
    var i;
    const lastIndex = completion.length;

    participant.sort();
    completion.sort();

    for (i=0; i<lastIndex;i++){
       if (participant[i]!= completion[i]){
           return participant[i];
       }
    }
    return participant[lastIndex];
}

 

추가 - Python

프로그래머스 강의를 듣고, hash를 이용해 O(n)만에 푸는 방법

def solution(participant, completion):
	d = {}
    
    for i in participant:
    	d[i] = d.get(i, 0) + 1
    for i in completion: 
    	d[i] -= 1
        
    answer = [k for k,v in d.items() if v != 0]
    
    return answer

participant를 키로 해서 dictionary value에 1씩 더해준 후,

completion안에 있는 키의 value는 1씩 빼준다.

participant와 completion에 모두 있는 인물이라면 value는 결국 0이 될테니,

value != 0인 key 반환하면 됨.

 

Lessons Learned (on Python3)

1. 중첩 for loop는 노노!

처음에 효율성 하나도 생각 안 하고, 중첩 for loop 비교문으로 구현했더니, n번의 search * n번의 search 로 O(n^2)가 나와 효율성 테스트를 하나도 통과 못했다.

제약 상황이 n = 100,000일 때, n^2 =10,000,000,000이고, 대략 1초 / 1억이라고 했을 때 100초가 걸려 timeout이 될 것이기 때문. (출처:박석준님의 다른 분 질문에 대한 답변 - 감사합니다.)

 

다른 분들 코드를 보면서 배운 부분들

2. collections.Counter()

 

collections 모듈이란?

this module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple.

-  docs.python.org/3

그 중에서 Counter()는 리스트에서 원소의 개수를 카운팅할 때 쓸 수 있는 객체이며, dictionary 값으로 출력된다.

class collections.Counter([iterable-or-mapping])
A Counter is a dict subclass for counting hashable objects. It is a collection where elements are stored as dictionary keys and their counts are stored as dictionary values. Counts are allowed to be any integer value including zero or negative counts. The Counter class is similar to bags or multisets in other languages.

-  docs.python.org/3

 

예시:

import collections

sample = ['a', 'b', 'c', 'c']
countered = collections.Counter(sample)

일 때, countered의 값은 {'a':1, 'b':2, 'c':2}가 된다.

 

그리고 Counter Object의 좋은 점은, 기본 수학적 연산이 가능하다는 것이다.

Several mathematical operations are provided for combining Counter objects to produce multisets (counters that have counts greater than zero). Addition and subtraction combine counters by adding or subtracting the counts of corresponding elements. Intersection and union return the minimum and maximum of corresponding counts. Each operation can accept inputs with signed counts, but the output will exclude results with counts of zero or less.

-  docs.python.org/3

c = Counter(a=3, b=1)
d = Counter(a=1, b=2)

c + d                       # add two counters together:  c[x] + d[x]
# Result: Counter({'a': 4, 'b': 3})

c - d                       # subtract (keeping only positive counts)
# Result: Counter({'a': 2})

c & d                       # intersection:  min(c[x], d[x]) 
# Result: Counter({'a': 1, 'b': 1})

c | d                       # union:  max(c[x], d[x])
# Result: Counter({'a': 3, 'b': 2})

 

따라서, 이 문제도

answer = collections.Counter(participants) - collections.Counter(completion)
return list(answer.keys())[0]

로 접근하면 쉽게 된다.