greentea31's Note

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

풀이 과정

여러개의 사각형이 주어질 때, 시작점에서 도착지점까지 사각형의 모서리만 타고 이동할 때의 최소 이동 횟수를 구하는 문제이다.

문제에서 주어진 예시와 같이 사각형의 내부는 방문할 수 없다.

입력값을 확인하면서 사각형의 모서리는 board값 1, 사각형 내부는 2, 내부와 모서리가 겹치는 경우는 내부가 우선해서 모서리 처리 안되게끔 board값을 처리하고 이동 가중치가 전부 1이니까 BFS로 board를 탐색하면서 최소 이동 거리를 구하면 답이 나올 것 같다. 하지만 이렇게 해결시 몇몇 테스트 케이스에서 오류가 발생한다.

위의 그림에서 (x, y) = (3, 5)인 지점을 보자. (4, 5)도 방문이 가능하지만 (3, 6)도 거리가 1만큼 떨어저 있고 사각형의 모서리에 해당하므로 방문이 가능하다고 판단해서 방문해버린다. 실제로는 (3, 6)을 방문하려면 (4, 5), (4, 6)을 먼저 방문해야 함에도 불구하고 말이다.

ㄷ자 모양의 모서리부분이 존재할 시, 바로 방문 불가능한 점을 방문이 가능하다고 처리하는 문제가 발생하는 것이다. 가장 간단한 해결방법은 좌표계를 2배 확대해서 보는 것이다. (1, 1)과 (1, 2) 사이에 2칸이 있다고 생각하는 것이다.

좌표계를 2배로 잡아서 보고 시작점, 도착지점 다 2배씩 해준 다음에 마지막에 구한 최소 이동 횟수도 2로 나눠주면 ㄷ자 모양의 모서리에서도 오류가 발생하지 않고 정상적으로 답을 구할 수 있다.

소스 코드

import collections

def solution(rectangle, characterX, characterY, itemX, itemY):
    board = [[0 for _ in range(102)] for _ in range(102)]
    for rec in rectangle:
        a, b, c, d = rec
        a *= 2; b *= 2; c *= 2; d *= 2
        for y in range(b, d+1):
            for x in range(a, c+1):
                if board[y][x] == 2:
                    continue
                if y == b or y == d or x == a or x == c:
                    board[y][x] = 1
                else:
                    board[y][x] = 2
    
    def bfs(start_y, start_x):
        dy = [0, 1, 0, -1]
        dx = [1, 0, -1, 0]
        discovered = [[False for _ in range(102)] for _ in range(102)]
        Q = collections.deque()
        Q.append([start_y, start_x, 0])
        discovered[start_y][start_x] = True
        
        while Q:
            cur_y, cur_x, dist = Q.popleft()
            if cur_y == itemY*2 and cur_x == itemX*2:
                return dist // 2
            for i in range(4):
                ny = cur_y + dy[i]
                nx = cur_x + dx[i]
                if 1 <= ny <= 100 and 1 <= nx <= 100 and board[ny][nx] == 1 and not discovered[ny][nx]:
                    Q.append([ny, nx, dist+1])
                    discovered[ny][nx] = True
        
    answer = bfs(characterY*2, characterX*2)
    return answer

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

풀이 과정

ICN에서 시작해 주어진 비행기 표를 모두 사용하는 여행 경로를 짜는 문제이다. 가능한 경로가 여러개라면 사전식으로 앞선 경로를 답으로 내야 한다.

모든 도시를 방문할 수 없는 입력은 들어오지 않으므로 모든 도시를 DFS로 방문하면 된다. 비행기 표를 defaultdict에 담아놓는데, pop으로 비행기표를 꺼내면서 알파벳 순이 앞선 도시를 먼저 방문하기 위해 티켓 리스트를 도착지를 기준으로 알파벳 내림차순으로 정렬해놓고 defaultdict에 담았다.

https://greentea31.tistory.com/202

LeetCode의 332번 문제와 아주 유사한 문제이고 풀이도 유사하게 하면 된다.

소스 코드

import collections

def solution(tickets):
    answer = []
    ticket_list = collections.defaultdict(list)
    tickets.sort(key=lambda x: x[1], reverse=True)
    
    for depart, arrive in tickets:
        ticket_list[depart].append(arrive)
    
    print(ticket_list)
        
    def dfs(go):
        while ticket_list[go]:
            dfs(ticket_list[go].pop())
        answer.append(go)  # 재귀를 사용해 여행순서가 반대 순서대로 answer에 저장된다.
        
    dfs('ICN')
    return answer[::-1]  # 그래서 반대로 출력해주어야 한다.

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

풀이 과정

