5월 3주차

[moodmine]

SWEA 1213. String

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    /*
       여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
    */
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int num;
        scanf("%d", &num);
        char arr[1000];
        char s[10];
        int size_s=0;
        int size_arr=0;
        int result = 0;
        int i;
        scanf("%s", s);
        scanf("%s", arr);

        for (i = 0; i < 10; i++)
        {
            if (s[i] != 0)
                size_s++;
            else
                break;
        }

        for (int i = 0; i < 1000; i++)
        {
            if (arr[i] != 0)
                size_arr++;
            else
                break;
        }

        int start = 0;
        while (start+size_s-1 <= size_arr)
        {
            for (i = start; i <= start + size_s - 1; i++)
            {
                if (s[i-start] != arr[i])
                {
                    break;
                }
                else if (i == start + size_s - 1)
                {
                    result++;
                }
            }
            start++;
        }
        printf("#%d %d\n", num, result);
    }

    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

SWEA 1215. 회문1

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    /*
       여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
    */
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int num;
        int result = 0;
        scanf("%d", &num);
        char arr[8][9];
        for (int i = 0; i < 8; i++)
        {
            scanf("%s", arr[i]);
        }

        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j + num - 1 <= 8; j++)
            {
                for (int k = 0; k <= (num / 2); k++)
                {
                    if (arr[i][j + k] != arr[i][(j + num - 1) - k])
                        break;
                    else if (k == num / 2)
                        result++;
                }
            }
        }

        for (int j = 0; j < 8; j++)
        {
            for (int i = 0; i + num - 1 <= 8; i++)
            {
                for (int k = 0; k <= (num / 2); k++)
                {
                    if (arr[i + k][j] != arr[(i + num - 1) - k][j])
                        break;
                    else if (k == num / 2)
                        result++;
                }
            }
        }

        printf("#%d %d\n", test_case, result);
    }

    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

SWEA 1216. 회문2

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    /*
       여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
    */
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int num = 100;
        int result = 0;
        char arr[100][101];
        int a;
        scanf("%d", &a);
        for (int i = 0; i < 100; i++)
        {
            scanf("%s", arr[i]);
        }
        while(result == 0)
        {
            for (int i = 0; i < 100; i++)
            {
                for (int j = 0; j + num - 1 < 100; j++)
                {
                    for (int k = 0; k <= (num / 2); k++)
                    {
                        if (arr[i][j + k] != arr[i][(j + num - 1) - k])
                            break;
                        else if (k == num / 2)
                            result++;
                    }
                }
            }

            for (int j = 0; j < 100; j++)
            {
                for (int i = 0; i + num - 1 < 100; i++)
                {
                    for (int k = 0; k <= (num / 2); k++)
                    {
                        if (arr[i + k][j] != arr[(i + num - 1) - k][j])
                            break;
                        else if (k == num / 2)
                            result++;
                    }
                }
            }
            if (result == 0)
                num--;
        }

        printf("#%d %d\n", test_case, num);
    }

    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

[murry2018]

SWEA 1213. String

#include <cstdio>
#include <cstring>

using namespace std;

#define DEBUG false

// pi[i] : max{k | pat[0..k) = pat(i-k..i]}
void compute_pi(char pat[11], int len, int pi[11]) {
  int begin = 0;
  pi[0] = 0;
  for (int i = 1; i < len; i++) {
    while (begin > 0 && pat[begin] != pat[i])
      begin = pat[begin-1];
    if (pat[begin] == pat[i])
      pi[i] = ++begin;
    else
      pi[i] = 0;
  }
}

// kmp search algorithm
int count_occur(
  char s[1001], int len_s, char p[11], int len_p
) {
  static int pi[11];
  compute_pi(p, len_p, pi);

#if DEBUG
  printf("===== pi =====\n");
  for (int i = 0; i < len_p; i++) {
    for (int j = 0; j <= i; j++)
      fputc(p[j], stdout);
    printf(" | %d\n", pi[i]);
  }
  printf("==============\n");
#endif

  int nmatches = 0;
  int cp = 0;  // current pattern index
  for (int i = 0; i < len_s; i++) {
    while (cp > 0 && p[cp] != s[i])
      cp = pi[cp - 1];
    if (p[cp] == s[i]) {
      if (cp+1 == len_p) {
        nmatches++;
        cp = pi[cp];
      } else {
        cp++;
      }
    }
  }
  return nmatches;
}

int main() {
  char sbuf[1002], pbuf[12];
  int len_s, len_p;
  for (int i = 0; i < 10; i++) {
    scanf("%*d\n"); // ignore first line
    fgets(pbuf, 12, stdin);
    fgets(sbuf, 1002, stdin);
    len_s = strlen(sbuf);
    len_p = strlen(pbuf);
    // remove trailing line feed
    if (sbuf[len_s - 1] == '\n')
      sbuf[--len_s] = 0;
    if (pbuf[len_p - 1] == '\n')
      pbuf[--len_p] = 0;
  #if DEBUG
    printf("len(s) : %d, len(p) : %d\n", len_s, len_p);
  #endif
    int nmatches = count_occur(sbuf, len_s, pbuf, len_p);
    printf("#%d %d\n", i+1, nmatches);
  }
}

