""" 출처: 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/389479 """ # 풀이 과정 """ m명 마다 서버 1대 m명 이하 증설 필요x n*m <= x <(n+1)*m : n대 서버 필요 k 값에 따라 그 시간 동안만 이용 후 반납 해야한다. 5시간 마다 증설 > 사라짐 heapq 관련 생각 예약 후 빠져나간다는 생각 목표: 증설 횟수 구하기 """ import heapq def solution(players, m, k): result = 0 # 서버 최대 수용 인원 max_people = m - 1 # 서버 설치 시간, 대수 ,사라지는 시간 heap = [] # 인원 수 투입 for num, p in enumerate(players): # 만료된 서버 제거 if len(heap) > 0 and heap[0][0] == num: # 제거될 시간, 서버 제거와 동시에 제거된 인원 수 make, n = heapq.heappop(heap) max_people -= n if max_people >= p: continue # 서버 설치를 해야할 경우 else: # 할당 충원에 필요한 인원 파악 charge = p - max_people # 나누어 떨어질 때 if charge / m == charge // m: heapq.heappush(heap, (num + k, charge)) max_people += charge result += charge // m else: # 서버 종료 시간, 충원된 인원 heapq.heappush(heap, (num + k, (m) * (charge // m + 1))) max_people += (m) * (charge // m + 1) # 추가된 기계 result += (charge // m) + 1 # 현재 설치된 기계 0대, 인원이 들어온 경우 elif len(heap) == 0 and p > max_people: necessary = (p - (max_people)) # 나누어 떨어질 떄 if necessary / m == necessary // m: heapq.heappush(heap, (num + k, necessary)) max_people += necessary * m result += necessary // m else: heapq.heappush(heap, (num + k, (necessary // m) * m + m)) max_people += (necessary // m) * m + m result += necessary // m + 1 elif len(heap) > 0 and p > max_people: # 기존 서버로 불가능한 경우 if p > max_people: charge = p - max_people if charge // m == charge / m: heapq.heappush(heap, (num + k, charge)) max_people += m * (charge // m) result += charge // m else: heapq.heappush(heap, (num + k, (charge // m + 1) * m)) max_people += m * (charge // m + 1) result += charge // m + 1 else: pass return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/150366 """ # 풀이 과정 # 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다. 중요포인트 # 병합된 셀의 경우 따로 체크 리스트를 만든 후 병합과 삭제 시 따로 함수를 만들어서 구현! (시간과 효율성에 관하여 생각도 해보기!) 03 07 20시 추가! # 업데이트 된 셀 또한 통합이 되어있을 경우 통째로 바뀌어야 한다! from collections import deque def merge(m, s, fir, sec, check): check = deque(check) flag = False n = len(check) count = 0 r1 = fir[0] c1 = fir[1] r2 = sec[0] c2 = sec[1] new = [[r1, c1], [r2, c2]] while count < n: i = check.popleft() if [r1, c1] in i or [r2, c2] in i: for v, w in i: if not [v, w] in new: new.append([v, w]) flag = True else: check.append(i) count += 1 if flag == False: check.append([[r1, c1], [r2, c2]]) m[r1][c1] = s m[r2][c2] = s else: for v, w in new: m[v][w] = s check.append(new) return m, list(check) def unmerge(m, check, s, fir): r = fir[0] c = fir[1] check = deque(check) n = len(check) count = 0 while count < n: i = check.popleft() if [r, c] in i: for v, w in i: m[v][w] = "EMPTY" m[r][c] = s break check.append(i) count += 1 m[r][c] = s return m, list(check) def solution(commands): m = [["EMPTY"] * 50 for _ in range(50)] # 표 k = commands # 축약 check = [] # sum cell result = [] for i in k: # update if "UPDATE" in i: if i.count(" ") == 3: t = i.split(" ") r = int(t[1]) - 1 c = int(t[2]) - 1 value = t[3] for v in check: if [r, c] in v: # print(check,value) for a, b in v: m[a][b] = value break else: m[r][c] = value elif i.count(" ") == 2: t = i.split(" ") value1 = t[1] value2 = t[2] # 모든 셀 변환 for v1 in range(50): for v2 in range(50): if m[v1][v2] == value1: m[v1][v2] = value2 # merge elif "MERGE" in i and not "UN" in i: t = i.split(" ") # index를 위해 -1 r1 = int(t[1]) - 1 c1 = int(t[2]) - 1 r2 = int(t[3]) - 1 c2 = int(t[4]) - 1 fir = [r1, c1] sec = [r2, c2] if m[r1][c1] == "EMPTY": s = m[r2][c2] else: s = m[r1][c1] # print(check,"before",s) m, check = merge(m, s, fir, sec, check) # print(check,"after",s) # unmerge elif "UNMERGE" in i: t = i.split(" ") r = int(t[1]) - 1 c = int(t[2]) - 1 s = m[r][c] # print(s,[r,c]) fir = [r, c] m, check = unmerge(m, check, s, fir) elif "PRINT" in i: t = i.split(" ") r = int(t[1]) - 1 c = int(t[2]) - 1 result.append(m[r][c]) # print(check,"all",t[0]) return result

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/84021 """ # 풀이 과정 """ 조건: 1회에 1번 조각 회전가능 뒤집기 불가능 목표: 채울 수 있는 최대칸을 구하여라 생각방향:모양이 들어맞아야 인접한 곳이 비는 일이 없어짐에 따라 빈 곳과 테이블을 비교해야한다 회전하는 방법에 대한 아이디어 생각 > 회전변환 닮음의 원칙 응용 생각 고민 # 양쪽 맵의 도형 좌표들을 모두 모은 후 리스트로 모은 후 두 맵 중 하나의 좌표를 하나씩 팝 한 후 회전변환 후 도형 중 가장 작은 점을 찾은 후 평행 이동 시켰을 때 같은 도형이라면 집합상 동일하다는 점을 체크 후 구하기 """ v = [] # 보드 도형 board = [] # 테이블 도형 check = [] from collections import deque import copy def find(i, j, g, s): global v_baord, v_table, board, check dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] new = [] q = deque([[i, j]]) while q: a, b = q.popleft() v[a][b] = True new.append([a, b]) for k, t in zip(dx, dy): if 0 <= a + k < len(g) and 0 <= b + t < len(g[0]): if v[a + k][b + t] == False and s == "board": if g[a + k][b + t] == 0: q.append([a + k, b + t]) v[a + k][b + t] = True elif v[a + k][b + t] == False and s == "table": if g[a + k][b + t] == 1: q.append([a + k, b + t]) v[a + k][b + t] = True # print(a+k,b+t) # print(new,"new",s) x = copy.deepcopy(new) # if s=="board": # check.append(x) # else: # board.append(x) return x def solution(game_board, table): global check, board, v g = game_board t = table # 행 길이 m = len(table) # 열 길이 n = len(table[0]) # 방문 기록 v = [[False] * n for _ in range(m)] s = "board" # 보드의 빈공간 도형 찾기 for i in range(m): for j in range(n): if g[i][j] == 0 and v[i][j] == False: plus = find(i, j, g, s) board.append(plus) # 보드 내 도형을 구한 후 초기화 v = [[False] * n for _ in range(m)] s = "table" # 테이블의 도형 찾기 for i in range(m): for j in range(n): if t[i][j] == 1 and v[i][j] == False: # print(i,j,"table 도형 찾기 시작점") plus = find(i, j, t, s) # print(check,"find 후 check") check.append(plus) # 테이블의 도형을 하나씩 뽑아낸 후 모든 좌표를 90도 회전변환 후 닮음 여부 체크 result = 0 # 채워질때마다 추가 # board=deque(board) # check:테이블 도형 board: 보드 도형 board = deque(board) count = len(board) # print(check,"table 도형",board,"보드 도형") while count > 0: o = board.popleft() o.sort() board.append(o) count -= 1 while check: k = check.pop() new = [] k.sort() new.append(k) one = [] # 90도 two = [] # 180도 three = [] # 270도 for x, y in k: one.append([-y, x]) two.append([-x, -y]) three.append([y, -x]) one.sort() two.sort() three.sort() new.append(one) new.append(two) new.append(three) new_board = [] while board: figure = board.popleft() # 꼭짓점의 개수 체크 if len(new[0]) == len(figure): flag = False # 0도~270도 for i in range(4): num1, num2 = (new[i][0][0] - figure[0][0]), (new[i][0][1] - figure[0][1]) for j in range(len(figure)): if (new[i][j][0] - figure[j][0]) != num1 or (new[i][j][1] - figure[j][1]) != num2: break else: # 같은 도형 flag = True # print(new[0],i,"figure",figure,num1,num2) result += len(new[0]) break else: new_board.append(figure) continue if flag == False: new_board.append(figure) elif flag == True: break board += new_board return result

