알고리즘 문제풀이/Python179 [프로그래머스] 주차 요금 계산 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 입력으로 주어진 시간을 분으로 수정하여 딕셔너리에서 입차와 출차를 관리하였고, 누적 시간을 저장하였습니다. 마지막에 이 누적시간에 따라 요금을 계산하였습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python from math import ceil def solution(fees, records): base_time, base_cost, per_time, per_cost = fees # 기본 시간(분), 기본 요금(원), 단위 시간(분), 단위 요금(원) answer = [] # 정답 리스트 parking = {} # 주차장에 차량이 있는지 없는지 여부, 키: 차량 번호, 값: 입차 시간 times = {} # 차량별 주차장 이용 누적시.. 2022. 2. 25. [백준] 1300 K번째 수 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 딕셔너리를 이용하여 각 숫자의 값들이 몇개씩 있는지 모두 정의한 후 탐색하려는 인덱스의 값이 어떤 값인지 탐색하였습니다. 그러나 메모리 초과 문제가 발생하였습니다. 이 후 이분탐색을 이용하여 해결하였습니다. 2) 알고리즘 이분탐색 3) 풀이 코드 사용 언어 - Python import sys N = int(sys.stdin.readline()) # 배열의 길이 K = int(sys.stdin.readline()) # 찾으려는 인덱스 번호 answer = 0 # 정답 low, high = 0, K # 정답의 최소 숫자, 최대 숫자 while low = K: # K번째 이후의 숫자라면 high = mid - 1 # 정답으로 작성 answer = m.. 2022. 2. 24. [프로그래머스] 징검다리 건너기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 단순하게 이중반복문을 이용하여 모든 디딤돌을 탐색하는데, 하나의 디딤돌을 기준으로 k개만큼의 디딤돌을 확인하여 몇명이 지나가면 더 지나갈 수 없는지 확인하였습니다. 그러나 이중반복문이기에 시간초과가 발생하였습니다. 시간 초과를 해결하기 위하여 이분탐색을 이용하여 건너는 인원의 수를 구하는 방법으로 접근하였습니다. 2) 알고리즘 이분탐색 3) 풀이 코드 사용 언어 - Python def solution(stones, k): low, high = 0, max(stones) # 건널 수 있는 인원의 최솟값, 최댓값 answer = 0 # 건널 수 있는 인원 while low = k: # k거리 만큼 벌어지면 종료 break else: # 건널 수 있.. 2022. 2. 23. [프로그래머스] 광고 삽입 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 모든 구현을 하는 방식으로 접근하였습니다. 그러나 변수의 범위가 매우 넓어 시간초과가 발생하였습니다. 이후에 시간 단축을 위하여 고민하던 중 시청자가 몇명인지에 따라 결과가 달라지기 때문에 누적합을 이용하여 풀이를 할 수 있다고 생각하여 접근했습니다. 2) 알고리즘 누적합 3) 풀이 코드 사용 언어 - Python def solution(play_time, adv_time, logs): def time_to_seconds(s): # 문자열 시간을 초로 바꾸어 주는 함수 return int(s[:2]) * 3600 + int(s[3:5]) * 60 + int(s[6:8]) play_time_seconds = time_to_seconds(play_.. 2022. 2. 22. [프로그래머스] 경주로 건설 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 DFS 를 재귀로 탐색하여 모든 경우를 탐색을 시도하였으나, 시간초과로 통과하지 못하였습니다. 그래서 BFS 탐색을 하며 DP를 이용하는 방식으로 접근하였습니다. 2) 알고리즘 BFS DP 3) 풀이 코드 사용 언어 - Python from collections import deque def solution(board): dr = [-1, 0, 1, 0] # 상 우 하 좌 dc = [0, 1, 0, -1] N = len(board) # 보드판의 길이 cost = [[1e10] * N for _ in range(N)] # 각 좌표로 이동하는데 발생하는 비용 def BFS(): q = deque([(0, 0, 0, -1)]) # 행 열 좌표, 해당.. 2022. 2. 21. [프로그래머스] 합승 택시 요금 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최소 요금을 구해야 하므로 다익스트라를 이용하였습니다. 출발지에서 각 지점으로 최소 요금으로 갈 수 있는 값을 구하였습니다. 그 이후 각 지점에서 a, b 지점으로 이동하는 요금을 구하여 비교하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import heapq def solution(n, s, a, b, fares): answer = 0 # 최소 요금 linked = [[] for _ in range(n+1)] # 도로 정보들 start_distance = [] # 시작 지점에서 각 지점으로 이동하는데 필요한 요금 for fare in fares: # 양방향으로 도로 정보를 저장함 linked[fare[0]].appe.. 2022. 2. 20. [프로그래머스] 셔틀버스 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 사람들이 기다리기 시작할떄 시간을 분으로 변경하여버스 시간이 올때마다 몇명의 대기 사람이 있는지 구했습니다. 무조건 마지막 버스에 탑승하면 되므로, 마지막 버스의 마지막으로 탑승한 사람보다 먼저 도착하면 되도록 접근하였습니다. 2) 알고리즘 문자열 구현 3) 풀이 코드 사용 언어 - Python def solution(n, t, m, timetable): answer = 0 bus = 540 # 버스의 첫 시작 시간 (분) waiting = 0 # 기다리는 사람의 수 time_line = [] # 사람들이 기다리기 시작하는 시간 리스트 for time in timetable: # 사람들 줄서는 시간들을 분으로 계산하여 분으로 바꾸어 저장 minute .. 2022. 2. 19. [프로그래머스] 추석 트래픽 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 입력으로 주어진 문자열을 가공하여 요청 시작 시간과 응답하는 시간을 ms 단위로 변환시켰습니다. 딕셔너리 변수를 이용하여 키값을 ms 시간으로 하여 처리하는 요청의 최대 개수를 구하였습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python def solution(lines): answer = 0 # 초당 최대 처리량 cnt = 0 # 특정 시간대 처리량 time_line = {} # 시간 테이블 - 키: 시간(ms) / 값: 시작 또는 완료 여부 (-1, 1) for line in lines: # 로그 데이터 date, time, duration = line.split(' ') # 날짜, 시간, 처리 시간 end_ms = int(tim.. 2022. 2. 18. [프로그래머스] 표 편집 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 표의 각 행을 가르키는 커서를 이리저리 움직이며 행을 삭제하거나, 삭제한 행을 원위치로 복구를 하게 되는데, 단순 리스트 구현시 각 요소들의 이동이 무수히 많아질 수 있으므로, 이중연결 리스트를 이용하였습니다. 2) 알고리즘 이중연결 리스트 3) 풀이 코드 사용 언어 - Python def solution(n, k, cmds): answer = [] # 행 삭제 여부를 저장할 정답 리스트 history = [] # 삭제된 행이 저장될 스택 table = [] # 연결 리스트 def create_item(idx): # 연결 리스트 초기 생성 item = [[idx-1, -1], idx] # [이전 인덱스, 이후 인덱스], 현재 인덱스(데이터) if id.. 2022. 2. 17. [프로그래머스] 불량 사용자 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 불량 사용자를 응모자 아이디와 비교하여 제재 가능한 아이디 목록을 만들어 주었습니다. 이때 좀 더 빠른 탐색을 위해, 응모자 아이디를 길이순, 알파벳순으로 정렬하여 앞에서 탐색하였고, 길이를 초과하면 탐색을 멈추도록 하였습니다. 재귀를 이용하여 제재 아이디를 만들 수 있는 경우를 구해주었습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python def solution(user_id, banned_id): answer = set() # 제재 아이디 가능한 경우들 집합 user_id = list(sorted(user_id, key=lambda x: (len(x), x))) # 유저 아이디를 길이순, 알파벳순으로 정렬 cases = [[] f.. 2022. 2. 16. [프로그래머스] 보석 쇼핑 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 하나의 배열에서 조건을 만족하는 구간을 구해야 했으므로 투포인터로 접근하였습니다. 시작점을 기준으로 하여, 조건을 찾은 후에 시작점을 한칸만 이동하여 다음 구간을 찾게 되면 시간초과 문제가 발생할것으로 생각했습니다. 또한, 짧은 구간이 여러개일 경우 시작 진열대 번호가 작은 구간을 출력하여야 했으므로 배열의 오른쪽에서 왼쪽으로 탐색을 시도하였습니다. 우선, 오른쪽 포인터를 기준으로 하여 왼쪽 포인터를 이동 시키며 조건을 만족하는 구간을 구했습니다. 그리고 왼쪽 포인터를 기준으로 오른쪽 방향으로 진행하여 더 짧은 구간이 존재하는지 탐색하였습니다. 구간의 길이를 구했다면, 다음 탐색을 위해 오른쪽 포인터보다 한칸 앞에서 기준을 잡아 탐색하였습니다. 2) .. 2022. 2. 15. [프로그래머스] 자물쇠와 열쇠 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 키가 회전이 가능하므로 회전했을때 모습을 구하였습니다. 키를 자물쇠 가장 오른쪽 하단부터 한칸씩 이동하며 열수 있는지 없는지 판별하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python def solution(key, lock): K, L = len(key), len(lock) # 키와 자물쇠의 한변의 길이 keys = [[[0] * K for _ in range(K)] for _ in range(4)] # 회전한 키의 모양들을 담을 리스트 for i in range(K): for j in range(K): keys[0][i][j] = key[i][j] # 정방향 keys[1][i][j] = key[K-1-j][i] # 90도 회전 .. 2022. 2. 14. 이전 1 ··· 7 8 9 10 11 12 13 ··· 15 다음
