AP 프로그래밍

4. codeup 2699 : 사투리 문제 해결

Quettabyte 2023. 4. 3. 01:23

이번에는 코드업 2699번 문제를 해결해 봅시다. 

<출처>코드업 사이트

알고리즘에 대해 구상을 해봅시다.

배열에 탐색 시작부터 지금까지 공통적으로 몇개의 문자가 공통인지를 arr 배열에 저장하게 됩니다. 이러한 방식으로 끝까지 탐색을 마치면 arr의 끝에 총 공통 부분이 얼마인지를 보여주게 됩니다. 약간 경우의 수 구하는것과 느낌이 비슷하네요..

 

 

그럼 코드를 봐봅시다.

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


int arr[1001][1001];  //공통 문자열 길이 저장 배열

int max(int a,int b){   //둘중 큰값이 무엇인지 반환하는 함수
    return a>b? a:b;          
}

int main() {
    char s1[1001],s2[1001];  
    scanf("%s %s",s1,s2);  //문자열 두개 입력
    int len1= strlen(s1);   //문자열 길이
    int len2= strlen(s2);

    for(int i=1;i<=len1;i++){       //문자열 탐색
        for(int j=1;j<=len2;j++){
            if(s1[i-1]==s2[j-1]) arr[i][j]= arr[i-1][j-1]+1;   //조건에 따라 arr배열 채우기 
			else arr[i][j]=max(arr[i-1][j], arr[i][j-1]);
        }
    }

    printf("%d", arr[len1][len2]);  //공통 문자열 길이 출력
}

 

처음에 

arr[i][j]=max(arr[i-1][j], arr[i][j-1]);

이 부분에서 어떤 연산을 해주어야 할지 고민이 많았는데 수학 시간에 배웠던 것 같은 경로의 경우의 수를 구하는 문제가 생각 났습니다. 그래서 arr의 이전 열, 혹은 행 중 큰 숫자가 지금까지 탐색 중 공통부분 중 긴 부분이겠구나 라고 생각하여 함수를 만들어 사용하게 되었습니다.  이렇게 어렵던 부분이 해결되니 속이 뻥 뚤리는 기분이었습니다.

 

코드는 별로 길지 않아 보이지만 구현할때 많은 고민이 있었고 구현된 코드를 보아도 이해하기 어려울 수 있겠다라고 생각이 드네요.. 제 설명이 좋지 못한점을 사과드리고.. 앞으로 더 많은 게시물로 찾아 뵙겠습니다.