[murry2018]

SWEA 1215. 회문1

/* brute-force algorithm */
#include <cstdio>
#include <cstring>

#define DEBUG false

using namespace std;

int count_palindrome_inrow(
  char mat[8][8], int size, int row
) {
  int cnt = 0, col = 0;
  for (int col = 0; col + size <= 8; col++) {
    // is mat[row][s..e] a palindrome?
    int s = col, e = col + size - 1;
    bool is_pal = true;
    while (s < e) {
      if (mat[row][s] != mat[row][e]) {
        is_pal = false;
        break;
      }
      s++, e--;
    }
    if (is_pal) {
    #if DEBUG
      printf("inrow: (%d, %d)\n", row, col);
    #endif
      cnt++;
    }
  }
  return cnt;
}

int count_palindrome_incol(
  char mat[8][8], int size, int col
) {
  int cnt = 0, row = 0;
  for (int row = 0; row + size <= 8; row++) {
    // is mat[s..e][col] a palindrome?
    int s = row, e = row + size - 1;
    bool is_pal = true;
    while(s < e) {
      if (mat[s][col] != mat[e][col]) {
        is_pal = false;
        break;
      }
      s++, e--;
    }
    if (is_pal) {
    #if DEBUG
      printf("incol: (%d, %d)\n", row, col);
    #endif
      cnt++;
    }
  }
  return cnt;
}

int count_palindrome_inmatrix(
  char mat[8][8], int size
) {
  int cnt = 0;
  for (int i = 0; i < 8; i++) {
    cnt += count_palindrome_incol(mat, size, i);
    cnt += count_palindrome_inrow(mat, size, i);
  }
  return cnt;
}

int main() {
  char mat[8][8];
  int size;
  for (int i = 0; i < 10; i++) {
    scanf("%d", &size);
    while(getchar()!='\n');
    for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 8; j++) {
        scanf("%c", &mat[i][j]);
      }
      while(getchar()!='\n');
    }
  #if DEBUG
    for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 8; j++) {
        printf("%c", mat[i][j]);
      }
      printf("\n");
    }
  #endif
    int cnt = count_palindrome_inmatrix(mat, size);
    printf("#%d %d\n", i+1, cnt);
  }
}

[happy-oh]

SW1213

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;

    freopen("test_input.txt", "r", stdin);
    T = 10;
    // cin >> T;
    int temp;
    int i, j, k;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        char str_arr[1001];
        char ans_arr[11];
        int str_size;
        int ans_size;
        int find_bit;
        int find_nums = 0;
        scanf("%d", &temp);
        scanf("%s", ans_arr);
        scanf("%s", str_arr);

        ans_size = strlen(ans_arr);
        str_size = strlen(str_arr);
        for (i = 0; i < str_size - ans_size + 1; ++i)
        {
            find_bit = 0;
            for (j = 0; j < ans_size; ++j)
            {
                if (str_arr[i + j] != ans_arr[j])
                    break;
                else if (j == ans_size - 1)
                    find_bit = 1;
            }
            if (find_bit == 1)
                find_nums = find_nums + 1;
        }
        printf("#%d %d\n", test_case, find_nums);

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

[happy-oh]

SW1215

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;

    freopen("input.txt", "r", stdin);
    T = 10;
    // cin >> T;

    int i, j, k;
    int test_size;
    int find_bit;
    int find_nums;
    char str_arr[8][9];
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d", &test_size);
        for (i = 0; i < 8; ++i)
        {
            scanf("%s", str_arr[i]);
        }
        find_nums = 0;
        for (i = 0; i < 8 - test_size + 1; ++i )
        {
            for (j = 0; j < 8; ++j)
            {
                find_bit = 0;
                for (k = 0; k <= test_size / 2 - 1; ++k)
                {
                    if (str_arr[i + k][j] != str_arr[i + test_size - 1 - k][j])
                    {
                        find_bit = 0;
                        break;
                    }
                    else
                        find_bit = 1;
                }
                if (find_bit == 1)
                    find_nums = find_nums + 1;
            }
        }
        for (j = 0; j < 8 - test_size + 1; ++j)
        {
            for (i = 0; i < 8; ++i)
            {
                find_bit = 0;
                for (k = 0; k <= test_size / 2 - 1; ++k)
                {
                    if (str_arr[i][j+k] != str_arr[i ][j + test_size - 1 - k])
                    {
                        find_bit = 0;
                        break;
                    }
                    else
                        find_bit = 1;
                }
                if (find_bit == 1)
                    find_nums = find_nums + 1;
            }
        }
        printf("#%d %d\n", test_case, find_nums);

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

