새싹프로그래머의 이야기

풀이방법:

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

[문제 풀이]

• 두 큐의 합이 같게 되려면 모든 원소의 평균이 정수여야 하며, 각 큐의 합이 평균과 동일하게 만들어주면 됩니다.
• 문제에 대한 설명과 같이, 시간복잡도을 낮추고 큐의 특성을 활용하기 위해 deque()를 사용했으며, 원소의 합이 큰 쪽에서 작은 쪽으로 원소를 보내주도록 구현하였습니다.
• 이때 매번 큐의 합을 구해주는 것이 아닌 구해놓은 합에 대하여 +- 연산을 통해 시간 복잡도를 낮췄습니다.
• 마지막으로 두 개의 큐가 비지 않고 큐의 길이 * 2번 만큼 이동하게 된다면 원 상태가 되므로 해당 조건을 추가하였습니다.

[풀이 코드]

from collections import deque


def solution(queue1, queue2):
    answer = 0
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    s = (sum1 + sum2) / 2

    if s - int(s) > 0 or max(queue1) > int(s) or max(queue2) > int(s):
        return -1

    dq1 = deque(queue1)
    dq2 = deque(queue2)

    while dq1 and dq2 and sum1 != sum2 and answer <= 600000:
        if sum1 < sum2:
            v = dq2.popleft()
            dq1.append(v)

            sum1 += v
            sum2 -= v
        else:
            v = dq1.popleft()
            dq2.append(v)

            sum1 -= v
            sum2 += v
        answer += 1

    return answer if sum1 == sum2 else -1