문자열

1. 개요 안녕하세요? 이 문제의 유형은 문자열, 구현입니다. 시간복잡도와 상관없이 naive하게 구현해도 풀이할 수 있습니다. 2. 문제풀이입력으로 문자열이 주어집니다. 그 다음 문자열의 문자들을 하나씩 추가해 출력하시면 됩니다. 이때, 보이지 않은 문자 중 추가했을 때의 문자열은 사전 순으로 가장 앞에 오도록 하는 문자를 추가해야 합니다. 저는 vector을 선언해 현재 출력할 수 있는 문자열들을 모두 저장해 정렬하여 출력하는 방식을 사용했습니다.3. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typed..

1. 문제 풀이 문제 유형은 그리디입니다. 코드포스에서 나올법한 문제였습니다.  정수 N, K에 대해서 임의의 문자열 S는 다음과 같은 조건을 만족합니다.문자열 S의 길이는 N이고, 'A' 또는 'B' 문자로만 이루어져 있다.문자열 S는 0 N, K를 입력받은 다음, 'B'로만 이루어진 길이 N의 문자열을 선언합니다.루프를 돌면서 현재 위치 idx에 대해서 S[idx]를 A로 바꾸었을 때, 두 번째 조건을 만족하는 쌍이 몇 개 나오는지 검사합니다. 여기서 [ 0, idx ) 구간에서 'A'로 바꾼 횟수를 세어야 합니다. S[idx] 문자를 'B'에서 'A'로 바꾸게 된다면 이전에 계산했었던 쌍의 개수가 변동되기 때문 AABBB는 2 번째 조건을 만족하는 ( i , j ) 쌍이 6개 존재합니다. 여기서 A..

1. 문제 풀이 문제 유형은 다이나믹 프로그래밍이었습니다. 저는 좀 과하게 풀었습니다. kmp알고리즘을 적용하여 문자열 S에서 각 단어목록에 대해서 시작 위치를 찾았습니다. 그리고 루프를 돌면서 현재 위치에서 시작하는 문자열을 찾아 매핑하는 방식으로 풀이하였습니다. 그러나 S에서 A[i]를 찾는 과정을 naive하게 구현해도 AC를 받을 수 있습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typede..