새싹프로그래머의 이야기

풀이방법:

• 배열을 정렬하였으므로, 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/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/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]

[문제 풀이]

• 배열의 좌표가 (i,j)일 때, 해당 배열의 요소 값은 좌표 중 큰 값 입니다.
• 따라서, left와 right가 포함되는 열만 배열로 만들어서 배열의 좌표중 큰 값을 배열의 요소로 만들었습니다.
• 하지만, 시간 복잡도 부분에서 성능이 떨어지는 코드입니다. 또한, left와 right가 포함되는 열만 만들어줘야 하므로 출력하고자 하는 범위를 다시 계산해야한다는 단점이 있습니다.

**하지만, 저 좋은 발상이 있었습니다. 배열의 크기는 3x3이고 5번째 좌표를 알고 싶을 때, 그 좌표는 (5//3+1,5%3+1)인 것입니다.

(+1을 하는 이유는, 좌표를 (0,0) 부터가 아닌 (1,1)부터 계산하기 때문입니다.)

두번째 코드가 위 발상에 해당되는 코드입니다.

[풀이 코드]

def solution(n, left, right):
    answer = [(i, j) for i in range(int(left // n) + 1, int(right // n) + 2) for j in range(1, n + 1)]
    l = left - (int(left // n) * n)
    r = l + (right - left)
    return list(map(max, answer[l:r + 1]))

def solution(n, left, right):
    return [max(i // n, i % n) + 1 for i in range(left, right + 1)]

[풀이 방법]

• dfs를 활용하여 완전 탐색 진행하였습니다.
• isPrime 함수를 구현하여 소수 판별을 하였습니다.

[풀이 코드]

import math

def isPrime(k):
    if k in (2, 3):
        return True
    if k in (0, 1) or k % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(k)) + 1, 2):
        if k % i == 0:
            return False
    return True


def dfs(prev, num, numbers, visited):
    for i in range(len(numbers)):
        if visited[i]:
            continue
        visited[i] = True
        if prev + numbers[i] not in num and isPrime(int(prev + numbers[i])):
            num.append(prev + numbers[i])
        dfs(prev + numbers[i], num, numbers, visited)
        visited[i] = False


def solution(numbers):
    numbers = list(numbers)
    visited = [False] * len(numbers)
    prev = ''
    num = []

    dfs(prev, num, numbers, visited)

    return len(set(list(map(int, num))))

[문제 풀이]

-DFS를 활용하여 완전탐색을 진행하였습니다. 코드의 dfs 함수와 같이 방문했다가 나올 경우, (visited = false)를 통해 방문하지 않은 걸로 처리해주어 완전 탐색이 가능하도록 하였습니다.

-완전 탐색 시 가장 깊게 들어간 경우를 측정해야하므로, depth 설정을 통해 모든 경우에서 가장 깊게 들어간 경우를 측정해주었습니다.

[풀이 코드]

def dfs(k, answer, depth, dungeons, visited):
    answer = max(answer, depth)
    for i in range(len(dungeons)):
        if visited[i] or k < dungeons[i][0]: continue

        visited[i] = True
        answer = dfs(k - dungeons[i][1], answer, depth + 1, dungeons, visited)
        visited[i] = False
    return answer


def solution(k, dungeons):
    visited = [False] * len(dungeons)
    depth = 0
    answer = -1
    answer = dfs(k, answer, depth, dungeons, visited)

    return answer