h32j00

문제

처음 작성한 코드

def solution(n, computers):
    answer = 0
    visited = []
    stack = [0]
    all_stack = set([i for i in range(n)])
    while True:
        if len(visited)==n:
            return answer+1
        if len(stack)==0:
            answer+=1
            stack.append(list(all_stack-set(visited))[0])
        a = stack.pop()
        if a not in visited:
            visited.append(a)
        for j in range(n):
            if computers[a][j]==1 and a!=j and j not in visited:
                stack.append(j)

1. 탈출조건: 모든 노드를 다 방문했을 때
2. len(stack)이면 네트워크가 끊긴거라 answer+=1 하고 visited 안한 노드를 stack에 넣고 그 노드가 속해있는 네트워크를 다시 돈다.
3. stack(방문해야할 노드)에서 pop()하여 방문안했으면 방문을 하고, 노드의 이웃노드들을 stack에 넣는다. (왜냐면 방문해야하니까~)

깨달은 점

• 문제를 통과하긴 했는데 DFS인지 BFS인지 모르겠다..
• 네트워크가 끊기면 다음 방문할 노드를 어떻게 정할까 고민했었는데 set을 이용해서 all_stack에서 지금까지 방문한 노드의 리스트를 빼고 그 중 가장 앞에 있는 노드로 정했다. list는 빼기가 안되는데 set은 된다. set은 인덱스로 접근이 안되서 다시 list()로 변환하고 인덱스 접근을 시도해야한다.
• 오늘은 쉽게 푼 것 같다.

문제

처음 작성한 코드

answer = 0
def DFS(idx, numbers, target, value):
    global answer
    if idx == len(numbers):
        if value == target:
            answer+=1
        return

    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])
    
def solution(numbers, target):
    DFS(0,numbers,target,0)
    return answer

1. 탈출조건: 리스트 끝까지 갔을 때

2. 끝까지 갔는데 target이 됐다? 그럼 answer+=1

3. 쭉쭉쭉 더하면서 가다가 리스트 끝까지 다 갔으면 return 하고 다시 빼기로..

깨달은 점

1. 문제를 보고 어떤 알고리즘으로 푸는 게 맞는지 생각하는 능력을 길러야겠다..

2. dfs 풀려고 오랜만에 재귀 생각하니까 재밌었다. 쉬워서 그랬나?

3. 재귀를 풀 때는 항상 탈출조건과 어떻게 돌릴건지를 생각하면 된다.

문제

처음 작성한 코드

def solution(bridge_length, weight, truck_weights):
    from collections import deque
    answer = 0
    truck_weights = deque(truck_weights)
    on_bridge = []
    bbb = []
    seconds = [0]*len(truck_weights)
    idx=0
    while True:
        if len(bbb) < bridge_length and sum([i[1] for i in bbb])+truck_weights[0] <=weight:
                a = truck_weights.popleft()
                on_bridge.append([idx, a, True])
                bbb.append([idx,a])
                idx +=1
        if not len(truck_weights):
            answer+= bridge_length+1
            return answer
        for i in on_bridge:
            if i[2]==True:
                seconds[i[0]]+=1
                if seconds[i[0]]==bridge_length:
                    i[2] =False
                    bbb.remove([i[0],i[1]])
        answer+=1

코드 리뷰 후

def solution(bridge_length, weight, truck_weights):
    from collections import deque
    answer = 0
    on_bridge = deque([0]*bridge_length) # 큐를 이용하여 다리를 건너는 트럭을 나타낸다. (0으로 채우는 것은 그때의 트럭이 지나가지 않는다는 것)
    truck_weights = deque(truck_weights)
    sum_weight = 0 # sum(on_bridge)할 때 시간 초과가 나기 때문에 sum을 위한 변수
    while truck_weights: # 대기 중인 트럭이 있을 때
        answer+=1 # 1초의 시간
        sum_weight-=on_bridge.popleft() # 다리를 끝까지 지나간 트럭 무게 빼주기
        if sum_weight + truck_weights[0]<= weight: # 문제 상의 조건(대기 중인 트럭이 다리를 건널 수 있는가)
            sum_weight += truck_weights[0] # 다리 위의 트럭 무게를 더한다.
            on_bridge.append(truck_weights.popleft()) # 대기 중인 트럭을 다리 위의 트럭 리스트에 추가
        else: # 다리를 건널 조건이 안되면
            on_bridge.append(0) # 0으로 채운다. (트럭이 못지나가기 때문..)
            
    # bridge_length를 더하는 이유는 대기 중인 마지막 트럭을 빼고 while문을 빠져나오기 때문에 
    # 그 트럭이 다리를 건너는 시간인 bridge_length를 더해주는 것
    return answer+bridge_length 

깨달은 점

1. 어떻게 저렇게 생각을 하지?. . . . 난 너무 복잡하게 생각했다.....

