h32j00

문제

처음 작성한 코드

def solution(progresses, speeds):
    from collections import deque # 큐
    import math
    answer = deque([]) # 배포하는 데까지 걸리는 날짜 수
    result = []
    progresses = deque(progresses)
    speeds = deque(speeds)
    while progresses: # 진행속도를 계산하여 배포하는 데까지 걸리는 날짜 수를 저장
        answer.append(math.ceil((100-progresses.popleft())/(speeds.popleft())))
    cnt = 1
    for _ in list(answer):
        if len(answer):
            a = answer.popleft()
        if not len(answer):
            result.append(cnt)
            break
        for j in list(answer):
            if a >= j: #기준점(맨 왼쪽 수) 보다 작으면 하나씩 pop 하면서 cnt 증가
                answer.popleft()
                cnt+=1
            else: # 큰거 나오면 지금까지의 cnt를 저장하고 중단
                result.append(cnt)
                cnt=1
                break #중단하고 큰 for문으로 가면 answer 맨 왼쪽[0]엔 다음 배포날짜가 나옴
    return result

깨달은 점

1. math.ceil()하면 올림이 되고 반환도 int형으로 해준다.

2. level2의 스택/큐 문제를 푸는데 조금 어렵다.. 하다보면 되겠지..

3. 어떻게 풀지는 알겠는데 파이썬으로 구현이 좀 어렵다.. 파이썬 좋은데 어렵다....

4. collections의 deque 진짜 좋다.. popleft() 빠르다 대박~

문제

처음 작성한 코드 // 효율성 통과 X

def solution(prices):
    answer = [0]*len(prices)
    for idx,_ in enumerate(prices):
        first = prices.pop(0)
        for j in prices:
        	answer[idx]+=1
            if first>j:
                break
    return answer

코드 리뷰 후 // deque 사용

def solution(prices):
    from collections import deque
    answer = [0]*len(prices)
    prices =deque(prices)
    for idx,_ in enumerate(list(prices)):
        first = prices.popleft()
        for j in prices:
            answer[idx]+=1
            if first>j:
                break
    return answer

깨달은 점

1. pop()은 O(1), pop(index)는 O(n) 시간이 걸린다. 이유는 해당 인덱스 값을 pop 하는 건 O(1)이지만 그 후 앞으로 다 땡겨줘야하기 때문에 O(n)이 걸린다고 한다.

2. 큐를 이용하여 문제를 풀고싶을 때는 collections의 deque를 이용하자. deque는 자료구조의 큐처럼 값을 앞, 뒤에서 꺼내고 넣을 수 있다.

문제

처음 작성한 코드

def solution(s):
    result = []
    for i in s.split(' '):
        a = ''
        for idx,j in enumerate(i):
            if idx%2==0: a += j.upper()
            else: a += j.lower()
        result.append(a)
    return ' '.join(result)

코드 리뷰 후

def solution(s):
    return ' '.join([''.join([j.upper() if idx%2==0 else j.lower() for idx,j in enumerate(i)]) for i in s.split(' ')])    

깨달은 점

1. 공백을 기준으로 split 하고 싶을때 split()가 아닌 split(' ')로 하자

2. [j.upper() if~ else~ for문] 이런식으로 if, else 둘다 [ ] 에 넣을 수 있었다. (if와 else 뒤에 : 없이 사용)

문제

처음 작성한 코드

def solution(n):
    return [int(i) for i in (list(str(n)))[::-1]]

코드 리뷰 후

def solution(n):
    return list(map(int, reversed(str(n))))

깨달은 점

1. list를 reversed()라는 함수를 이용하면 거꾸로 할 수 있다.

2. map()을 이용하여 int로 바꿀 수 있다..

3. 잘 짰다고 생각했는데 아니였다..

문제

처음 작성한 코드

def solution(a, b):
    return sum([value*b[idx] for idx, value in enumerate(a)])

코드 리뷰 후

def solution(a,b):
    return sum([x*y for x,y in zip(a,b)])

깨달은 점

1. 리스트의 길이가 같으면 zip()을 이용할 수 있다. zip(a,b)를 하면 리스트 a와 b의 원소를 하나씩 반환해준다.

문제

처음 작성한 코드

def solution(n):
    answer = 0
    result = []
    while n:
        n,i = divmod(n,10)
        result.append(i)
    answer = sum([i*(10**idx) for idx,i in enumerate(sorted(result))])
    return answer

코드 리뷰 후

def solution(n):
    return ''.join(sorted(list(str(n)),reverse=True))

깨달은 점

1. 계산하지 않고 리스트 n을 정수에서 문자로 바꿔준다. -> list(str(n))

2. sorted(reverse=True)를 통해 내림차순으로 정렬해준다.

3. 하나의 문자열로 반환하기 위해 ''.join()을 사용한다.

4. 왜 다 계산했을까..

문제

처음 작성한 코드(dict, hash X) // 효율성 체크 Non Pass

def solution(participant, completion):
     _par = [i for i in participant]
     _com = [i for i in completion]
     result = []
     for value in _par:
         if value not in _com:
             result.append(value)
         else:
             _com.pop(_com.index(value))
     return ''.join(result)

