문제 출처: 백준 온라인 저지

문제 설명

🔎상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

캔디크러쉬를 구현하라는 문제였다.

사진같은 게임판이 주어졌을 때, 딱 한번 인접한 칸 끼리 교체할 수 있을 때 같은 문자가 나타나는 열 또는 행이 최대가 되는 방법을 도출하라는 것이다.

구현을 바탕으로 한 문제지만 문제 분류도 그렇고 결국은 브루트 포스로 접근해야하는 문제였다.

<정답 코드>

def candy_count(x, y):
    global n
    ea_x, ea_y = 1, 1
    cur = candy[x][y]

    for ny in range(y+1, n):
        if candy[x][ny] == cur:
            ea_y += 1
        else:
            break

    for py in range(y-1, -1, -1):
        if candy[x][py] == cur:
            ea_y += 1
        else:
            break

    for nx in range(x+1, n):
        if candy[nx][y] == cur:
            ea_x += 1
        else:
            break

    for px in range(x-1, -1, -1):
        if candy[px][y] == cur:
            ea_x += 1
        else:
            break

    return max(ea_x, ea_y)



n = int(input())
candy = [list(input()) for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
ans = 0

for x in range(n):
    for y in range(n):
        ans = max(ans, candy_count(x,y))
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0 <= nx < n) and (0 <= ny < n) and candy[x][y] != candy[nx][ny]:
                candy[x][y], candy[nx][ny] = candy[nx][ny], candy[x][y]
                ans = max(ans, candy_count(x, y))
                candy[x][y], candy[nx][ny] = candy[nx][ny], candy[x][y]

print(ans)

브루트포스 문제의 특성인건지 아니면 내가 정말 코드를 너무 못짜서 그런건지, 지저분하게 답이 나왔다.

접근 방법은 아래와 같다.

1. 입력을 2차원 리스트를 통해 게임보드처럼 생성한다.

2. 반복문을 통해 모든 칸을 순회한다.

3. 각 칸을 순회할 때 주변의 사탕 수를 count한다. 

    3-1. count는 candy_count함수를 통해 이루어진다.

    3-2. candy_count함수는 상하좌우를 모두 순회해 사탕의 행, 열 중 더 많은 사탕의 수를 반환한다.

4. 각 칸에서 인접한 모든 칸에 대해 이동할 수 있고, 원래 칸과 다른 사탕일 때만 스왑한다.

5. 스왑한 후에 candy_count를 한번 더 수행한다.

candy_count함수의 경우는 투포인터나 재귀를 통해 좀 더 간략하게 구현할 수 있었을 것 같다.

브루트포스 문제는 보통 각오로 덤빌 수 있는 문제는 아닌 것 같다. 시간 복잡도도 고려해야하고, 구현 자체도 복잡하고, 코드도 길어져서 한번 틀리면 디버깅하는게 힘든 것 같다.

문제 출처: 백준 온라인 저지

문제 설명

🔎왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

리스트의 길이가 9로 고정된 비교적 간단한 브루트포스 문제였다. 7명의 키의 합이 100이 되는 경우 중 한가지만 출력하면 된다.

7명을 선택하는 방법은 $$ _{9}\mathrm{C}_{7} $$ 로 36가지만 검토하면 되므로 Combination(조합)을 이용해서 풀어도 시간 제약에 걸리지 않고 통과할 것이다.

코딩 테스트 도중이라면 위 방법이 먹힘을 확인하고 바로 넘어갔겠지만, 통과하지 못하는 시간 제약이 있을 수도 있어 stack을 이용한 풀이까지 해서 총 2가지 방법으로 풀어보았다.

<정답 코드1>

import sys
from itertools import combinations
inp = sys.stdin.readline

heights = []
for _ in range(9):
    heights.append(int(inp()))

heights.sort()

kinds = list(combinations(heights, 7))

for i in kinds:
    if sum(i) == 100:
        print(*i, sep='\n')
        break

우선은 조합을 이용한 풀이다.

itertools에서 제공하는 combinations를 활용해 가능한 모든 조합을 도출하고, 조합 안에서 합이 100인 리스트가 존재하면 출력하고 종료하는 것으로 매우 간단한 코드다.

<정답 코드2>

import sys
inp = sys.stdin.readline

heights = []
for _ in range(9):
    heights.append(int(inp()))

