CEO

문제 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 풀이 좌측에 있는 탑이, 우측의 탑 보다 높이가 높은 경우에 신호를 수신할 수 있다. 이를 구현하기 위해 처음에는 입력을 리스트로 받고 뒤집어서 생각해야 할까 고민했다. 하지만, 각 탑의 인덱스, 높이를 `stack`으로 처리하면 위 문제를 간단히 해결할 수 있다. `stack`에 탑을 순서대로 삽입한다. pop을 하게 되면, 현재 탑을 기준으로 바로 좌측의 탑부터 비교를 시작 할 수 있다. 현재 타워와 비교하여 `stack`안의 타워들(좌측의 타워..

문제 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 풀이 프린터를 하기 위한 문서 대기열에 문서들이 있다. 이때, 각 문서들은 `우선순위`를 가진다. 큐(문서 대기열)에서 문서를 인쇄하고자 할 때 큐에 있는 문서들 중 우선수위가 하나라도 높은 것이 있다면, 프린트하지 않고 큐의 맨 뒤로 보낸다. 이는 앞서 다룬 프로그래머스: 프린터와 유사한 문제이다. 문제를 풀기 위해서 다음과 같이 접근하였다. 최초의 문서가 위치한 인덱스를 알기 위해 `enumerate`를 활용한다. `deque`를 활용하여, 인쇄 가능..

문제 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 문제 풀이 괄호의 문자열이 주어질 때, 올바른 괄호인지 찾는 문제이다. 이 문제는 `DP`로도 풀 수 있지만, 카탈랑 수로도 풀 수 있다. 카탈랑 수는 이진트리의 수를 셀 때 사용하는 수열이다. 카탈랑 수를 파이썬 코드로 나타내면 `factorial(2 * num) // (factorial(num) * factorial(num + 1))`이다. 이를 통해 문제를 해결할 수 있다. 코드 from math import factorial from sys impo..

문제 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 풀이 진열된 보석들 중 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾는 문제이다. 앞에서부터 순차적으로 탐색을 하게 되면 효율성을 통과할 수 없다. 고민을 하다가 솔루션을 참조하였는데, `투포인터`를 사용하여야 하는 문제였다. 구현하는 방식은 솔루션과 같이 구현하면, 문제를 해결할 수 있다. 평소 `투포인터`를 활용하는 문제를 다루어보지 않아 풀이를 보고 나서야 이해를 할 수 있었다.🤔 코드 def solution(gems): start, end = 0, 0 gem_num = l..

문제 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제 풀이 특정한 숫자 `N`으로 사칙연산을 사용하여 `number`를 표현할 수 있는지 찾는 문제이다. 이때 `N`을 사용한 횟수가 가장 작은 경우를 찾아야 한다. 문제를 풀기 위해서는 `DP`를 통해서도 풀 수 있지만, `DFS`를 통해 풀더라도 간신히 통과할 수 있다. `DFS`를 통해 사용한 `N`의 수를 카운트하고, 카운트된 수가 8보다 크다면 더 이상 가지를 뻗을 필요 없이 종료하면 된다. 또한 만족하는 경우를 찾은 경우, 현재 찾은 카운트보다 `N`을 더 많이 사용한다면 가지를 뻗지 않으면 보다 시간을 단축시킬 수 있다. 코드 from math import inf answer = inf def dfs(n, cnt, num,..

문제 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 문제 풀이 주어진 연산 종류에 따라 큐에 연산을 삽입하고 삭제하는 과정을 진행한다. 연산의 종류에 따라 동작하는 과정은 다음과 같다. 명령어에 따라 큐에 숫자를 삽입하고, `D 1`인 경우 큐에서 최댓값을 삭제한다. 이와 달리 `D -1`인 경우 큐에서 최솟값을 삭제한다. 이는 별도로 `heapq`를 사용하지 않더라도 `list`를 통해 간단히 구현할 수 있다. 코드 def solution(operations): answer = [] for cur_op in operations: op, num = cur_op.split(' ') if op == 'I': answer.append(int(num)) elif answer: if num =..

문제 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 문제 풀이 출발지점부터 거리만큼 떨어진 곳에 도착지점이 있다. 이때 그 사이에 있는 바위들 중 몇 개를 제거하려고 한다. 특정 바위를 `N`개만큼 제거할 때 거리의 최솟값이 최대가 되는 경우를 구하는 문제이다. 이 문제는 문제의 분류와 같이 `이분 탐색`으로 해결할 수 있다. `이분 탐색`을 통해 최소값 기준으로, 빠진 돌의 개수를 카운트한 후 거리의 최솟값이 최대가 되는 경우를 찾으면 된다. 코드 from math import inf def ..

문제 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 문제 풀이 문자열이 주어질 때, 문자열의 부분 문자열 중 가장 긴 팰린드롬을 찾는 문제이다. 문제를 풀기 위해서는 `2중 반복문`을 통해 부분 문자열의 시작 위치와 끝 위치를 설정 후 팰린드롬인지 확인하면 된다. 코드 def solution(s): answer = -1 for i in range(len(s)): for j in range(i + 1, len(s) + 1): cur_string = s[i:..