words 배열에 있는 단어 중, 현재 단어와 한 글자 차이 나는 단어로 이동이 가능하다고 할 때, begin에서 target까지 가는 가장 짧은 변환 과정을 구하는 문제이다. 변환이 불가능하면 0을 출력하면 된다.

이동 가능한 단어간의 거리는 1, 구해야 하는 것은 가장 짧은 경로.... 문제를 읽다보면 BFS가 바로 떠오른다. 이미 방문한 적이 있는 단어는 방문하지 않게끔 처리하면서 BFS로 단어들을 탐색하면서 거리를 측정하면 된다. 각 단어는 노드, 한 글자씩 차이나는 단어 노드들간에 간선이 존재하는 그래프로 생각할 수 있다.

어떤 진행 경로에서 방문하지 않았던 단어여도, 다른 진행 경로에서 방문한 단어면 방문 할 필요가 없다. 예를 들어 cat -> cot 경로가 존재하고 cat -> cet 경로에서 다음 단어를 찾는다고 가정해보자. BFS 진행 중, cat -> cet -> cot로 방문이 가능해야 하지만 어차피 이건 cat -> cot 경로보다 정답에 도달하는게 무조건 느리다. 따라서 방문을 할 필요가 없고, 다른 경로에서 이미 방문한 단어이므로 방문 불가능 처리를 해주면 된다. 즉, 경로마다 각자의 진행 경로를 저장할 필요 없이 어떤 경로에서든 이미 방문한 단어 노드이면 방문이 불가능하다고 생각해야 필요없는 경로를 구성하지 않으면서 답을 구할 수 있다.

소스 코드

import collections


discovered = []

def solution(begin, target, words):
    def transferable(a, b):
        same_char = 0
        length = len(a)
        for i in range(length):
            if a[i] == b[i]:
                same_char += 1
        if same_char == length-1:
            return True
        else:
            return False
    
    def bfs(start, words):
        Q = collections.deque()
        Q.append([start, 0])
        discovered = [False for _ in range(len(words))]
        
        while Q:
            cur_word, dist = Q.popleft()
            print(f'cur_word: {cur_word}, dist: {dist}')
            if cur_word == target:
                return dist
            for index, word in enumerate(words):
                if discovered[index]:
                    continue
                if not transferable(cur_word, word):
                    continue
                discovered[index] = True
                Q.append([word, dist+1])
        
        return 0
        
    
    if transferable(begin, target):
        return 1
    
    answer = bfs(begin, words)
    
    return answer

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

풀이 과정

상하좌우로 이동 가능한 좌표계에서, 통과 가능한 공간과 통과 불가능한 벽이 주어질 때, 시작점 (1, 1)에서 도착점 (n, m)까지 경로의 최단 거리를 구하는 문제이다.

문제의 예시에서 보이듯이, 위처럼 지도가 주어지면 최단 경로의 길이는 11이 된다.

좌표간의 가중치가 존재하지 않으므로 그냥 BFS를 돌려서 최단거리를 구하면 된다.

파이썬에서 BFS를 구현 시, 이미 접근한 좌표를 discovered 배열에 넣는, 예를 들어 discovered = [] 상태에서 [1, 1] 방문시 discovered.append([1, 1])로 좌표를 넣어주고 BFS로 진행할 좌표를 찾을 때 not in discovered 조건으로 구현하는 경우가 있다. 그러나 이 문제에서는 효율성 테스트에서 시간 초과가 발생할 것이다. set이나 dictionary 자료형이 아니면 in이나 not in으로 자료형을 탐색하는 연산의 시간복잡도는 O(N)이 된다.

이 문제 같은 경우에는 이미 방문한 점을 map에서 2로 바꿔준다거나 하는 방법으로 해결이 가능하다. 별도의 discovered 리스트로 방문 점을 판별하고 싶다면 discovered = [[0 for _ in range(m)] for _ in range(n)] 과 같이 별도의 방문점을 판별하는 2차원 배열을 선언후 값을 바꿔주어야 방문 가능 판단 연산이 O(1)이 된다.

소스 코드

import collections

def solution(maps):
    def bfs(maps, n, m):
        Q = collections.deque()
        Q.append([0, 0, 1])
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        
        while Q:
            cur_y, cur_x, dist = Q.popleft()
            for i in range(4):
                ny = cur_y + dy[i]
                nx = cur_x + dx[i]
                ndist = dist + 1
                if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == 1:
                    Q.append([ny, nx, ndist])
                    maps[ny][nx] = 2
                    if ny == n-1 and nx == m-1:
                        return ndist
        
        return -1
                
            
    answer = bfs(maps, len(maps), len(maps[0]))
    return answer

# discovered = [] 와 in으로 방문 여부 판단하면 in이 O(N)이라서 시간초과가 발생한다.

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