heights.sort()

for i in range(9):
    for j in range(i, 9):
        if sum(heights) - (heights[i]+heights[j]) == 100:
            heights.pop(j)
            heights.pop(i)
            print(*heights, sep='\n')
            exit()

반복문을 통해 조합을 구현하되, 7명이 아닌 2명을 선택하고, 최악의 경우는 모든 조합을 검토하지만 최선의 경우에는 한번만 점검해도 답이 도출된다는 점에서 combinations보다 빠를 것으로 기대된다.

접근방법은 아래와 같다.

1. 출력이 오름차순으로 되어야하므로 미리 정렬시켜놓는다.

2. 이중 반복문을 통해 2명을 선택할 수 있는 모든 경우의 수를 순회한다.

3. 순회 도중 합이 100임을 만족하는 선택지가 있으면 해당 2명을 pop한 후 프로그램을 종료한다.

문제만 차분히 읽는다면 충분히 빠른 시간 안에 해결할 수 있는 문제였다.

문제 출처: 프로그래머스

문제 설명

🔎정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

달팽이가 삼각형을 그리면서 한칸씩 이동할 때 발자취를 남기는 문제다.

해당 문제는 어떤 특별한 자료구조를 사용하기 보다 어떻게 구현할 것이냐가 중요한 문제였다.

처음에는 새로운 삼각형 시작의 상관성을 찾아서 문제를 쉽게 해볼려고 노력했었다. (ex. n=4일 때, 다음 삼각형은 10에서 시작, n=5일 때는 13일 때 시작..)

하지만 늘 그렇듯 이렇게 생각하는게 오히려 더 복잡하게 돌아가는 방법이었고, 그냥 단순무식하게 코딩을 하는게 더 빠르게 답을 도출할 것 같다 생각이 들었고, 실제로 그랬다.

<정답 코드>

def solution(n):
    answer = [[0]*i for i in range(1, n+1)]
    dx = 0
    x, y = 0, 0
    cur = 1
    
    while n:
        if dx == 0:
            for i in range(n):
                answer[x][y] = cur
                cur += 1
                x += 1
            x, y = x-1, y+1
            dx = 1
            
        elif dx == 1:
            for i in range(n):
                answer[x][y] = cur
                cur += 1
                y += 1
            y -= 1
            dx = 2
        
        else:
            for i in range(n):
                x, y = x-1, y-1
                answer[x][y] = cur
                cur += 1
            x += 1
            dx = 0
        
        n -= 1
            
    ans = []
    for i in answer:
        ans.extend(i)
        
    return ans

결과적으로 코드가 아주 너저분하게 됐지만, 통과는 하였다.

접근 방법은 아래와 같다.

1. 피라미드 형식의 2차원 리스트를 생성한다.

2. 달팽이의 진행 방향을 결정하는 dx와 칸을 이동할 때 마다 증가하는 cur 변수를 통해 기록을 진행한다.

3. 달팽이가 한 방향으로 진행할 때 마다 전진 횟수가 줄어드는데 이는 n을 통해 기록한다.

4. 달팽이를 진행시키면서 기록한다.

5. 결과로 나온 2차원 리스트를 1차원 형식으로 변경한다.

달팽이는 사진처럼 이동한다.

dx = 0일 때 좌하향, dx = 1일 때 우향, dx = 2일 때 좌상향한다.

한 방향으로 진행이 끝나면 다음 방향으로 진행 횟수가 1 감소한다. (최초 진행횟수는 피라미드의 높이인 n과 같다.)

for문을 통해 해당 사항을 구현하면 최후의 좌표가 도착해야할 좌표보다 1 커지기 때문에 해당 진행 방향으로 1 감소시켜주는게 중요하다.

코딩 테스트는 참 컨디션에 영향을 많이 받는 것 같다. 어떤 날은 복잡한 문제가 더 잘 풀리고, 어떤 날은 간단한 문제가 잘 풀리고.. 기복이 없이 조절하는 것이 앞으로의 과제인 것 같다.

문제 출처: 백준 온라인 저지 13023 ABCDE

문제 설명

🔎BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

(문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.)

위 그림에서 나타난 것 처럼, 주어진 여러 관계 속에서 A➡B➡C➡D➡E 로 이어지는 관계가 존재하는지 묻는 문제이다.