2. for문 돌릴 때, ( for i in a: ) 이렇게 해놓고 for 문안에서 a의 원소를 remove하거나 리스트 자체에 변화가 생기면 내 뜻대로 돌아가지 않는다는 사실을 알아냈다..... ㅡ.ㅡ 어려워

문제

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

처음 작성한 코드

def solution(priorities, location):
    from collections import deque
    together = deque([f'{chr(65+i)}:{priorities[i]}' for i in range(len(priorities))])
    location = together[location]
    finish = []
    while len(finish)<=len(priorities):
        if len(together):
            a = together.popleft()
        else: 
            finish.append(a)
            break
        for idx,j in enumerate(together):
            if a.split(':')[1] < j.split(':')[1]:
                together.append(a)
                break
            if idx==len(together)-1:
                finish.append(a)
    return finish.index(location)+1

1. 리스트 together에 'A':2, 'B':1 이런식으로 저장한다.

2. 프린트를 하면 리스트 finish에 넣는다.

3. 'A':2 이런식으로 저장했기 때문에 split(':')을 이용하여 비교를 해줘야한다.

4. 포문을 돌면서 마지막까지 돌았는데 나보다 큰 애가 안나오면 finish에 넣는다.

코드 리뷰 후

def solution(priorities, location):
    from collections import deque
    together = deque([(i,value) for i,value in enumerate(priorities)])
    cnt = 0
    while True:
        p = together.popleft()
        if any(p[1]<q[1] for q in together):
            together.append(p)
        else:
            cnt +=1
            if p[0]==location:
                return cnt

1. 리스트 together에 (idx,value) 이런 식으로 저장한다. (0,2), (1,1) 이런 식..

2. while문 돌면서 진행하고 내가 원하는 location을 찾으면 반환하고 함수를 종료한다.

3. while문 안에서의 로직은 리스트에서 popleft()로 원소를 뽑고 나보다 큰 게 나오면 조용히 다시 넣고.. 아니면 출력하고(cnt+=1) 그 출력한 것이 내가 원했던 location이라면 출력한 순서인 cnt를 반환하고 종료한다.

깨달은 점

1. together에 'A':2 이런식으로 넣다보니 코드가 조금 지저분해졌다.. index를 활용하자!

2. 출력할 때마다 cnt를 +1 하고 그 때 location이랑 비교하는 건 사실 생각치도 못했다.. ㅜ.ㅜ

3. 너무 어렵게 생각했다..

4. collections의 deque 좋다.. popleft() 좋다

문제

처음 작성한 코드

def solution(brown, yellow):
    s = brown+yellow
    for i in range(s,0,-1):
        if s%i==0:
            if (i-2)*(s/i-2)==yellow:
                return [i,s//i]

가로(i)가 세로(s//i)보다 크거나 같다고 해서 for문돌때 0이 아닌 s부터 시작해서 다른 조건문없이 구할 수 있게 하였다. 

깨달은 점

1. 완전탐색 문제 중에 젤 빨리 푼 것 같다 히히  레벨2가 맞나????

문제

처음 작성한 코드 // 시간 초과 (코드 없어짐..)

코드 리뷰 후

def is_prime(n):
    if n<2: return False
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            return False
    else: return True

def solution(numbers):
    from itertools import permutations
    answer = 0
    result = []
    for i in range(len(numbers)):
        result += set(map(int, map(''.join, permutations(numbers, i+1))))
    for i in set(result):
        if is_prime(i): answer+=1
    return answer

깨달은 점

1. 모든 경우의 수를 다 따지는 거라면 permutations가 내가 짠 것보다 빠르다..

2. 소수를 찾을 때에는 최대 약수가 sqrt(n) 이하이므로 거기까지만 체크하면 된다.

 -> 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 

문제

처음 작성한 코드 // 90.9 점 나옴

def solution(name):
    alphabet = [chr(65+i) for i in range(26)]
    result = ['A']*len(name)
    answer = 0
    cursor = 0
    for idx,value in enumerate(name):
        i = alphabet.index(value)
        if i < 26-i:
            answer += i
        else:
            answer += (26-i)
        if idx+1!= len(name) and result[idx+1] != name[idx+1]:
            if idx+1-cursor < cursor+1: # 오른쪽으로
                answer+= (idx+1-cursor)
            else: # 왼쪽으로 돌아서 맨 오른쪽으로
                answer += cursor+1
            cursor = idx+1 # 'A' 인 애들 뛰어넘기
    return answer

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42860#

깨달은 점

문제에서 "최소값"을 찾으라 하여 찾았는데.. 90.9점이 뜹니다.. 제 코드를 보시고 혹시 잘못된 점이 있다면 댓글에 남겨주시면 감사하겠습니다!!

문제

처음 작성한 코드

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는 자료구조의 큐처럼 값을 앞, 뒤에서 꺼내고 넣을 수 있다.