(python3) (17min) 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 앞으로는 시간을 재면서 풀어보기로 했다. - 로 구현하는 슬라이딩 윈도우 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다. 위 두 조건은 같은 조건을 가리킨다. 하나의 조건에서 최단, 최장 길이를 구하는 것이다. 예시 : abaccaddda, 2 위 예시에서 a만 고려하면 a..
(python3) 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 이 문제는 처음 떠올린 아이디어에 예외처리를 더해가면서 해결해서 재밌는 흐름이었습니다. 물론 모범답안은 매우 짧았지만요...ㅋㅋㅋ 시간 초과 첫 문자열 s, 두번째 문자열 t로 지칭합니다. 첫번째 접근으로는 s에서 파생될 수 있는 모든 경우의 수를 재귀로 탐색했습니다. - 1, 2 선택지로 분기를 갈라서 재귀 - 모든 경우의 수에 대해 탐색 최악의 경우 O(2^50)이라 시간초과가 발생합니다. 이걸 조금 ..
(python3) 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 아이디어 어딘가에 a를 다 뭉쳐놔야합니다. a를 뭉쳐놓을 위치 안에 있는 b를 밖에 있는 a와 교환해주면 됩니다. 즉 보고있는 위치 안의 b의 개수를 세는 것이 교환 최소 횟수가 됩니다. a를 뭉쳐놓을 수 있는 모든 위치에 대해 위 과정을 수행합니다. abababababa : a가 총 6개 (ababab)ababa : 괄호 안에 a를 뭉쳐넣을것. 괄호의 길이 = 6. 괄호 안의 b를 밖으로 다 빼려면 3번 교환하면 됨. a(bababa)baba :..
(python3) 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 두포인터 혹은 슬라이딩 윈도우 윈도우 길이를 k로 유지하고 옆으로 한칸씩 이동시키면서 먹을 수 있는 가짓수를 확인합니다. 이 문제의 파이썬 풀이 10등이네요~ 와~ 디테일한건 코드 주석으로 남기겠습니다. 코드 import sys def solution(input) : N,d,k,c = list(map(int,input().split())) sushi = [int(input().strip()) for _ i..
(python3) 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 아이디어 1. A를 왼쪽으로 모은다 2. B를 왼쪽으로 모은다 3. A를 오른쪽으로 모은다 4. B를 오른쪽으로 모은다 단순화하면 이렇게 4가지 경우가 가능합니다. 한가지만 풀린다면 똑같은 방법론을 적용해서 나머지를 해결해줄 수 있으니 1번 예시만 생각해보겠습니다. A를 왼쪽으로 모으는 경우 왼쪽부터 탐색하면서 A를 옮기면 항상 (연속된A)(연속된B)(새로만난A) 의 배치가 유지됩니다. 여기서 그리디가 적용됩니다. 왼..
(python3) 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net DP로 해결하기 n지점 이하의 dp 배열이 최단으로 저장되어있다는 가정하에, dp[n] = min(dp[n], dp[n-1]+1) 입니다. 바로 앞 지점에서 1만큼 더 이동하거나 이미 지름길로 더 짧게 도달하거나 둘 중 하나입니다. 그리고 지름길 시작점이 n 이라면 끝점의 dp 값을 변경해주어야 합니다. dp[끝점] = min(dp[끝점], dp[시작점]+지름길 길이) 앞서서 말한 가정을 성립시키기 위해서는 지름길들이 시작점 기준..