해당 관계가 몇번이 나타나는지는 상관없이 하나라도 존재하면 1, 하나도 존재하지 않는다면 0을 출력한다.

문제를 읽기만 했을 때는 그래프 문제라고 파악하기 힘들지만, 주어진 예제들을 통해 그래프 탐색을 통해 문제를 해결해야하는 것을 확인할 수 있다.

<정답 코드>

def dfs(cur, depth=0):
    if depth == 4:
        return True

    visit[cur] = True

    for nx in relation[cur]:
        if not visit[nx]:
            flag = dfs(nx, depth+1)
            if flag:
                return True

    visit[cur] = False
    return False


n, m = map(int, input().split())
relation = [[] for _ in range(n)]
ans = 0
for _ in range(m):
    v, w = map(int, input().split())
    relation[v].append(w)
    relation[w].append(v)


for i in range(n):
    visit = [False] * n
    ans = dfs(i)
    if ans:
        break

print(int(ans))

한번만 관계를 확인하면 되기에 flag와 DFS를 활용해 문제를 풀이하였다.

접근은 아래와 같다.

1. 입력을 2차원 리스트에 그래프형태로 저장한다.

2. 그래프를 dfs를 통해 순회한다. dfs를 수행할 때는 depth 인자를 주어 depth가 4가 되면 탈출하게 작성하였다.

3. depth가 4일 때만 True를 반환하여 flag를 변경해주었고, flag가 True가 되면 True를 반환하며 탈출한다.

dfs의 특성을 통해 깊이 = 관계의 깊이로 생각하여 문제를 풀었다.

주의해야할 점은 탐색에 실패하였을 때 visit[cur]을 False로 바꾸어 다음 진행에 차질이 생기지 않도록 하는 것이다.

