""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/388352 """ # 풀이 과정 from itertools import combinations """ n: 가능한 자연수 개수 q: 시도한 자연수 배열 집합 ans: 맞춘 자연수 개수 집합 > 스무고개 아이디어 생각! """ def solution(n, q, ans): check = [k + 1 for k in range(n)] num_list = list(combinations(check, len(q[0]))) num_list = list(map(list, num_list)) result = 0 for n in num_list: for count, q_ in enumerate(q): if len(q[0]) * 2 - len(set(q_ + n)) == ans[count]: pass else: break else: result += 1 return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/59036 """ """ 풀이 과정 SELECT ANIMAL_ID,NAME from ANIMAL_INS where INTAKE_CONDITION="Sick" order by ANIMAL_ID """

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/59037 """ """ 풀이 과정 SELECT ANIMAL_ID,NAME from ANIMAL_INS where INTAKE_CONDITION !="Aged" order by ANIMAL_ID """

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/59403 """ """ SELECT ANIMAL_ID,NAME from ANIMAL_INS order by ANIMAL_ID asc """

""" 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/68646 """ # 풀이 과정 """ 맨 끝에 두 개는 항상 살아남음 """ def solution(a): result = [] if len(a) >= 3: check = [0] * len(a) left_num = float("inf") # 좌로 확인 for l in range(len(a)): if left_num < a[l]: check[l] += 1 else: left_num = a[l] # 우로 확인 right_num = float("inf") for r in range(len(a) - 1, -1, -1): if right_num < a[r]: check[r] += 1 else: right_num = a[r] else: return len(result) return len(a) - check.count(2)

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/150367 """ # 풀이 과정 # 왼쪽 자식 노드가 1일때 오른쪽 노드는 반드시 1이고,부모노드 또한 1이어야한다 이걸 바탕으로 확인해야한다 from collections import deque def solution(numbers): result = [] n = numbers for i in n: k = bin(i)[2:] l = len(k) # 포화이진 트리 찾기 h = 0 # 깊이 count = 0 while count < l: count += 2 ** h h += 1 # 포화 이진트리로 모형으로 변환 k = "0" * (count - l) + k # 맨 처음 노드 번호 start = (len(k) + 1) // 2 - 1 # -1인이유: 인덱스 번호 d = (start + 1) // 2 # print(start,i, "start") q = deque([start]) m = [False for _ in range(len(k))] flag = False son = [] # 자식노드 모음 while True: arrive = q.popleft() a = arrive # 방문 확인 m[a] = True # 부모 노드 0일때 if k[a] == "0": if 0 <= a + d < len(k) and k[a + d] == "1" and m[a + d] == False: # print(1,i,"d:",d,"a :",a,"a+d:",a+d) flag = True break elif 0 <= a + d < len(k) and k[a + d] == "0" and m[a + d] == False: # print(2,i) son.append(a + d) if 0 <= a - d < len(k) and k[a - d] == "1" and m[a - d] == False: # print(3,i) flag = True break elif 0 <= a - d < len(k) and k[a - d] == "0" and m[a - d] == False: # print(4,i) son.append(a - d) else: if 0 <= a + d < len(k) and m[a + d] == False: son.append(a + d) if 0 <= a - d < len(k) and m[a - d] == False: son.append(a - d) if len(q) == 0: if len(son) == 0: break else: q += son d //= 2 son = [] # print(q) if flag == True: result.append(0) # print("--------",i,"result") else: result.append(1) # print("--------",i,"result") return result

""" 출처: 프로그래머스, 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