풀이 과정

A로만 이루어져 있는 글자가 주어질 때, 원하는 문자열로 바꾸려면 조이스틱을 몇 번 조작해야 하는지 구하는 문제이다.

위의 예시를 읽으면서 생각해보면 조이스틱을 위나 아래로 몇 번 조작해야 하는지는 구하기가 간단할 것 같다. A는 0, B는 1, C는 2, ... M은 12, N은 다시 12, O는 11 ... Z는 1번 조이스틱을 조작해서 만들 수 있다.

문자열의 문자를 읽으면서 각 문자에 대응하는 숫자를 조이스틱의 이동 횟수에 더해주면 위, 아래 조작수는 전부 답에 더해진다. 하지만 왼쪽, 오른쪽 조작은 몇 번 해야할까? 문자열의 길이만큼 조작한다고 하기엔 BBAAA는 좌우 이동이 오른쪽으로 한번만 필요한 문자이다.

펜대를 굴려가며 여러 예시를 쓰면서 생각해보면 결국 가장 긴 연속된 A 문자열을 지나가지 않도록 좌우 이동을 해야 최소 이동횟수가 나오겠다는 생각이 든다. 그러면 가능한 최소 경우는 아래와 같다.

1. 그냥 문자열의 길이 - 1 만큼 좌우 이동을 해야하는 경우

ex) BABAB -> 모든 B를 A로 바꿔주려면 결국 4번 이동해야 한다. 다른 방법은 존재하지 않는다.

2. 왼쪽으로 진행하다 꺾어서 오른쪽으로 진행

ex) ABBBBAAAB -> 왼쪽으로 한번 진행후 B를 A로 바꿔준 뒤, 오른쪽으로 가면서 모든 B를 A로 바꿔주는게 최소 경우이다. 좌우 이동횟수 6번이 최소 횟수이다. 문자열의 길이 - 1 = 8보다 적게 이동이 가능함을 알 수 있다. 가장 긴 연속된 A 문자열 AAA 안쪽은 굳이 지나갈 필요가 없기 때문이다.

3. 오른쪽으로 진행하다 왼쪽으로 꺾어서 진행

2번과 비슷한 예시를 생각해볼 수 있다.

소스 코드

def solution(name):
    answer = 0
    minimum_move = len(name) - 1
    
    for i, char in enumerate(name):
    	# 상하 최소 조작 횟수를 구하는 부분
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        nxt = i + 1
        
        while nxt < len(name) and name[nxt] == 'A':
            nxt += 1
            
        # 좌우 최소 이동횟수를 구하는 부분          
        minimum_move = min([minimum_move, 2 *i + len(name) - nxt, i + 2 * (len(name) - nxt)])
        
    answer += minimum_move
    return answer

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

풀이 과정

limit의 무게 제한이 있는 2인용 구명보트에 임의의 무게를 가진 사람들을 모두 태우고 나가려면 구명보트가 몇 대가 있어야 하는지 구하는 문제이다.

투 포인터를 이용하여 문제를 쉽게 해결할 수 있다. 무게 배열을 오름차순으로 정렬하고, left 포인터를 0, right 포인터를 오른쪽 끝에 위치시키자.

people[left] + people[right]가 limit를 넘으면 people[right]는 배열 내의 어떤 사람이랑 짝을 지어도 무조건 limit를 넘게 된다. (정렬했으므로 people[left]가 무조건 최소 무게 사람) 따라서 right번째 있는 사람은 무조건 배를 혼자 타야 하므로 right 포인터를 1 감소시키고, 사용한 배의 횟수를 1 증가시켜주면 된다.

people[left] + people[right]가 limit를 넘지 않는다면, 2명이서 배를 탈 수 있으므로, left 포인터 증가, right 포인터 감소, 사용한 배의 횟수를 1 증가시켜주면 된다. 

첫번째 입출력 예시에 위의 알고리즘을 적용한다면

people.sort() -> [50, 50, 70, 80]

1. 50 + 80 안되므로 80kg 혼자 배에 태우고 right -= 1

2. 50 + 70 안되므로 70kg 혼자 배에 태우고 right -= 1

3. 50 + 50 가능하므로 둘이 배에 태우고 left += 1, right -= 1

4. left, right가 교차했으므로 -> 모든 사람이 배에 탔으므로 사용한 배의 횟수 출력

순으로 돌아갈 것이다.

소스 코드

def solution(people, limit):
    people.sort()
    answer = 0
    left = 0
    right = len(people) - 1
    
    while left < right:
        if people[left] + people[right] <= limit:
            answer += 1
            left += 1
            right -= 1
        else:
            right -= 1
            answer += 1
    
    if left == right:
        answer += 1
    
    return answer

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://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]