문제 출처: 프로그래머스 ( https://school.programmers.co.kr/learn/courses/30/lessons/49189 )

문제 설명

🔎n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항
1. 노드의 개수 n은 2 이상 20,000 이하입니다.
2. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
3. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

해당 문제는 전형적인 그래프 최단거리를 구하는 문제로, bfs를 사용할 줄 알면 간단하게 풀 수 있는 문제이다.

다만, 문제의 설명에 연결되지 않은 1번 노드에 연결되지 않은 노드가 존재할 수 있다는 문구가 있었으면 조금 더 좋았을 것 같다.

<정답 코드>

from collections import deque
def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    for start, end in edge:
        graph[start].append(end)
        graph[end].append(start)
    
    dist = [float('inf')] * (n+1)
    visited = [False] * (n+1)
    
    dist[1] = 0
    q = deque()
    q.append(1)
    while q:
        cur = q.popleft()
        if visited[cur]:
            continue
        
        visited[cur] = True
        
        for x in graph[cur]:
            if dist[x] > dist[cur] + 1:
                dist[x] = dist[cur] + 1
                q.append(x)
                

    target = 0
    for i in dist[1:]:
        if i != float('inf') and target < i:
            target = i
    
    answer = dist.count(target)
    
    
    return answer

접근 방법은 아래와 같다.

1. 주어진 파라미터를 통해 그래프를 생성한다.

2. 1번 노드를 출발점으로 지정하여, 그래프를 탐색한다. 탐색한 깊이에 따라 거리를 업데이트 해준다.

3. 거리 리스트에서 inf가 아닌 최대 값을 도출하고 이것을 count한다.

처음에는 max(dist)를 target으로 설정하고 진행하였다. 하지만 테스트 2번 예시를 통해 앞서 언급한 방문 불가 노드가 있다는 사실을 깨닫고 위와 같이 수정하였다.

<테스트 2>

문제 출처: 프로그래머스 (https://school.programmers.co.kr/learn/courses/30/lessons/42861)

문제 설명

🔎n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항
1. 섬의 개수 n은 1 이상 100 이하입니다.
2. costs의 길이는 ((n-1) * n) / 2이하입니다.
3. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
4.같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
5. 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
6. 연결할 수 없는 섬은 주어지지 않습니다.

해당 문제는 프로그래머스의 코딩 테스트 고득점 kit에 있는 문제다.

섬, 연결, 최소 비용이라는 단어를 보자마자 bfs, 다익스트라 등을 생각했고 실제 바로 그리디한 방법이 떠오르지 않아 다익스트라로 먼저 시도했었다.

<틀린 코드 보기>

from queue import PriorityQueue
# 다익스트라 x
def solution(n, costs):
    answer = 0
    island = [[] for _ in range(n)]

    for e1, e2, w in costs:
        island[e1].append((e2, w))
        island[e2].append((e1, w))

    visited = [False] * (n+1)
    dist = [float('inf')] * (n+1)
    q = PriorityQueue()
    q.put((0, 0)) # 최단거리, 노드번호
    dist[0] = 0
    bridge = [0] * (n+1)
    while q.qsize()>0:
        cur_node = q.get()[1]
        if visited[cur_node]: continue

        visited[cur_node] = True

        for nx, val in island[cur_node]:
            if dist[nx] > dist[cur_node] + val:
                dist[nx] = dist[cur_node] + val
                bridge[nx] = val
                q.put((dist[nx], nx))

    print(dist)
    print(bridge)

다익스트라를 통한 구현의 문제점은 아래와 같다.

1. 결국은 모든 costs에 대한 점검을 해야한다.

2. 다익스트라로 구현된 dist 리스트는 시작점부터 해당 노드까지의 비용으로 산정되기 때문에 sum으로 답을 구할 수 없다.

제한 사항에서 섬의 개수(n)은 100이하라고 했고, costs의 길이는 ((n-1) * n) / 2 이라 규정하였으므로, 실제 costs를 전체 도는데만 해도 O(n²) 만큼의 시간이 들기 때문에 1번 문제점은 꽤나 크게 작용하였다.

이후 이 문제가 그리디로 분류되었다는 사실을 다시 한번 깨닫고 아래와 같은 코드를 작성하였다.

<정답 코드>

from collections import deque
def solution(n, costs):
    answer = 0
    costs = sorted(costs, key=lambda x: x[2])
    isl = [[] for _ in range(n)]

    
    for start, end, cost in costs:
        q = deque()
        flag = False
        q.append(start)
        visit = [False] * n
        visit[start] = True
        while q:
            a = q.popleft()
            if a == end:
                visit[a] = True
                flag = True
                break
            
            visit[a] = True
            for i in isl[a]:
                if not visit[i]:
                    q.append(i)
        
        if sum(visit) == n:
            break
        
        if not flag:
            isl[start].append(end)
            isl[end].append(start)
            answer += cost
    
    return answer

접근 방법은 아래와 같다.

1. 가장 낮은 비용의 다리부터 우선적으로 고려한다. (비용을 기준으로 costs를 정렬한다.)

2. 비용을 기준으로 정렬된 costs를 순회하면서, 연결되지 않은 섬에 대해서만 다리를 건설한다.

3. 모든 섬을 방문할 수 있게 되었으면 반복문을 탈출하게 한다.

연결되지 않은 섬을 판단하는 알고리즘으로는 bfs를 사용하였다. 

bfs를 채택할 수 있었던 것은, 다리를 하나씩 건설하기 때문에 bfs를 통한 연산 횟수가 0에서 부터 지수적으로 상승한다는 사실 때문이다.

해당 섬과 연결이 되었는가에 대한 판단은 flag를 통해 진행하였고, 만약 모든 섬을 방문할 수 있게 되었다면 반복문을 탈출하는 것으로 마무리 지었다. 이 부분이 다익스트라에서 모든 costs를 점검해야한다는 부분을 해소할 수 있게 해주었다.

사실 이 문제는 수개월 전에 먼저 도전했다가 실패한 문제이다. 최근에는 그래프나 트리 문제를 많이 풀지 않고 DP와 브루트포스 문제를 많이 풀어 해당 문제를 푸는데 도움이 되었던 것 같다.

문제 출처: 백준 온라인 저지 (https://www.acmicpc.net/problem/1932)

문제 설명

🔎위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

처음 문제 예시만 봤을 땐 포화 이진트리나 힙을 생각하게 만드는 문제였다.

하지만 문제를 잘 읽어보면 이진트리 방식으로 수를 선택하면서 내려왔을 때 최대가 되는 수를 출력하는 다이나믹 프로그래밍 문제였다.

<정답코드>

import sys
input = sys.stdin.readline

n = int(input())
tree = []

for i in range(n):
    inp = list(map(int, input().split()))
    if i == 0:
        tree.append(inp)
        continue
    elif i == 1:
        tree.append(list(map(lambda x: x+tree[0][0], inp)))
        continue

    inp[0] += tree[-1][0]
    inp[-1] += tree[-1][-1]

    for j in range(1, len(inp)-1):
        inp[j] += max(tree[-1][j-1], tree[-1][j])

    tree.append(inp)

print(max(tree[-1]))

접근은 아래와 같다.

1. 리스트로 입력을 받아 2차원 리스트 형태로 저장한다.

2. 리스트에 저장하기 전, 각 원소에 대한 부모 노드 중 더 큰 값을 더하여 저장한다.

3. 0번째 리스트는 원래 값 그대로 저장하고, 1번째 리스트는 0번째 리스트의 값만 부모로 갖는다.

트리 구조에 대한 이해만 있다면 쉽게 풀 수 있었던 문제였던 것 같다.

문제 출처: 프로그래머스 (https://school.programmers.co.kr/learn/courses/30/lessons/42884#)

문제 설명

🔎고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

처음 문제를 접했을 때는 완전탐색인가?라고 생각했었다. (아마 DP문제를 계속 풀다와서 그런 것 같다.)

첫 시도로 defaultdict로 모든 경로에 대해 방문하는 차량의 대수를 기록하여 문제 풀이를 시도했다.

<틀린코드 보기>

from collections import defaultdict
def solution(routes):
    answer = 0
    routes.sort()
    road = defaultdict(int)
    
    for enter, out in routes:
    	for i in range(enter, out+1):
        	road[i] += 1
    
    start = list(road.keys())[0]
    end = list(road.keys())[-1]
    cur = start
    rec = 0
    
    while cur < end:
    	answer += 1
    	rec = road[cur]
        while rec == road[cur]:
        	cur += 1
            
    return answer

다시 살펴보니 틀린 코드는 여기 올리기 민망할 정도로 논리가 안맞는 수준이었다. 점검을 위해 돌렸을 때 대부분의 케이스에서 시간 초과가 발생하였고, 제대로 돌아간 3개 조차 실패로 나왔다.

패착은 이렇다.

1. 방문한 전체 길이의 경로를 탐색하므로 인해 연산이 지나치게 많이 발생하였다.

2. 방문과 탐색을 따로 진행함으로 인해 연산이 두배정도 증가하였다.

3. 해당 도로의 방문 차량 숫자가 달라지는 것과 CCTV 수는 항상 관련이 있는 것은 아니다.

나의 잘못된 버릇이 항상 그렇듯 문제를 너무 꼬아 생각하게 되는 것을 하루 빨리 고쳐야 실력 향상에 도움이 될 것 같다..

정답은 다음과 같다.

<정답 코드>

from collections import deque
def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[1])
    q = deque(routes)
    
    while q:
        enter, out = q.popleft()
        answer += 1
        while q and q[0][0] <= out:
            q.popleft()

    return answer

이전에 짰던 코드보다 훨씬 간결하게 답안을 작성할 수 있는 것이었다.

접근은 아래와 같다.

1. 주어진 route에 대해, 먼저 나가는 차량들을 기준으로 정렬한다. 

2. 정렬된 리스트를 queue형식으로 변경한다.

3. queue에서 차량경로를 하나씩 꺼낸 후, 해당 경로 상 임의의 위치에 CCTV 하나를 배치한다 가정하고, 해당 경로 안에서 출발을 하는 차량들을 모두 pop해준다.

처음엔 나가는 차량을 기준으로 정렬을 하는게 아닌, 출입하는 차량을 기준으로 정렬을 해야한다고 생각했다.

이와 같이 생각한 이유는, 먼저 출발한 차량이 탈출하기 전에 있었던 모든 차량들을 pop해야한다고 생각했기 때문이다.

하지만 이런 접근이 틀린 이유는 가장 먼저 출발한 차량이 가장 나중에 탈출하는 경우가 있다면, CCTV 대수는 1대로 출력되기 때문이다. (그리고 가장 먼저 탈출하는 차량을 기준으로 정렬해야한다는 사실을 3시간 만에 떠올렸다...)

그리디 문제를 풀 때 가끔씩 드는 생각이지만 해당 코드가 항상 정답을 배출하는 코드일까?라는 의문이 아직까지 남아있지만, 그렇다할 반례를 아직 못찾았다. 반례를 찾게 된다면 추가로 업로드 해야겠다.