""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/92344 """ # 풀이 과정 """ 조건:행:m 열:n 적군 내구도가 0으로 되면 파괴 아군 내구도를 높임 타입1:적 타입2:아군 특이점:파괴된 건물도 공격받으면 내구도가 더 하락한다! 목표:파괴되지 않은 건물의 개수를 구하시오 생각방향:skill의 조건을 감안하면 skill의 한 번의 루프로 board를 구성하는 방향성에서 생각해보기 중복되는 면적에 대한 생각 사고 누적합 개념 적용여부 및 dp 생각방향 전환 """ def solution(board, skill): # 행 m = len(board) # 열 n = len(board[0]) result = 0 check = [[0] * (n + 1) for _ in range(m + 1)] # sol1: 시간 초과 # team: 아군 enemy: 적 """ for s in skill: ax,ay=s[1],s[2] bx,by=s[3],s[4] c=s[5] # 적 if s[0]==1: for x in range(ax,bx+1): for y in range(ay,by+1): before=board[x][y] board[x][y]-=c after=board[x][y] if before>0 and after<=0: result-=1 # 아군 else: for x in range(ax,bx+1): for y in range(ay,by+1): before=board[x][y] board[x][y]+=c after=board[x][y] if before<=0 and after>0: result+=1 """ # sol2:시간 초과 # for s in skill: # if s[0]==1: # for x in range(s[1],s[3]+1): # for y in range(s[2],s[4]+1): # check[x][y]-=s[5] # else: # for x in range(s[1],s[3]+1): # for y in range(s[2],s[4]+1): # check[x][y]+=s[5] # for i in range(m): # for j in range(n): # board[i][j]+=check[i][j] # if board[i][j]>0: # result+=1 # sol3 for enemy, r1, c1, r2, c2, degree in skill: check[r1][c1] += (-degree) if enemy == 1 else degree check[r2 + 1][c1] += degree if enemy == 1 else -degree check[r1][c2 + 1] += degree if enemy == 1 else -degree check[r2 + 1][c2 + 1] += (-degree) if enemy == 1 else degree # print(check) # 누적합 행 for i in range(len(check)): for j in range(len(check[0]) - 1): check[i][j + 1] += check[i][j] # print(check) # 누적합 열 for j in range(len(check[0])): for i in range(len(check) - 1): check[i + 1][j] += check[i][j] # print(check) for v in range(m): for w in range(n): board[v][w] += check[v][w] if board[v][w] > 0: result += 1 return result

