🐍 코딩테스트 대비 : PS

[프로그래머스] 입국심사 (level3, python)

🤔 풀이 코드 def check(n, times, k): can_enter = 0 for t in times: can_enter += k // t return True if can_enter >= n else False def solution(n, times): answer = 0 start = 0 end = min(times) * n mid = start while mid + 1 != end: mid = (start + end) // 2 if check(n, times, mid): end = mid else: start = mid return end 🤔 문제 풀이 이분탐색으로 풀이해야 하는 문제입니다. 항상 이분 탐색은 시작점과 끝점을 잡는 기준과, 어떤 것을 이분탐색에 사용해야 할지 판단하는게 어렵네..

[프로그래머스] 거리두기 확인하기 (level2, python)

🤔 풀이 코드 from collections import deque def bfs(start, place): queue = deque() queue.append([start[0], start[1], 0]) visited = [[False for _ in range(5)] for _ in range(5)] visited[start[0]][start[1]] = True dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] candidate = [] while queue: a, b, dist = queue.popleft() for i in range(4): nx = dx[i] + a ny = dy[i] + b if 0

[프로그래머스] 멀쩡한 사각형 (level2, python)

🤔 풀이 코드 import math def solution(w,h): return w * h - (w + h - math.gcd(w, h)) 🤔 문제 풀이 코드가 짧아서 쉬운 문제처럼 보이지만, 왜 저런 식이 나왔는지 이해하는 것이 중요합니다. 문제에서 나온 이 예시를 한 번 봅시다. 가로 8, 세로 12의 사각형으로, 일정한 패턴이 반복되는 것처럼 보입니다. 위와 같은 가로 2, 세로 3의 사각형의 패턴이 여러 번 반복되는 것처럼 보이죠. 계산하면, 가로 8 세로 12의 사각형은, 가로 2, 세로 3의 사각형에서 선에 걸리는 사각형의 개수 * 4입니다. 여기서 4라는 숫자는, 8과 12의 최대 공약수인것을 알 수 있습니다. 또한 가로 2와 세로 3은 서로소 관계임을 알 수 있죠. 따라서 최대 공약수를 ..

[프로그래머스] 여행경로 (level3, python)

🤔 풀이 코드 from collections import deque import copy def bfs(start, ways, visited, n): queue = deque() queue.append([start, start, visited]) candidate = [] while queue: now, log, visit = queue.popleft() if len(log) == 4 * n - 1: candidate.append(log) continue for next in ways[now]: visited_key = now + next if visit[visited_key] != 0: visit[visited_key] -= 1 queue.append([next, log + " " + next, cop..

[프로그래머스] 디스크 컨트롤러 (level3, python)

🤔 풀이 코드 import heapq from collections import deque def solution(jobs): # jobs : [작업이 요청되는 시점, 작업의 소요시간] answer = [] job_queue = deque(sorted(jobs, key=lambda x : x[0])) heap = [] time = 0 while job_queue or heap: # 작업 큐에서 실행가능한 힙으로 이동 while job_queue and job_queue[0][0]

[프로그래머스] 전력망을 둘로 나누기 (level2, python)

🤔 풀이 코드 import copy from collections import deque def bfs(start, tree, n): visited = [False for _ in range(n+1)] queue = deque() queue.append(start) visited[start] = True result = 1 while queue: now = queue.popleft() for next_node in tree[now]: if not visited[next_node]: queue.append(next_node) visited[next_node] = True result += 1 return result def solution(n, wires): answer = n adjust_arr = [[..

[프로그래머스] 뒤에 있는 큰 수 찾기 (level2, python)

🤔 풀이 코드 from collections import deque def solution(numbers): answer = [-1 for i in range(len(numbers))] stack = deque() for idx, now in enumerate(numbers): if not stack: stack.append([idx, now]) continue top_idx, top_now = stack[-1] while stack and now > top_now: stack.pop() answer[top_idx] = now if stack: top_idx, top_now = stack[-1] stack.append([idx, now]) return answer 🤔 문제 풀이 우선, 문제의 조건을 보면..

[프로그래머스] 연속 부분 수열 합의 개수 (level2, python)

🏝 문제 설명 철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다. 원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다. 원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 3 ≤ elements의 길이 ≤ 1,000 1 ≤..