CEO

문제 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..

문제 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 문제 풀이 M개의 문자들 중 N개의 문자의 접미사가 하나라도 되는지 확인하는 문제이다. 접미사 이므로 찾고자 하는 패턴의 수와 N개의 문자 중 일치하는지 확인하면 쉽게 해결할 수 있다. 코드 split을 활용한 풀이 from sys import stdin if __name__ == '__main__': n, m = map(int, stdin.readline().split()..

문제 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 문제 풀이 N개에 문자열로 이루어진 집합 S가 있을 때, M개에 문자열 중 집합 S에 포함되는 문자가 총 몇 개인지 구하는 문제이다. 문제를 풀기 위해서는 `딕셔너리`와 `in`을 활용하면 쉽게 풀 수 있다. M개의 문자열 중, N에 포함되는지 확인하기 위해서는 `if pattern in strings`와 같이 확인하면 된다. 파이썬의 `in` 연산은 리스트의 경우 `O(N)`의 시간이 소요되지만 딕셔너리의 경우 `O(1)`의..

문제 1305번: 광고 첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다. L은 백만보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 전광판에 N개의 문자열을 광고를 표시한다. 이때 시간이 지남에 따라 문자열은 한 칸씩 옆으로 이동한다. 어느 순간 광고판을 볼 때, 쓰여 있는 문자가 입력으로 주어진다면 가능한 광고의 길이 중 가장 짧은 것을 출력하는 문제이다. 이는 `KMP 알고리즘`에서 접미사와 접두사가 되는 문자열의 최대 길이를 생성하면 쉽게 해결할 수 있는 문제이다. 만약 `KMP 알고리즘`에 대해 이해하고 있지 않다면 문제를 풀 수 없다. 코드 def make_table(patten): table = [0] * l j = 0 for i ..

문제 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 문제 풀이 입력된 문자열의 두 번 이상 나오는 부분 문자열 중 가장 긴 길이를 찾는 문제이다. 이는 앞서 다룬 16916 부분 문자열, 1786 찾기에서 문자열 일치에 따라 정보를 생성하는 `make_table`을 활용하면 해결할 수 있는 문제이다. 코드 def make_table(patten): length = len(patten) table = [0] * len(patten) j = 0 for i in range(1..

문제 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 문제 풀이 문자열과 패턴이 주어지면, 이를 통해 몇 개가 일치하고 어느 위치에 일치하는지 반환하는 문제이다. 앞서 다룬 16916 부분 문자열과 같이 `KMP 알고리즘`을 이해하고 있으면 쉽게 해결할 수 있는 문제이다. 앞서 다룬 문제와 다른 점이 있다면 패턴과 일치하는 경우 바로 결과를 반환하지 않고, 값을 추가하여 모든 탐색이 끝난 후에 반환하는 부분을 수정하면 된다. 코드 def make_table(): length = len(p) table =..

문제 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net 문제 풀이 0부터 N까지 집합을 이룰 때, 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 확인하고 반환하는 문제이다. 이는 `Union-Find`를 이해하고 구현하면 문제를 쉽게 해결할 수 있다. 즉, 해당 자료구조를 그대로 구현하면 문제를 풀 수 있다. 코드 from sys import stdin def find(target): if target == parent[target]: return target re..