프로그래머스
[프로그래머스] 🔢 큰 수 만들기 / python
[프로그래머스] 🔢 큰 수 만들기 / python
2019.05.08🔢 큰 수 만들기 😃 나의 코드 def solution(number, k): length = len(number) if length > k: m = 0 for cnt in range(k): for idx in range(m, length-1): if number[idx] 0: m = idx-1 break else: number = number[:length-k+cnt] break return "".join([str(i) for i in number]) else: return "0" 탐욕법Greedy 알고리즘에 해당하는 문제입니다. 하지만, 탐욕법을 적용하고도, 특정 ..
[프로그래머스] 🖨 프린터 문제 / python
[프로그래머스] 🖨 프린터 문제 / python
2019.02.18🖨 프린터 문제 풀어보기 😃 나의 코드 def solution(priorities, location): pos = [] for i in range(len(priorities)): if i == location: pos.append(True) else: pos.append(False) answer = 0 count = 0 m = max(priorities) while True: if m > priorities[0]: priorities.append(priorities.pop(0)) pos.append(pos.pop(0)) else: count += 1 priorities.pop(0) if pos.pop(0): return count m = max(priorities) 스택(stack)/큐(queue) 자료..
[프로그래머스] 👨💻 기능 개발 / python
[프로그래머스] 👨💻 기능 개발 / python
2019.02.18👨💻 기능 개발 문제 풀어보기 😃 나의 코드 import math def solution(progresses, speeds): answer = [] progresses = [math.ceil((100-a)/b) for a, b in zip(progresses, speeds)] front = 0 for idx in range(len(progresses)): if progresses[front] < progresses[idx]: answer.append(idx-front) front = idx answer.append(len(progresses)-front) return answer 스택stack/큐queue 자료구조에 속한 문제입니다. 우선 progresses와 speeds로 나누어진 두 list를 하나..
[프로그래머스] 👷♀️ 타일 장식물 / python
[프로그래머스] 👷♀️ 타일 장식물 / python
2019.02.18👷♀️ 타일 장식물 문제 풀어보기 😃 나의 코드 def solution(N): rad_array = [1,1] for i in range(2,N): rad_array.append(rad_array[-1] + rad_array[-2]) answer = (rad_array[-2] + rad_array[-1]*2)*2 return answer DP(Dynamic Programming, 동적계획법)을 이용해 해결한 문제입니다. DP의 계획에 따라 전체 문제를 작은 부분으로 나누겠습니다. 최종적으로 구할 직사각형의 둘레는 마지막으로 구한 정사각형과 그 전 정사각형의 변의 길이를 통해 구할 수 있기 때문에 변을 구하는 문제로 치환해서 풀겠습니다.가장 작은 정사각형부터 구하면 마지막으로 구한 정사각형의 한 변과 그..
[프로그래머스] 👨🏫 정수 삼각형 / python
[프로그래머스] 👨🏫 정수 삼각형 / python
2019.02.18👨🏫 정수 삼각형 문제 풀어보기 😃 나의 코드 def solution(tri): m_lst = [] for row in tri: lst = [] if len(m_lst) == 0: lst.append(row[0]); else: for idx, num in enumerate(row): if idx == 0: lst.append(m_lst[-1][idx] + num) elif idx == len(row)-1: lst.append(m_lst[-1][-1] + num) else: lst.append(max(m_lst[-1][idx-1],m_lst[-1][idx]) + num) m_lst.append(lst) return max(m_lst[-1]) DP(Dynamic Programming, 동적계획법)을 이용해..
[프로그래머스] ⚾ 숫자 야구 / python
[프로그래머스] ⚾ 숫자 야구 / python
2019.02.15⚾ 숫자 야구 문제 풀어보기 😃 나의 코드 from itertools import permutations def check_score(question, candidate, s, b): strike = 0 for i in range(len(question)): if question[i] == candidate[i]: strike += 1 if s != strike: return False ball = len(set(question) & set(candidate))-strike if b != ball: return False return True def solution(baseball): lst = list(permutations([1,2,3,4,5,6,7,8,9], 3)) for i in baseball:..
[프로그래머스] 🎨 카펫 문제 / python
[프로그래머스] 🎨 카펫 문제 / python
2019.02.15--- --- 🎨 카펫 문제 풀어보기 😃 나의 코드 def solution(brown, red): for a in range(1, int(red**0.5)+1): if not red % a: b = red // a if 2*a + 2*b + 4 == brown: return [b+2, a+2] 완전 탐색(exhaustive search)를 이용하여 푸는 문제입니다. 빨간색의 가로를 A, 세로를 B라고 했을 때, 주어진 값 red는 A*B가 되고 brown은 2(A+B)+4가 됩니다. 이제 A와 B에 찾는 과정입니다. red를 두 자연수 곱의 쌍으로 봤을 때, 중복된 곱의 쌍을 없엔다면 A의 범위는 red의 제곱근의 내림값보다 작거나 같을 것입니다. 이를 통해 얻은 자연수 A와 B의 쌍이 brown에 값에..
[프로그래머스] 👨🏫 가장 큰 정사각형 / Python
[프로그래머스] 👨🏫 가장 큰 정사각형 / Python
2019.02.15👨🏫 가장 큰 정사각형 문제 풀어보기 😃 나의 코드 def solution(board): width = len(board[0]) height = len(board) for x in range(1,height): for y in range(1,width): if board[x][y] == 1: board[x][y] = min(board[x-1][y-1], min(board[x-1][y], board[x][y-1])) + 1 return max([item for row in board for item in row])**2 이 문제를 완전 탐색(Brute-force)으로 푼다고 생각해봅시다. board의 모든 인덱스를 확인해야하고, 정사각형이 가장 작은 1부터 최대 크기의 정사각형까지 확인하게 된다면 시간 ..
[프로그래머스] 👩🏫 행렬의 곱셈 / Python
[프로그래머스] 👩🏫 행렬의 곱셈 / Python
2019.02.15👩🏫 행렬의 곱셈 문제 풀어보기 😃 나의 코드 def solution(arr1, arr2): answer = [] for idx1 in range(len(arr1)): row = [] for idx2 in range(len(arr2[0])): tmp = 0 for idx3 in range(len(arr1[0])): tmp += arr1[idx1][idx3] * arr2[idx3][idx2] row.append(tmp) answer.append(row) return answer 제한 조건에서 곱할 수 있는 배열만 주어진다고 했으니, 두 배열을 A X B, B X C로 해보겠습니다. 그리고 두 행렬의 곱으로 나온 배열의 크기는 A X C가 될 것입니다. 결과 배열의 왼쪽 위부터 오른쪽 아래까지 만들어 나가..
[프로그래머스] ☎ 전화번호 목록 / Python
[프로그래머스] ☎ 전화번호 목록 / Python
2019.02.14☎ 전화번호 목록 문제 풀어보기 😃 나의 코드 def solution(phone_book): phone_book.sort() for prefix_idx, prefix_phone in enumerate(phone_book): for target_phone in phone_book[prefix_idx+1:]: if prefix_phone == target_phone[:len(prefix_phone)]: return False return True 우선 일반적인 풀이입니다. 먼저 해야할 것은 phone_book에 사전 작업으로 사전형으로 정렬해줍니다. 이렇게 정렬하게 되면 절대로 특정 인덱스 앞은 특정 인덱스의 prefix가 될 일이 없기 때문에 시행을 조금이나마 줄여줍니다. 같은 O(n^2)의 시간 복잡도이..
[프로그래머스] 👷♀️ 쇠막대기 / Python
[프로그래머스] 👷♀️ 쇠막대기 / Python
2019.02.14👷♀️ 쇠막대기 문제 풀어보기 😃 나의 코드 def solution(arrangement): answer = 0 arrangement = arrangement.replace("()","L") stack = [] for idx, c in enumerate(arrangement): if c == '(': stack.append('(') answer += 1 elif c == ')': stack.pop() else: answer += len(stack) return answer 스택/큐 알고리즘 카테고리에 속한 문제입니다. 이 문제는 스택을 이용해 풀어야합니다. 우선 레이저에 해당하는 ()를 (과 )이 아닌 다른 문자 하나로 바꾸줍니다 여기서는 Lazer에 해당하는 L로 바꿔주었습니다. stack라는 lis..
[프로그래머스] 🧱 프렌즈 4 블록 - [1차] 2018 카카오 블라인드 채용 / Python
[프로그래머스] 🧱 프렌즈 4 블록 - [1차] 2018 카카오 블라인드 채용 / Python
2019.02.14🧱 프렌즈 4 블록 문제 풀어보기 😃 나의 코드 dx = [0, 1, 0, 1] dy = [0, 0, 1, 1] def safe(width, height, c_idx, r_idx): for x, y in zip(dx,dy): if width-1 < x+c_idx or x+c_idx < 0 or height-1 < y+r_idx or y+r_idx < 0: return False return True def del_check(board, c_idx, r_idx): square_set = set() for x, y in zip(dx,dy): square_set.add(board[y+r_idx][x+c_idx]) if len(square_set) == 1 and square_set != {" "}: retur..