[happy-oh]

SW1216

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;

    freopen("input.txt", "r", stdin);
    T = 10;
    // cin >> T;

    int i, j, k;
    int test_size;
    int temp;
    int find_bit;
    int find_size;
    int break_bit;

    char str_arr[100][101];
    for (test_case = 1; test_case <= T; ++test_case)
    {

        scanf("%d", &temp);
        for (i = 0; i < 100; ++i)
        {
            scanf("%s", str_arr[i]);
        }
        find_size = 1;
        break_bit = 0;
        for (test_size = 100; test_size > 0; --test_size)
        {
            for (i = 0; i < 100 - test_size + 1; ++i)
            {
                for (j = 0; j < 100; ++j)
                {
                    find_bit = 0;
                    for (k = 0; k <= test_size / 2 - 1; ++k)
                    {
                        if (str_arr[i + k][j] != str_arr[i + test_size - 1 - k][j])
                        {
                            find_bit = 0;
                            break;
                        }
                        else
                            find_bit = 1;
                    }
                    if (find_bit == 1)
                    {
                        find_size = test_size;
                        break_bit = 1;
                    }
                    if (break_bit == 1)
                        break;
                }
                if (break_bit == 1)
                    break;
            }
            for (j = 0; j < 100 - test_size + 1; ++j)
            {
                if (break_bit == 1)
                    break;
                for (i = 0; i < 100; ++i)
                {
                    find_bit = 0;
                    for (k = 0; k <= test_size / 2 - 1; ++k)
                    {
                        if (str_arr[i][j + k] != str_arr[i][j + test_size - 1 - k])
                        {
                            find_bit = 0;
                            break;
                        }
                        else
                            find_bit = 1;
                    }
                    if (find_bit == 1)
                    {
                        find_size = test_size;
                        break_bit = 1;
                    }
                    if (break_bit == 1)
                        break;
                }
                if (break_bit == 1)
                    break;
            }
            if (break_bit == 1)
                break;
        }

        printf("#%d %d\n", test_case, find_size);

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

[murry2018]

SWEA 1216. 회문2

/* 팰린드롬 DP 알고리즘
 * https://www.crocus.co.kr/1001를 참고하였음 */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int compute_max_palindromes_inrow(char s[100]) {
  static bool ispal[100][100];
  for (int i = 0; i < 100; i++)
    for (int j = 0; j < 100; j++)
      ispal[i][j] = false;
  int cnt = 0;
  int maxlen = 1;
  for (int i = 0; i < 100; i++) {
    ispal[i][i] = true;
  }
  for (int i = 0; i < 100; i++) {
    if (s[i] == s[i+1]) {
      ispal[i][i+1] = true;
      maxlen = 2;
    }
  }
  for (int k = 2; k < 100; k++) {
    for (int i = 0; i + k < 100; i++) {
      int j = i + k;
      if (s[i] == s[j] && ispal[i+1][j-1]) {
        ispal[i][j] = true;
        maxlen = max(maxlen, j-i+1);
      }
    }
  }
  return maxlen;
}

int compute_max_palindromes(char mat[100][100]) {
  int maxlen = 0;
  for (int i = 0; i < 100; i++) {
    maxlen = max(maxlen, compute_max_palindromes_inrow(mat[i]));
  }
  char buf[100];
  for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++)
      buf[j] = mat[j][i];
    maxlen = max(maxlen, compute_max_palindromes_inrow(buf));
  }
  return maxlen;
}

int main() {
  char mat[100][100];
  for (int i = 0; i < 10; i++) {
    scanf("%*d\n");
    for (int i = 0; i < 100; i++) {
      for (int j = 0; j < 100; j++)
        mat[i][j] = getchar();
      while(getchar() != '\n');
    }
    int maxlen = compute_max_palindromes(mat);
    printf("#%d %d\n", i+1, maxlen);
  }
}

[moodmine]

STEA. 1213 String by KMP 알고리즘

ti 란 문자열을 찾을 때 tti 처럼 일부만 일치하는 문자열 다음 찾으려는 문자열이 나올 때의 상황 처리를 잘해줘야할듯...

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    /*
       여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
    */
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int num;
        scanf("%d", &num);
        char arr[1001];
        char s[11];
        scanf("%s", s);
        scanf("%s", arr);

        int i = 0;
        int j = 0;
        int start = 0;
        int result = 0;

        while (arr[i] != NULL)
        {
            if (arr[i] == s[j])
            {
                if (s[j + 1] == NULL)
                {
                    i++;
                    j = 0;
                    result++;
                }
                else
                {
                    i++;
                    j++;
                }
            }
            else
            {
                if (j != 0)
                    j = 0;
                else
                    i++;
            }
        }

        printf("#%d %d\n", num, result);
    }

    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}