친절한 도현씨 친절한 도현씨

※ 접근법 옥상의 개수가 최대 팔만 개였기 때문에 단순 이중 for 문을 돌면 시간 초과가 발생할 것이라고 생각을 했다. 높이를 정렬을 하면 안 됐기 때문에 느낌상 스택을 사용해야 할 것 같았다. ※ 풀이 생각의 전환이 필요한 문제이다. 내가 바라볼 수 있는 옥상 정원의 개수가 아니라 나를 바라보는 옥상의 개수를 구하는 것이다. 1. stack이 아니라 단순 스택이라고 불리는 내림차순, 올림차순을 유지하는 stack을 만드는 것이다. 2. 10, 3, 7, 4, 12, 2라고 했을 때 10은 일단 stack에 넣는다. [10] 10은 맨 왼쪽에 있기 때문에 바라볼 수 있는 옥상이 없다. 3. [10,3]은 3을 바라볼 수 있는 옥상 10이 있기에 len(stack) - 1(자기 자신을 바라볼 수 없으니)..

※ 접근법 주사위 갯수가 최대 만 개였지만 따져야할 주사위 면에 주사위 숫자는 1~6으로 고정돼 있었기 때문에 경위의 수가 많지 않다고 생각해 문제에서 시키는 대로 구현하면 풀릴 것이라고 생각했다. ※ 풀이 (전체적인 관점 : 주사위 윗면 아랫면에 4,5,6이 없다면 옆면으로는 계속 회전시킬 수 있기 때문에 어떻게든 최대인 기둥이 만들어진다. 그렇다면 윗면 아랫면에 6 or 5 or 4가 없는지 확인하고 없다면 elif문으로 걸러서 제일 큰 숫자를 더해준다. 1. 첫 번째 주사위에 윗면을 담당할 숫자는 1~6까지가 있다. 2. 윗면 아랫면에 4,5,6이 없었다면 임의 변수 temp에 6또는 5또는 4를 더해준다. 3. 이것을 마지막 주사위까지 반복해주면 되는 간단한(?) 문제였다. n = int(inpu..

※ 접근법 문제에서 시작 지점이 주어지고 그 지점에서 최단 거리를 구하는 문제였기 때문에 다익스트라 알고리즘을 떠올렸고 노드의 개수가 최대 오만 개로 많았기 때문에 우선순위 큐를 이용한 다익스트라 알고리즘 문제로 풀어야겠다고 생각했다. ※ 풀이 1. 풀이법은 우선순위 큐를 이용한 다익스트라 구현과 너무 똑같기 때문에 주석으로 코드 한줄 한줄이 무엇을 의미하는지 달아놓겠습니다. (한 가지 틀린점이 있다면 문제에서 양방향이라고 말을 해줬기 때문에 입력받을 때 양방향으로 받았습니다.) import sys, heapq input = sys.stdin.readline n, m = map(int,input().split()) INF = float("inf") # 무한대 상수 선언 graph = [[] for _ i..

※ 점근법 문제에서 시키는 것만 하면 되는 구현 문제이다. 근데 여기서 00:00 ~ 23:59 까지 시간을 흐르게 할지 여부를 정해야 하는데 그러면 오히려 반복 길이가 더 길어질 것 같아서 과제에 들어있는 것을 순차적으로 돌았다. ※ 풀이 1. 일단 멈춘 과제를 담아둘 리스트인 stop을 만들어 줍니다. 2. 마지막 과제인 경우 후에 처리해야 할 과제가 없기 때문에 무조건 끝내니 이 과제가 마지막인지 여부를 판단해줍니다. 3. 현재 과제의 끝날 시간과 다음 과제의 시작 시간을 계산해서 비교해줍니다. 4. 다음 과제 끝날 시간보다 같거나 작은 시간안에 현재 과제가 끝난다면 정답 리스트에 담아줍니다. 5. 그 후에 멈춰둔 과제가 있다면 진행해줍니다. 6. 여기서 다음 과제를 할 때까지 남은 시간을 계산해줍..

※ 접근법 처음에는 데이터 갯수가 너무 많아서 그리디이지 않을까 떠올렸다. 근데 그리디라고 하기에는 탐욕적인 방법이 떠오르지 않았다. 그래서 힙을 이용하여 heappop을 통해 최솟값을 계속 꺼내서 값을 구할까도 생각을 해봤지만 결국 구해나가는 방법이 그리디적으로 생각을 해야했고 발상이 떠오르지 않았다. 그래서 다른 알고리즘이 없을까 하다가 이분탐색을 떠올렸다. ※ 풀이 1. 각 캐릭터의 레벨을 입력 받으면서 최소 레벨과, 최대 레벨을 구해준다. (최종적으로 코드에서는 최대 레벨을 사용하지 않았지만 처음에는 혹시 모르니 구해놨다.) 2. 최소 레벨을 맞추기 위해 높은 레벨이 낮아질 필요는 없으니 데이터를 올림차순으로 정렬시켰다. 3. 이분탐색 로직에서는 mid값보다 커지는 구간이 나오면 반복문을 종료시켰..

※ 접근법 문제를 봤을 때 어떤 곡괭이로 광물을 캐는지에 따라서 누적 피로도가 달라지니 바로 백트래킹인 것을 떠올렸다. 하지만 여기서 곡괭이가 최대 15개가 될 수 있는데 시간초과가 나지 않을까라는 생각이 들었다. 결국 여기서 시간초과가 발생했고 로직을 조금 수정했더니 문제가 해결됐다. ※ 풀이 1. 곡괭이 종류만큼 반복을 해 곡괭이가 남아있다면 곡괭이로 광물을 캔다. 2. 광물을 캐면서 누적 피로도를 계산해준다. 3. 다음 재귀로 넘어갈 때 누적피로도, 다음 광물 인덱스, 쓴 곡괭이 개수를 계산해서 넘겨준다. def dfs(picks,minerals,fatigue,m_idx,p_count,total): global count if m_idx >= len(minerals) or p_count == tot..

※ 접근법 두 큐 합을 같게 만들기 위한 방법은 여러가지가 있고 최소 횟수를 구해야하니 모든 경우의 수를 파악해야 한다고 생각했다. 하지만 제한사항에서 두 큐의 리스트의 길이가 최대 300,000인 것을 보고 완전탐색을 하면 안 된 다는 것을 느꼈다. ※ 풀이 1. 두 큐 리스트의 합을 비교해 큰 쪽에서 팝을 하고 작은 쪽에다가 append를 해준다. 2. 두 큐 값이 같아지거나, 한 쪽 큐가 비워지거나, 큐 하나 길이에 * 4만큼 반복을 했으면 무한루프를 끝내준다. 3. 2번 조건에 들어가기 전 까지 1번 조건을 반복해준다. def solution(queue1, queue2): count = 0 one_sum = sum(queue1) two_sum = sum(queue2) total = one_sum ..

※ 접근법 그래프가 주어지고 최소의 경우의 수를 구해야 하기에 bfs를 떠올렸다. n,m의 크기를 보고 그람을 사용하고 공주를 찾는 경우를 구하는 함수와 그람을 사용하지 않고 공주를 찾는 경우의 수를 동시에 구해야 시간초과가 나오지 않을 것이라 생각했다. ※ 풀이 1. 0,0부터 시작해 bfs를 시작한다. 2. 방문하지 않았고 배열 범위 안에 있는 조건을 만족하고 그 때 빈 공간이라면 큐에 추가한다. 3. 다음 좌표가 그람이 있는 곳이었다면 그람과 공주 사이의 좌표 거리를 계산한다. ※ 정답코드 from collections import deque n,m,t = map(int,input().split()) data = [list(map(int,input().split())) for _ in range(n..