greentea31's Note

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

풀이 과정

어떤 숫자에서 k개의 수를 제거해서 만들 수 있는 가장 큰 수를 반환하는 문제이다.

위의 예시를 보며 잠시 생각하면 문자열의 앞에서 부터 읽어나가면서 뒤의 문자보다 작을 시, 해당 문자를 제거해주면 문제를 해결할 수 있겠다는 생각이 든다.

1924는 1 < 9 이므로 1 제거, 2 < 4이므로 2 제거, 이런식으로 해결하면 94가 나오고... 1231234는 같은 방식으로 3234, 4177252841은 같은 방식으로 775841이 나온다.

하지만 number="4321", k = 2라면 어떨까? 위의 방법을 아무리 수행해도 어떤 문자도 지워지지 않는다. 실제 답은 "43"이지만 오답 "4321"이 나올 것이다. 따라서 지운 횟수가 k보다 적다면 뒤에서 k - 지운횟수 만큼 문자를 제거해주어야 한다. (문자가 내림차순으로 정렬되어 있을 것이므로 뒤에서 지우는게 무조건 남은 숫자가 큼이 보장된다.)

if string[index] != '9' and int(string[index]) < int(string[index+1]):
    string = string[:index] + string[index+1:]

그런데 위 방법과 같이 실제 문자열 계산을 하며 문자를 제거하면 비효율적 코드로 TLE가 발생해 문제를 해결할 수도 없다. 문자열의 각 문자를 스택에 담으면서 stack top과 새로 들어올 문자를 비교하고 더 큰게 들어오면 pop() 이후 append() 연산을 하는식으로 문자 제거를 처리해주어야 효율적으로 문제를 해결할 수 있다.

소스 코드

def solution(number, k):
    stack = []
    for num in number:
        while stack and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k > 0:
        stack = stack[:-k]
    return ''.join(stack)

https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=python3 

풀이 과정

트리 형태의 전력망이 주어지는데, 전선을 하나 끊어서 두개의 전력망을 만들 때, 두 전력망의 송전탑의 차가 가장 적을 때의 차를 반환하는 문제이다.

위와 같은 전력망은 3-4 or 4-7을 끊으면 각 전력망내 송전탑의 차가 3으로 최소가 된다.

전선을 하나 끊고, 전선의 출발점과 도착점에 대해 BFS로 출발점이 속해 있는 망과 도착점이 속해 있는 망의 송전탑의 차를 모두 구해보면서, 최소인 경우를 반환하도록 하였다.

소스 코드

import collections

def solution(n, wires):
    def bfs(n, start, graph):
        visited = [False for _ in range(n+1)]
        visited[start] = True
        Q = collections.deque([start])
        network = 1
        
        while Q:
            cur = Q.popleft()
            for edge in graph[cur]:
                if not visited[edge]:
                    Q.append(edge)
                    visited[edge] = True
                    network += 1
                    
        return network
    
    graph = collections.defaultdict(set)
    for i, j in wires:
        graph[i].add(j)
        graph[j].add(i)
        
    answer = 101
    
    for vertex in graph:
        for edge in graph[vertex]:
            graph[vertex].remove(edge)
            graph[edge].remove(vertex)
            temp_vertex = bfs(n, vertex, graph)
            temp_edge = bfs(n, edge, graph)
            temp_answer = abs(temp_vertex - temp_edge)
            answer = min(answer, temp_answer)
            graph[vertex].add(edge)
            graph[edge].add(vertex)
    
    return answer

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

풀이 과정

현재 주어진 피로도와, 각 던전 별 입장에 필요한 최소 피로도, 입장시 소모되는 피로도가 주어질 때, 탐험 가능한 최대 던전 수를 구하는 문제이다.

1, 2, 3, 4 던전이 있다 치면 12 13 14 23 24 34 123 124 134 234 1234 모든 경우를 진행시켰다.. 진행 도중 피로도 문제로 진입하지 못하는 던전은 가지치기로 추가 탐색을 중단하였다.

소스 코드

answer = 0

def solution(k, dungeons):
    dungeon_count = len(dungeons)
    visited = [False for _ in range(dungeon_count)]
    def go(index, M, energy, dungeon):
        global answer
        if energy < 0:
            return
        if index > M:
            return
        answer = max(answer, dungeon)
        
        for trys in range(0, M):
            if not visited[trys] and energy - dungeons[trys][0] >= 0:
                visited[trys] = True
                go(index+1, M, energy - dungeons[trys][1], dungeon+1)
                visited[trys] = False
                
                
    go(0, dungeon_count, k, 0)
            
    return answer

