새싹프로그래머의 이야기

풀이방법:

• 배열을 정렬하였으므로, citation[i]의 오른쪽은 모두 citation[i]보다 같거나 큽니다.
• 즉, 값이 citation[i] 이상인 배열의 개 수의 합은 length-i 입니다.
• 따라서, h번 이상 인용된 논문의 개 수가 h개 이상이여야 한다는 조건은 다음과 같이 구현됩니다. 이때, h번에 해당 하는 값은 length -i 이므로 해당 값을 return 합니다 .
• 다른 방식으로 문제를 풀 때 어려웠던 점은 [0,1,5,6,7,9] 라는 배열이 주어졌을 때, 배열 내에서만 조건을 충족하는 값을 찾아 많이 헤맸었습니다. 이 경우, 4가 나와야한다는 것을 인지하시고 풀면 도움이 많이 될 것 같습니다.

풀이코드:

def solution(citations):
    citations.sort()
    length = len(citations)

    for i in range(length):
        if citations[i] >= length-i and citations[i] >= i:
            return length-i
    return 0

https://school.programmers.co.kr/learn/courses/30/lessons/43162

풀이방법:

• 각 노드들의 관계가 배열로 주어졌을 때, 노드들이 이어져 있는 네트워크의 개 수를 세는 문제입니다.
• dfs를 이용하여 노드 간의 연결 관계를 탐색하고, visited를 이용하여 서로 다른 네트워크의 개 수를 셀 수 있도록 구현하였습니다.

풀이코드:

def dfs(n,computers,now,visited):
    for i in range(n):
        if i == now:
            continue
        if computers[now][i] == 1 and not visited[i]:
            visited[i] = True
            dfs(n,computers,i,visited)
    return 1

def solution(n, computers):
    answer = 0
    visited = [False] * n

    for i in range(n):
        if not visited[i]:
            answer += dfs(n,computers,i,visited)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/1844

풀이방법:

• bfs를 통해 문제를 해결하였습니다.
• direction 배열을 통해 이동할 수 있는 방향을 지정해주었습니다.
• 마지막으로, 가고자하는 위치의 값이 1(초기 값)이거나 현재 가는 경로가 더 가깝다면 갱신 될 수 있도록 하였습니다.

풀이코드:

from collections import deque
def solution(maps):
    q = [(0,0)]
    direction = [(0,1),(0,-1),(1,0),(-1,0)]

    while q:
        x,y = q.pop(0)
        for i,j in direction:
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]) :
                continue

            if maps[nx][ny] == 1 or maps[x][y]+1 < maps[nx][ny]:
                maps[nx][ny] = maps[x][y]+1
                q.append((nx,ny))

    return -1 if maps[len(maps)-1][len(maps[0])-1] == 1 else maps[len(maps)-1][len(maps[0])-1]

https://school.programmers.co.kr/learn/courses/30/lessons/42576

풀이방법:

• participant 중에서 completion에 없는 선수를 찾는 문제 입니다.
• 다만, 동명이인이 있을 수 있어 Counter 함수를 활용해 이름의 수를 세어주었습니다.
• 저는 문제를 이렇게 풀었지만, 문제를 풀고 난 후 Counter 객체는 빼기 연산이 가능하다는 것을 알 수 있었는데 ctra -ctrc 연산을 통해 Counter 객체에 남은 이름을 찾는 방법을 통해 더 깔끔하게 풀 수 있을 것 같습니다.

풀이코드:

from collections import Counter
def solution(participant, completion):
    ctrc = Counter(completion)
    ctra = Counter(participant)

    return ''.join([a for a in list(set(participant)) if ctra[a] != ctrc[a] ]) 

https://school.programmers.co.kr/learn/courses/30/lessons/42626

풀이방법:

• 최소 값을 연산하는 문제이므로, heapq를 사용했습니다.
• 종료 조건으로는 K 값을 구할 수 없는 경우(즉, 배열의 요소가 1개만 남아있고 그 값이 K보다 작은 경우) 와 최소 값이 K보다 크거나 한 개의 요소만 남아 더 이상 연산할 수 없는 경우로 설정하였습니다.
• scoville 배열이 정렬되어있다는 보장이 없는데, heapify() 함수를 통해 정렬해주지 않아 시간을 많이 잡아먹었습니다.

풀이코드:

import heapq
def solution(scoville, K):
    answer = 0

    heapq.heapify(scoville)
    while True:
        if len(scoville) == 1 and scoville[0] < K:
            return -1
        if scoville[0] >= K or len(scoville) == 1:
            break
        val1 = heapq.heappop(scoville)
        val2 = heapq.heappop(scoville)
        heapq.heappush(scoville, val1 + val2*2)
        answer+=1


    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스 '타겟넘버' 문제를 풀며, 제목과 같은 에러를 만났었습니다.

이에, 해당 문제를 해결할 수 있는 방법인 nonlocal과 global 변수 범위 지정 키워드에 대해서 정리하고자 합니다.

def solution(numbers, target):
    answer = 0
    length = len(numbers)

    def dfs(i, val):
        if val == target and i == length - 1:
            answer += 1
            return 0

        if i + 1 < length:
            dfs(i + 1, val + numbers[i + 1])
            dfs(i + 1, val - numbers[i + 1])

    dfs(-1, 0)
    return answer

처음에는 위와 같이 코드를 작성하였습니다. 

