[파이썬] 프로그래머스 커뮤러닝 1주차 체육복

 

https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

 

제한사항

 - 전체 학생의 수가 30 이하라는 점을 잘 봐야딤

 - 체육복을 빌려줄 수 있지만 여벌 체육복을 도난당했을 수 있음 이때 다른 사람에게 줄 수는 없음

 - 1번이 2번에게만 빌려 줄 수 있음

 

문제의 접근방식

  - 1번이 2번, 3번이 4번 을 빌려줘 5가 될 수 있도록 하거나 3이 2를 빌려주거나 5가 4가 빌려줘 해결할 수 있을 것이다.

 

 탐욕법(Greedy)

  - 그 순간에 지엽적으로 최적이라고 생각할 때 이를 활용하여 실시한다.

  - 매 단계에서 최적의 선택이 최적성을 해치지 않는다고 하면 이를 활용할 수 있다.

  - 빌려줄 학생들을 "정해진 순서"로 살펴야 하고, 이 "정해진 순서"에 따라 우선하여 빌려줄 방향을 정해야 함

  - (착안점) 학생의 수는 30명 밖에 되지 않으므로, 배열을 확보하고, 여기에 각자 가지고 있는 체육복 수를 기록함

  - 번호 순서대로"스캔"하여 빌려줄 관계를 정함

  - 해결방법 1

    1) n개의 전체 배열을 하나 만들고 reserve에 있는 수를 1씩 늘려 놓는다.

    2)  lost배열에 있는 숫자를 빼놓는다.

      - 2개의 체육복이 있는 사람만 양측중 하나에 체육복을 빌려 줄 수 있다. 

   

    3) 알고리즘의 복잡도

     - 탐욕범을 사용하여도 리니어 알고리즘에도 사용해도 충분하다고 봄

 

 

 해결방법 2

  - 위의 알고리즘도 충분하지만, 만약에 천만명의 학생중, 20명의 학생만 여벌이 있다면, 천만명의 학생을 전부 확인해야 하므로 시간복잡도가 올라간다. 

  - 이럴경우 여벌의 체육복을 가져온 학생들의 번호를 정렬하고, 이것을 순서대로 보면서 빌려줄 수 있는 다른 학생을 찾아 처리함

  - 빌려 줄 수 있는 다른학생은 해시를 적용해서 상수 시간에 처리하면 된다.

 - 먼저 오름차순으로 RESERVE를 정렬하고 LOST를 활용하여 해시테이블을 만든다.

 - 먼저 n개의 배열에서 각 reserve에 값을 빼주고  lost에 있는 값들 중 대치 가능한 값들을 빼주고 남은 값을 빼주면 값을 구할 수 있을것이다.

 

  - 알고리즘 복잡도

   1) 여벌의 체육복을 가져온 학생들의 번호를 정렬하면 O(klogk)의 복잡도를 가진다.

   2) 체육복을 빌려줄 수 있는 학생을 찾아 처리 하면 -> O(k) X O(1) 상수시간에 이것을 구현한다. 

   3) 전체 알고리즘의 시간 복잡도는 O(klogk)가 될 것이다. 

 

 

내가 직접푼 풀이

def solution(n, lost, reserve):

    for i in lost:
        min_num = i-1
        max_num = i+1
        if max_num not in reserve or max_num not in reserve:
            n-=1
        if i in reserve:
            n+=1

    return n

 - 처음 풀때에는 자신과 자신이 매칭되는 수도 고려하지 못하고 풀었다. 그래서 lost에 있는 숫자중, 1작은수 또는 큰수를 판별하여 숫자가 있으면 1씩 더했고, 그렇지 않으면 빼는 방식으로 했다. 테스트 코드에서는 작동이 되었지만, 채점 코드에서는 제대로 작동하지 않았다.

def solution(n, lost, reserve):

    uni_reserve = set(reserve) - set(lost)
    uni_lost = set(lost) - set(reserve)

    for i in uni_reserve:
        if i-1 in uni_lost:
            uni_lost.remove(i-1)
        elif i+1 in uni_reserve:
            uni_lost.remove(i+1)

    return n - len(uni_lost)

- 구글링을 통하여 본 문제이다. 기존코드에서 set함수를 통해 자신과 자신이 대응되는 것을 제거 해주고, 1작은 값이나 큰값이 대응되는것이 있다면 이를 제거해주고, 전체에서 남는것을 빼주는 방식으로 코드를 구현하였다. 채점코드 상으로 50점으로 상승하였지만 100점은 안되었다.

 

해결 풀이(1)

def solution(n, lost, reserve):
    u = [1] * (n+2)
    for i in reserve:
        u[i] += 1
    for i in lost:
        u[i] -= 1
    for i in range(1, n+1):
        if u[i - 1] == 0 and u[i] == 2:
            u[i -1:i +1] = [1, 1]
        elif u[i] == 2 and u[i +1] ==0:
            u[i:i +2] = [1,1]
    return len([x for x in u[1:-1] if x> 0])

 - 리스트가 0부터 시작하기 때문에 10이라면 0과 11번을 주고 시작을 한다.

 - reserve에 리스트가 있으면 1을 넣어 2를 만들어주고 lost에 있는 학생은 -1을 해줘서 수를 만들어 준다.

 - 빌려주는 규칙을 쓰는데, 만약 u[i-1]은 앞에 있는 학생이고 u[i+1] 뒤학생을 뜻한다. 

 - 즉 첫번째 if문에서 앞의 학생이 0이고 본인이 2개 갖고 있다면, u[i-1:i+1] 리스트 슬라이스를 통해서 둘의 값을 [1,1]로 만들어 준다. (이때 중요한건 앞의 학생이 없을때 먼저 주는것을 실행해 줘야 하는 것이다.)

 - elif 문에선느 뒷학생이 없고 내가 있을경우, 1씩 만들어주는 코드이다.

 - 마지막으로 번호가 유효한 학생 즉, 0인 아닌 학생을 꺼낸다. 

 

해결 풀이(2) (학생수가 많고, 여벌체육복이 별로 없을 경우)

 

def solution(n, lost, reserve):
    s = set(lost) & set(reserve) # 교집합
    l = set(lost) - s
    r = set(reserve) -s
    for x in sorted(r):
        if x - 1 in l:
            l.remove(x -1)
        elif x + 1 in l:
            l.remove(x +1)
    return n - len(l)

 - 먼저 lost와 reserve의 교집합을 통해서 잃어버렷으면서 여벌의 체육복이 있는 사람을 선정한다.

 - 그다음 lost에서 이를 빼준 set을 l을 만들고, reserve에도 이를 빼준 r을 만들어준다.

 - 정렬을한 r 을 for문을 돌면서 값이 1빼준 값이 l에 존재한다면 이를 제거해준다(이것도 마찬가지로 앞거부터 해줘야 한다.,)

 - elif문 통해서도 앞에 있는 값이 있으면 이를 제거해준다

 - l에서 남은값을 전체에서 빼준다.

시간 복잡도는 

r만큼 동작을 하고, 크기순서대로 정렬하는데 klogk만큼의 복잡도를 소요하게 됨 알고리즘 복잡도는 k log k에 비례해서 실행되게 됨 set 구성할때, 배열의 길이에 비례해서 단계 그리고 복잡도가 필요하므로 k log k에 비례해서 이가 실행되게 됨

적은수의 학생이기 때문에 여벌의 체육복이 별로 없다면 1번째 방법보다 훨씬 간단하게 실행될 수 있다.