""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/118668 """ # 풀이 과정 # 알고력: 0이상의 정수 코딩력: 0이상의 정수 # 조건: 알고력, 코딩력, 알고력 증가량, 코딩력 증가량, 걸리는 시간 # 목표: 모든 문제를 푸는 코딩력,알고력을 얻는 최단 시간 (최단 시간안에 역량 얻기) # 중요포인트:모든 문제 다 안풀어도 됨,같은 문제 여러번 풀기 가능 # 생각 접근 및 방향 변화: 최대로 걸리는 시간을 산정 후 그 시간에 도달하기 전 코딩력 알고력 체크 # 도달해야 될 알고력과 코딩력을 확인 후 최단 시간에 도달하는 방향으로 나아가는 생각 # 완탐 불가능 # 효율1 알고력 효율2 코딩력을 기준으로 가장 효율이 좋은 것을 넣는 방식 고민 # 시간 대비 효율 # 시간 효율로 dp 구성 가능한지 여부(반복되는 문제를 통해 답을 찾는 과정이라 생각이 들기 때문이다.) # 요구력에 제일 근사한 값이 두 개 나올 시 dp에 넣을지 생각 # 효율이 떨어져도 검증해야될 필요성 느낌: 문제 푸는데 최소한의 역량 확보와 효율과 차이가 날 수 있음 import heapq def solution(alp, cop, problems): # 목표 역량 algorism, coding = 0, 0 for a, c, algo, code, time in problems: algorism = max(a, algorism) coding = max(c, coding) # dp를 활용하기 위한 최대 시간 계산 if alp >= algorism: plus_alp = 0 else: plus_alp = algorism - alp if cop >= coding: plus_cop = 0 else: plus_cop = coding - cop max_time = plus_alp + plus_cop if max_time == 0: return 0 dp = [[float("inf")] * (plus_cop + 1) for _ in range(plus_alp + 1)] q = [[alp, cop, 0]] check = 0 while q: al, co, t = q.pop() for a, c, alco, code, time in problems: if al >= a and co >= c and (t + time) <= max_time: if al + alco >= algorism and co + code >= coding: if dp[plus_alp][plus_cop] > (time + t): dp[plus_alp][plus_cop] = time + t elif al + alco >= algorism and co + code < coding: if dp[plus_alp][(co + code) - cop] > (time + t) and time + t < dp[plus_alp][plus_cop]: dp[plus_alp][(co + code) - cop] = time + t q.append([algorism, co + code, time + t]) elif al + alco < algorism and co + code >= coding and time + t < dp[plus_alp][plus_cop]: if dp[(al + alco) - alp][plus_cop] > (time + t): dp[(al + alco) - alp][plus_cop] = time + t q.append([al + alco, coding, time + t]) elif al + alco < algorism and co + code < coding and time + t < dp[plus_alp][plus_cop]: if dp[(al + alco) - alp][(co + code) - cop] > (time + t): dp[(al + alco) - alp][(co + code) - cop] = time + t q.append([al + alco, co + code, time + t]) if (al + 1) <= algorism and t + 1 < dp[plus_alp][plus_cop]: if co >= coding: if dp[al + 1 - alp][plus_cop] > t + 1: q.append([al + 1, coding, t + 1]) else: if dp[al + 1 - alp][co - cop] > t + 1: dp[al + 1 - alp][co - cop] = t + 1 q.append([al + 1, co, t + 1]) if (co + 1) <= coding and t + 1 < dp[plus_alp][plus_cop]: if al >= algorism: if dp[plus_alp][co + 1 - cop] > t + 1: q.append([algorism, co + 1, t + 1]) else: if dp[al - alp][co + 1 - cop] > t + 1: dp[al - alp][co + 1 - cop] = t + 1 q.append([al, co + 1, t + 1]) return dp[-1][-1]

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12949 """ # 풀이 과정 from collections import deque def solution(arr1, arr2): result = [] new = [] count = 0 while count < len(arr2[0]): check = [] for k in range(len(arr2)): check.append(arr2[k][count]) new.append(check) count += 1 arr1 = deque(arr1) while arr1: check = [] i = arr1.popleft() for j in new: count = 0 for v, w in zip(i, j): count += v * w check.append(count) result.append(check) return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/59404 """ """ 풀이 과정 SELECT ANIMAL_ID,NAME,DATETIME from ANIMAL_INS order by NAME asc,DATETIME desc """

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/77485 """ # 풀이 과정 def solution(rows, columns, queries): import copy from collections import deque result = [] map = [[False for col in range(columns)] for a in range(rows)] count = 1 # 기본 맵 for a in range(rows): for b in range(columns): map[a][b] = count count += 1 # 맵 모양 변경 for c in queries: num_list = [] x_1 = c[0] y_1 = c[1] x_2 = c[2] y_2 = c[3] tmp = map[x_1 - 1][y_1 - 1] # 맨 왼쪽 for g in range(x_1 - 1, x_2 - 1): map[g][y_1 - 1] = map[g + 1][y_1 - 1] num_list.append(map[g][y_1 - 1]) # num_list.append("first") # 맨 아랫줄 ok for f in range(y_1 - 1, y_2 - 1): map[x_2 - 1][f] = map[x_2 - 1][f + 1] num_list.append(map[x_2 - 1][f]) # num_list.append("second") # 맨 오른쪽 ok for e in range(x_2 - 1, x_1 - 1, -1): map[e][y_2 - 1] = map[e - 1][y_2 - 1] num_list.append(map[e][y_2 - 1]) # num_list.append("third") # 맨 윗줄 ok for d in range(y_2 - 1, y_1, -1): map[x_1 - 1][d] = map[x_1 - 1][d - 1] num_list.append(map[x_1 - 1][d]) # print(num_list) map[x_1 - 1][y_1] = tmp num_list.append(map[x_1 - 1][y_1]) result.append(min(num_list)) # num_list.append("fourth") # print(num_list) return result

""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/131129 """ # 풀이 과정 # 점수를 깎아서 0점으로 만듬 단, 남은 점수보다 큰 점수로 득점하면 버스트 후 실격 # 조건: # 싱글: 해당 점수 더블:해당 점수 2배 트리플: 해당 점수 3배 # 불, 아우터 불: 50점 # 승리 조건: 더 빨리 0점 만든 선수(같은 라운드의 경우 그 중 싱글 또는 불을 더 많이 던진 선수) # 빨리 0점을 만들면서 싱글 또는 불을 최대한 많이 던지는 방법 # 목표:[다트 던진 횟수,싱글 횟수+불 횟수] # 생각방향: 무조건 1번에 끝나지 않는 경우 불과 싱글과 함께된 조합으로 동일한 횟수로 해결 가능할 경우 그 경우의 수 조합 생각 # 불과 싱글인 수로 뺀 것 그렇지 않은 경우 두 가지 밖에 없다 # 기본 전제 생각 조건: 가장 빨리 끝나는 라운드에서 싱글과 불이 제일 많아야한다 # dfs로 생각 후 접근 방향 생각! > 시간초과 # 같은 수들로 끊임없이 작게 만들어 원하는 값을 얻는 방식 > dp 접근 # 다트의 수가 차이나는 순간에 대하여 고찰 후 문제를 접근 > 시간 단축 및 정답! import heapq from collections import deque import sys sys.setrecursionlimit(10 ** 6) result = [] def dfs(count, sb, num, s, d): global result for i in range(len(s) - 1, -1, -1): if num - s[i] >= 0: if s[i] in d and num - s[i] == 0: result.append([count + 1, sb + 1]) elif not s[i] in d and num - s[i] == 0: result.append([count + 1, sb]) elif s[i] in d and num - s[i] > 0: if len(result) > 0: if count + 1 >= result[0][0]: break dfs(count + 1, sb + 1, num - s[i], s, d) break elif not s[i] in d and num - s[i] > 0: if len(result) > 0: if count + 1 >= result[0][0]: break dfs(count + 1, sb, num - s[i], s, d) return result def solution(target): t = target global result # 다트판 (싱글 가능판) d = [k + 1 for k in range(20)] # 점수 얻을 수 있는 판 s = [] for i in d: s.append(i) s.append(i * 2) s.append(i * 3) s.append(50) s = list(set(s)) d.append(50) s.sort() count, sb, num = 0, 0, t if t > 300: count += (t - 300) // 60 num = 300 + (t - 300) % 60 dfs(count, sb, num, s, d) result = sorted(result, key=lambda x: (x[0], -x[1])) return result[0]

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/131127 """ # 풀이 과정 def solution(want, number, discount): from collections import deque discount = deque(discount) result = 0 check = {} for k in range(len(want)): check[want[k]] = number[k] result_check = check.copy() check_2 = deque([]) while discount: t = discount.pop() check_2.append(t) if len(check_2) >= 10: flag = False for l in check_2: if l in result_check: if result_check[l] > 0: result_check[l] -= 1 if result_check[l] == 0: del result_check[l] if len(result_check) == 0: result += 1 check_2.popleft() result_check = check.copy() flag = True break if flag == False: check_2.popleft() result_check = check.copy() return result