https://www.acmicpc.net/problem/11725

풀이 과정

트리가 주어지고, 1번 노드가 루트라고 할 때 각 노드의 부모 노드 번호를 구하는 문제이다.

root 노드인 1번부터 시작해 BFS or DFS를 사용해서 트리를 탐색하고, 각 노드의 부모 노드를 갱신해주면 된다.

소스 코드

import sys
import collections

N = int(sys.stdin.readline())
graph = collections.defaultdict(list)
parent = collections.defaultdict(int)
Q = collections.deque([])
discovered = [False for _ in range(N+1)]

for _ in range(N-1):
    A, B = map(int, sys.stdin.readline().split())
    graph[A].append(B)
    graph[B].append(A)

Q.append(1)

while Q:
    cur = Q.popleft()
    for i in graph[cur]:
        if discovered[i]:
            continue
        parent[i] = cur
        discovered[i] = True
        Q.append(i)

for i in range(2, N+1):
    print(parent[i])

8월 26일날 진행되었던 예선 시험에 합격해, 어제 본선 시험을 치르고 왔다. 신촌 ybm 센터 기준으로 파이썬, c++, 자바의 인원수 비중이 3:2:2쯤 되어보여 파이썬 지원자가 가장 많았다.

1문제당 약 9분 정도의 시간으로 해결해야 했던 예선과는 달리 본선에서는 3문제 180분으로 1문제당 약 60분 내로 해결하면 되었다.... 라기에는 동점자중 순위를 가를때 문제를 빨리 푼 순서, 나이 어린 순서대로 우선순위가 주어지기에 가능한 제출을 빨리하는 것이 유리했다. 3개의 문제가 전부 골드 정도 난이도였다는 생각이 들었는데, 아마 시상식에 참가하려면 3솔은 기본이고 시간 효율적인 코드를 빠르게 제출 완료를 마쳐야 할 것 같다.

나는 풀이 코드 자체는 빠르게 짰었는데 내 코드가 모든 테스트 케이스를 통과할거라는 확신이 들지 않아 테스트 케이스를 여러개 만들어 보고 코드를 점검하느라 코드 제출이 늦은편이었다. 그래도 점검 과정에서 버그를 발견하고 수정해서, 더 빨리 낼 걸! 이런 후회는 들지 않는다.

시험을 마치고 나오니 무려 3만원이 들어있는 스타벅스 기프트 카드를 받았다. 1200원짜리 편의점 커피로만 카페인을 충전하고 있었는데 카드를 받으니 기분이 좋다.... 그래도 순위 안에 들어 시상식에 참가할 수 있으면 더 기분이 좋을 것 같다.

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

풀이 과정

다음과 같이 테두리가 갈색, 나머지 색깔은 노란색인 카펫이 존재한다. 노란색 격자와 갈색 격자의 수가 주어질 때 카펫의 가로 길이와 세로 길이를 구하는 문제이다.

노란색 영역의 가로 길이를 w, 세로 길이를 h라고 하면 갈색 영역은 2*w + 2*h + 4가 된다. 문제 조건에 카펫은 항상 가로 >= 세로 라고 했으므로 가로, 세로 길이를 조정해 가며 입력으로 주어진 갈색 영역의 크기랑 일치한지 확인하면 된다.

brown 24, yellow 24가 주어졌다고 해보자.

가로 세로

 24    1

 12     2

  8     3

  6     4

가 가능하고, 2w + 2h + 4의 값은 위에서 부터 차례대로 54, 32, 26, 24이다. brown이 24이므로 노란색 범위의 가로 길이는 6, 세로 길이는 4임을 알 수 있다.

그러면 테두리가 합쳐질 경우 총 가로 길이는 w + 2, 총 세로 길이는 h + 2가 될 것이므로 이를 답으로 반환해주면 된다.

소스 코드