저는 solution 함수 내에 answer 변수가 선언 되어 있으므로, dfs 함수 내에서도 사용할 수 있을 것이라 생각하였습니다.

에러 코드를 보면 '할당되지 않아서' 에러가 발생함을 알 수 있습니다.

파이썬 컴파일러는 dfs 내의 answer 변수를 solution 함수 내의 answer 변수와 동일한 변수로 보지 않고, dfs 함수 내의 '로컬 변수'로 인식하여 발생하는 에러였습니다.

def solution(numbers, target):
    answer = 0
    length = len(numbers)
    visited = [False] * length

    def dfs(i, val):
        nonlocal answer
        
        if val == target and i == length - 1:
            answer += 1
            return 0

        if i + 1 < length:
            dfs(i + 1, val + numbers[i + 1])
            dfs(i + 1, val - numbers[i + 1])

    dfs(-1, 0)
    return answer

첫번째 해결 방법은 dfs 함수 내에 answer라는 변수에 nonlocal 이라는 keyword를 지정해주는 것입니다.

해당 키워드를 지정하게 되면, answer이라는 변수를 dfs 함수 내의 로컬 변수로 취급하지 않고 solution 함수 내의 answer 변수를 의미한다고 설정해주는 것입니다.

def solution(numbers, target):
    global answer
    answer = 0
    length = len(numbers)
    visited = [False] * length

    def dfs(i, val):
        global answer

        if val == target and i == length - 1:
            answer += 1
            return 0

        if i + 1 < length:
            dfs(i + 1, val + numbers[i + 1])
            dfs(i + 1, val - numbers[i + 1])

    dfs(-1, 0)
    return answer

두번째 해결 방법은 global이라는 keyword를 지정해주는 것입니다. 

global 변수는 해당 변수를 전역 변수로 사용하겠다는 것을 의미합니다.

따라서 위와 같이 각 함수 내에 global이라는 keyword를 사용하여 answer이라는 변수를 로컬 변수가 아닌 전역 변수로 설정해주는 방법이 있습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12906

풀이방법:

• 중복된 숫자를 제거하는 문제
• list를 탐색하며 now 변수를 활용해 연속적으로 나오는 동일한 숫자를 제거

풀이코드:

def solution(arr):
    now = arr[0]
    answer = [now]
    for i in arr:
        if now != i:
            answer.append(i)
            now = i
        else:
            continue
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/43165

풀이방법:

• 주어진 숫자들을 모두 사용하되, 덧셈과 뺄셈을 이용해서 target과 동일한 값을 만드는 경우의 수를 구하는 문제
• dfs를 통해 모든 원소를 더한 마지막 단계부터 시작하여 이전 단계로 돌아가며 해당 단계의 원소의 값을 더했을 때와  뺐을 때의 모든 경우의 수를 탐색

풀이코드:

def solution(numbers, target):
    answer = 0
    length = len(numbers)

    def dfs(i, val):
        nonlocal answer

        if val == target and i == length - 1:
            answer += 1
            return 0

        if i + 1 < length:
            dfs(i + 1, val + numbers[i + 1])
            dfs(i + 1, val - numbers[i + 1])

    dfs(-1, 0)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/86491/solution_groups?language=python3&type=my 

풀이방법:

• 명함은 옆으로 눕혀서 넣을 수 있으며, 모든 명함이 들어갈 수 있는 최소 크기를 구하는 문제
• 따라서, 주어진 각 명함의 가로와 세로의 크기 중에서 큰 값들 중 제일 큰 값과 작은 값들 중 제일 큰 값을 구해야함

풀이코드:

def solution(sizes):
    maxv,minv = 0,0

    for card in sizes:
        maxv = max(card) if max(card) > maxv else maxv
        minv = min(card) if min(card) > minv else minv
    return maxv*minv

https://school.programmers.co.kr/learn/courses/30/lessons/178870

풀이 방법

• 비내림차순으로 정렬된 수열이 있을 때, 연속된 부분 수열의 합이 k가 되는 수열 중 가장 길이가 짧고 시작 인덱스가 작은 부분 수열의 index를 찾는 문제.
• 주어진 수열을 순회하며 합이 k가 되는 부분수열을 찾고자 함.
• 하지만, 단순히 k가 되는 index를 찾았을 때 그 다음 index부터 찾고자 하면 k=5 이고 [1,1,1,2,3,4] 가 있을 때 [1,1,1,2]를 찾은 이후 [2,3]을 찾지 못하는 경우 발생.
• 따라서, while 문을 통해 제일 먼저 포함했던 원소를 제거해가며 값이 갱신되도록 해주었음. 
• ex) [1,1,1,2]가 있을 때, 앞에 들어온 [1,1,1]을 3이 대체하여 [2,3]이 되는 방식 . 또한, [1,1,1,2,2,4] 가 있을 경우, 앞선 '1' 2개를 '2' 1개가 대체할 수 있음.

풀이 코드

from collections import deque


def solution(sequence, k):
    answer = []
    length = len(sequence) - 1
    idxs = deque()
    kval = k

    for idx, i in enumerate(sequence):
        kval -= i
        idxs.append(idx)

        if kval == 0:
            answer.append([idxs[0], idxs[-1]])

        while idxs and idx < length and kval < sequence[idx + 1]:
            kval += sequence[idxs.popleft()]

    return sorted(answer, key=lambda x: x[1] - x[0])[0]