맛있는물회

[맛있는물회] <알고리즘> 1120번 "문자열" 본문

IT/알고리즘

[맛있는물회] <알고리즘> 1120번 "문자열"

맛있는물회 2019. 6. 28. 14:00

간단한 그리디 문제이다.

A 문자열과 B문자열과 비교했을때 동일한 문자의 개수의 MAX값만을 구하면 된다.

예를들어 

A : adaabc

B: aababbc

 

일때 

a d a a b c

a a b a b b c

-> 같은 문자 개수 : 3개

 

  a d a a b c

a a b a b b c

-> 같은 문자 개수 : 4개

 

따라서 이 MAX값을 가지고 계산하면 cnt2 - MAX 가 답이다!!!

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

 

int main() {

    char arr1[51= { '\0', };

    char arr2[51= { '\0', };

    int cnt1 = 0, cnt2 = 0,count = 0;

    int i=0, j=0,k=0;

    int MAX = -1;

    int idx;

 

    scanf("%s %s", arr1, arr2);

 

    while (1) {

        if (arr1[i] == '\0')

            break;

        i++;

        cnt1++;

    }

    i = 0;

    while (1) {

        if (arr2[i] == '\0')

            break;

        i++;

        cnt2++;

    }

    for (i = 0; i<=cnt2-cnt1; i++) {

        count = 0;

        for (j = i, k = 0; k < cnt1; j++, k++) {

            if (arr1[k] == arr2[j])

                count++;

        }

        if (count > MAX) {

            MAX = count;

            idx = i;

        }

    }

    //cnt2 - MAX

    printf("%d", cnt1 - MAX);

}

Colored by Color Scripter

cs
Comments