def solution(brown, yellow):
    answer = []
    for div in range(1, yellow // 2 + 2):
        if yellow % div == 0:
            garo = yellow // div
            sero = div
            if 2 * garo + 2 * sero + 4 == brown:
                return [garo+2 , sero+2]

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

풀이 과정

어떤 과학자가 발표한 논문 중, h번 이상 인용된 논문이 h개 이상이면 그 과학자의 H-index를 h라 한다. 논문의 인용 횟수를 줄테니 H-index를 구하라는 문제이다.

논문 인용 횟수를 내림차순 정렬 후, 1부터 시작하는 논문의 index가 논문 인용 횟수보다 커지는 순간의 바로 이전의 index가 어떤 과학자의 H-index가 된다.

20, 19, 18, 17, 16, 15, 11, 5, 4, 3     논문

1     2    3    4    5   6   7   8  9  10    index

위의 예시를 봤을 때, index 8에서 논문 인용 횟수보다 index가 커지므로 H-index는 7이 된다.

소스 코드

def solution(citations):
    citations.sort(reverse=True)
    index = 1
    answer = 0
    for citation in citations:
        if citation < index:
            return index-1
        index += 1
    return index-1

https://www.acmicpc.net/problem/1916

풀이 과정

N개의 도시, M개의 버스가 주어지고 버스의 출발점과 도착지점, 그리고 드는 버스 비용이 주어질 때, A번째 도시에서 B번째 도시로 가는 경로의 최소 버스 비용을 구하는 문제이다.

https://greentea31.tistory.com/205

이 문제와 비슷한 조건의 문제이다. 똑같이 다익스트라 알고리즘을 구현해서 문제를 해결할 수 있다.

소스 코드

import sys
import heapq
import collections

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = collections.defaultdict(list)
dist = collections.defaultdict(int)

for _ in range(M):
    depart, arrive, cost = map(int, sys.stdin.readline().split())
    graph[depart].append((cost, arrive))

start, end = map(int, sys.stdin.readline().split())

Q = [[0, start]]

while Q:
    cost, node = heapq.heappop(Q)
    if node not in dist:
        dist[node] = cost
        for w, v in graph[node]:
            temp = cost + w
            heapq.heappush(Q, [temp, v])

print(dist[end])

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

풀이 과정

초 단위로 기록된 주식의 가격이 주어질 때, 가격이 떨어지지 않은 기간을 반환하는 문제이다.

문제를 보자마자 생각나는 풀이 방법은 배열의 각각의 원소로부터 시작해 배열의 끝까지 탐색하면서 가격이 언제 떨어지는지 확인하는 2중 for문을 돌리는 O(N^2) 방법일 것이다. 굳이 이 방법으로 코드를 짜서 제출하지는 않았지만 아마 효율성 테스트에서 시간 초과를 발생시킬 것이다.

원소들을 스택에 담으면서 stack top의 가격과 새로 들어오는 원소의 가격을 비교하고, 새로 들어오는 원소의 가격의 숫자가 더 낮으면 stack top에 해당하는 index의 답을 계산해주고 pop하고.. 하는 방식으로 문제를 O(N)으로 해결할 수 있다.

소스 코드

def solution(prices):
    prices = list(enumerate(prices))
    answer = [0 for _ in range(len(prices))]
    stack = []
    for index, price in prices:
        if not stack:
            stack.append((index, price))
            continue
        while stack and stack[-1][1] > price:
            answer[stack[-1][0]] = index - stack[-1][0]
            stack.pop()
        stack.append((index, price))
    while stack:
        answer[stack[-1][0]] = len(answer) - 1 - stack[-1][0]
        stack.pop()
    return answer

트라이란?

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조.

최대 20개의 알파벳을 갖는 10000개의 문자열이 있다고 가정할때 일반 배열에 문자열을 저장할 시, 특정 문자열의 존재여부 판단은 10000번의 연산이 필요하다. 하지만 Trie에 저장할 시 20번 안팎의 연산으로 문자열의 존재여부 판단이 가능하다. 트라이의 예시는 아래의 그림과 같다.

["A", "to", "tea", "ted", "ten", "i", "in", "inn"] 을 키로 둔 트라이의 예시이다. 동일한 키를 배열에 담고 "tea"의 존재 여부를 판단하려 했다면 최악의 경우 8번의 연산이 필요하지만 트라이에서는 문자열의 길이만큼의 연산으로 존재 여부가 판단이 가능하다.

트라이 예시 문제

https://leetcode.com/problems/implement-trie-prefix-tree/

트라이를 구현해보는 문제가 리트코드에 있으니 풀어보면서 익히면 좋다.

정답 코드는 아래와 같다.

class TrieNode:
    def __init__(self):
        self.word = False
        self.children = collections.defaultdict(TrieNode)
        

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children[char]
        node.word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True