[C언어/BOJ] BOJ 5555번 반지 (문자열 포함여부 찾기)

백준 5555번 반지 풀이 / C언어

중간고사를 앞두고 문자열 문제를 연습중에 A문자열이 B문자열에 등장하는지를 구하는 알고리즘을 활용할수 있어서 한번 풀어보았습니다. 조금 특이한점은 "반지" 에 문자열을 적었기때문에 문자열이 순환된다는 것입니다. ( 끝과 시작이 연결되어있습니다)

문제를 풀이하기전에 문자열 검색에 대한 쉬운 문제 두가지를 먼저 풀어보겠습니다.

두 문자열의 포함관계를 구하는 알고리즘을 실습을 통해 익히기

두 문자열의 포함관계를 구하는 문제입니다. 먼저 입력받는 str1에 str2가 포함되어있는지를 판단해주면 됩니다.

간단한 알고리즘이지만 한번 떠올려볼까요?

아이디어 생각하기

아이디어를 떠올리는것부터 매우 쉽게 접근할수있습니다.

두번째 입력 문자열 str2를 비교 문자열로 하여서, str2의 첫번째값과 같은 문자가 등장할때까지 str1 문자열을 훑습니다.

 

만약 같은 문자를 찾았다면? ==> 그때의 str1문자열 인덱스부터 시작해서 증가하며 str2과 비교를 들어갑니다.

그리고 같은 문자의 개수가 기준 문자열인 str2의 길이와 같다면? 포함되어있는 것입니다.

쉬운 문제이기때문에 바로 코드로 구현해보겠습니다.

 

코드로 구현하기

 

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

#pragma warning(disable:4996) #include <stdio.h> #include <string.h>   int main() {     char str1[81];//첫번째 문자열     char str2[11];//두번째 문자열     int str2_idx = 0;//두번째 문자열의 인덱스로 사용할 변수       int cnt = 0;//몇번 등장하는지를 검사합니다.     scanf("%s %s", str1, str2);     //str1에 str2가 있는지를 검사하는 알고리즘     int start = 0;     for (int i = 0; i < strlen(str1); i++) {         //초기화         str2_idx = 0;           //str1의 문자열을 훑으며, 첫글자가 같은 인덱스찾기         if (str1[i] == str2[str2_idx]) {             start = i;             while (str1[start] == str2[str2_idx]) {                 cnt++;                 start++;                 str2_idx++;             }//두 문자열을 비교해줍니다.                  }     }     //출력파트     printf("%d ", strlen(str1));     if (cnt >= 1) {             printf("%d", 1);         }         else printf("0");          return 0; } Colored by Color Scripter

cs

위의 코드처럼 쉽게 구현 가능합니다.

그러면 같은 유형의 문제를 하나 더 풀어보겠습니다.

위의 문제와 유사합니다. 하지만 함정이 하나 있습니다.

 

위의 문제와 똑같이 풀게되면

AAA 입력예시에서 AA가 두번 등장한 것으로 나오지만, 이 문제에서는 이미 사용된 문자는

사용하지않는 조건을 달았습니다.

따라서 조건을 맞춰야합니다.

조건을 맞춰주기 위해 i=i+cnt-1이라는 문구를 넣었습니다.

왜냐면 cnt가 strlen(str2)와 같다는 것은 str1에 str2가 포함되었다는 것을 의미합니다.

따라서 기존의 i 인덱스에 cnt만큼 값을 더하고 ( 다음 for문의 i++을 위해 1을 빼줌)

진행해주면 해결됩니다. 두가지 문제를 통해 문자열의 포함관계를 다루는 연습이 충분히 되었을 것입니다.

이제 백준 문제를 풀어보겠습니다.

 

 

백준 5555번 반지 /C언어

두 실습문제를 통해 연습을 하고 왔으므로 어렵지않게 해결할 수 있었습니다.

문제

 

당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의

시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을 거꾸로 읽는 걱정은 없다.

찾고자하는 문자열이 주어졌을 때 그 문자열을 포함하는 반지가 몇 개인지를 발견하는 프로그램을 작성하라.

 

제일 중요한 문구는 시작과 끝이 연결되었다는 문구겠네요 !.

 

입력 , 출력 및 예시

입력은 총 2 + N 줄 이다.

첫 번째 줄에는 1 자 이상 10 자 이하의 대문자로 구성된 찾고자 하는 문자열이 적혀있다.

두 번째 줄에는 반지의 개수 N (1 ≦ N ≦ 100)이 적혀있다.

2+i 줄(1 ≦ i ≦ N)엔 i개의 반지에 새겨져있고, 10 문자로 이루어진 문자열이 적혀있다.

 

찾고자하는 문자열을 포함 반지의 개수를 나타내는 정수를 한 줄로 출력하라.

 

접근 및 풀이 코드

주의 해야 할 사항인, 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 만 신경써주면 됩니다.

위의 실습코드를 그대로 응용하고, 반지에 새겨진 문자열의 끝과 시작을 이어주는 코드만 추가해주면 됩니다.

바로 코드를 구현해보겠습니다.

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 42 43 44 45

#pragma warning(disable:4996) #include <stdio.h> #include <string.h>   int main() {     char str1[11], str2[100][11];     int cnt = 0, pass = 0;     scanf("%s", str1); //정답코드       int N;     scanf("%d", &N);       for (int i = 0; i < N; i++) scanf("%s", str2[i]);          int re_cnt = 0;     int j = 0, k = 0;       for(int t=0;t<N;t++){         for (int i = 0; i < strlen(str2[t]); i++) {             cnt = 0;             k = 0;                          if (str2[t][i] == str1[k]) {                 j = i;                 while (str2[t][j] == str1[k]) {                                          j++;                     k++;                     cnt++;                     if (j == (strlen(str2))) j = 0;                 }                 if (cnt == strlen(str1))                 {                     pass++;                     break;                 }             }         }                }     printf("%d", pass);     return 0; }   Colored by Color Scripter

cs

반지 문자열의 시작과 끝 이어주기

문자열의 포함관계에 대한 BOJ 문제풀이 포스팅을 마칩니다.