두번째 작성한 코드(dict O) // 효율성 체크 Non Pass

def solution(participant, completion):
    _par = {x:participant.count(x) for x in participant}
    _com = {x:completion.count(x) for x in completion}
    for key in _com.keys():
        _par[key]-=_com[key]
    for key in _par.keys():
        if _par[key]!=0: 
            result = key
            break
    return result

_par, _com에 값을 넣는 과정 중 count(x)와 for문에서 모두 O(n) 만큼 소요, 즉 O(n^2) 소요 -> 효율성 나쁨

세번째 작성한 코드(dict O) // 효율성 체크 Pass

import collections
def solution(participant, completion):
    result = collections.Counter(participant) - collections.Counter(completion)
    print(list(result.keys())[0])

코드 리뷰 후(hash O)

def solution(participant, completion):
    temp = 0
    dic = {}
    for p in participant:
        dic[hash(p)] = p
        temp += hash(p)
    for c in completion:
        temp -= hash(c)
    return dic[temp]

1. participant의 원소(참가자 이름)에 따른 hash 값을 key로 하고 원소(참가자 이름)를 value로 하는 dic을 생성

 -> hash값 계속 변화

2. 참가자 리스트를 돌면서 temp에 참가자 이름에 따른 hash값을 더해준다.

3. 완주자 리스트를 돌면서 temp에서 완주자 이름에 따른 hash값을 빼준다.

4. 그렇게 되면 하나의 hash 값만 남을 것이다.

5. 그 hash 값에 대한 value(참가자 이름)를 return 한다.

깨달은 점

1. dictionary는 dict() 또는 {} 요렇게 초기화할 수 있고, key:value 이렇게 구성된다. dict[key] 하면 value를 직접 접근할 수 있어서 O(1)의 시간이 걸린다고 한다.

2. collections라는 라이브러리를 알아냈다. collections의 Counter()는 "key:key의 갯수" 이렇게 정리해준다.

3. Counter()는 뺄셈 연산이 가능하다. dict의 item 갯수가 다르더라도 가능하다.

4. hash()의 사용법을 알게되었다. 코드 밑에 설명을 썼다.

문제

처음 작성한 코드

def solution(answers):
    one = [1,2,3,4,5]
    two = [2,1,2,3,2,4,2,5]
    three = [3,3,1,1,2,2,4,4,5,5]
    result = [0,0,0]
    for idx, value in enumerate(answers):
        if one[idx%len(one)]==value:
            result[0]+=1
        if two[idx%len(two)] == value:
            result[1]+=1
        if three[idx%len(three)] == value:
            result[2]+=1
    answer = [idx+1 for idx,i in enumerate(result) if i==max(result)]
    return answer

깨달은 점

max()의 반환 값은 idx가 아닌 value라는 것..

잘 짠 코드 같다!

문제

처음 작성한 코드

#5,7 Non Pass
def solution(n, lost, reserve):
    have = [1]*n # 체육복 가진 사람=1 아니면 0
    give = [0]*n # 빌려준 사람=1 아니면 0 -> 두 번 빌려줌을 방지하기 위해
    reserve = [i-1 for i in reserve] # index 헷갈려서 -1 함
    for i in lost:
        have[i-1] = 0 # lost면 체육복 안가졌으니 flag=0 
    for i in reserve: #여분 가진 사람
        if give[i]==0:
            if have[i]==0: have[i]=1
            elif i==n-1:
                if have[i-1]==0: have[i-1]=1
            elif i==0:
                if have[i+1]==0: have[i+1]=1
            else:
                if have[i-1]==0:have[i-1]=1
                elif have[i+1]==0: have[i+1]=1
            give[i]=1
    return have.count(1) 

코드 리뷰 후

def solution(n, lost, reserve):
    _lost = [i for i in lost if i not in reserve]
    _reserve = [i for i in reserve if i not in lost]
    for i in _reserve:
        if i-1 in _lost:
            _lost.remove(i-1)
        elif i+1 in _lost:
            _lost.remove(i+1)
    return n-len(_lost)

깨달은 점

너무 어렵게 생각했다.. -> 처음 작성한 코드 개판..

탐욕법이 도대체 뭔지 모르겠다..

테스트 케이스 5,7 번에서 NP 떠서 고민고민하고 있었는 데, 연주(내친구)가 반례를 찾아줬다..

제한사항중에 "여벌 체육복을 가져온 학생이 도난당할 수 있다." 라는 표현때문에 

reserve를 돌면서 i+1, i-1 에게 빌려주기전에 i인 자신에게 먼저 빌려주면 된다고 생각했는데 생각이 짧았다.

  -> 반례) solution(5, [3,4,5],[2,3,4]) 이렇게 되면 2가 3한테 먼저 빌려주게 되어버리니까 내가 생각한대로 구현하기 위해서는 for 문을 돌기전에 lost와 reserve에 공통적으로 있는 3,4 를 없애주고 시작하는 것이 맞다.