백준 및 코드포스

https://www.acmicpc.net/problem/24524

문제 자체는 어렵지 않았는데 시간제한이 너무 빡빡했습니다.

몰랐는데 strlen 함수가 시간을 엄청나게 잡아먹더라고요. 변수에다가 strlen 값을 미리 저장시켜두고 써먹어야겠습니다.

이거 때문에 2~30분은 버렸네요.

제가 푼 문제 풀이 로직은 이렇습니다.

먼저 알파벳의 개수를 세어줄 answer 배열을 준비합니다.

1. S를 앞에서부터 읽어나가며 T에 동일한 문자가 있는지 찾습니다.

2. T[0]과 동일하다면 answer[T[0]]++,  첫 번째 이후의 문자와 동일하다면 answer[T[j - 1]]의 값과 비교해서 answer[T[j]] 가 더 작다면 answer[T[j]]++.

answer[T의 마지막 알파벳] 이 정답입니다.

ex) waawa wa 의 경우 위의 연산을 마치면 w 2개 a 2개로 정답은 2가 됩니다.

      aaassss sa 의 경우 위의 연산을 마치면 s 4개 a 0개로 정답은 0이 됩니다.

밑에 반례와 코드입니다.

waaaawawawawwwaaaaaawwawawwawawwaaaawa
aw

15


tasdfjasdfletllelteeelteletelteeelteltleltelltelltelellelelelllteltleltlqwereltlqwerleqwerlellelqwereeeteqwerlqwerltltelasdfkasdfeowijqjofiajsdnfvznxnnftlelteltleltellteltle
tle

23


jiwon
jiwon

1


goodgooddogbaaaaagood
god

3

#include <stdio.h>
#include <string.h>

int main() {
    char s[1000011] = {}, t[26] = {};
    int answer[150] = {};
    scanf("%s %s", s, t);
    int a = strlen(s), b = strlen(t);
    for(int i = 0; i < a; i++) {
        for(int j = 0; j< b; j++) {
            if(s[i] == t[0]) {
                answer[t[0]]++;
                break;
            }
            else if(s[i] == t[j] && answer[t[j]] < answer[t[j - 1]]) {
                answer[t[j]]++;
                break;
            }
        }
    }
    printf("%d", answer[t[b - 1]]);
}