[C++] SWEA 1216번 :회문2

🔗 문제

[S/W 문제해결 기본] 3일차 - 회문2

SW Expert Academy

 

🖍 풀이

회문은 각 셀의 위치에서 오른쪽과 아래 방향으로 검색할 수 있다.

아래 방향으로 검색하는 식 세우는게 귀찮아서 전치 행열(arr2)을 만들어줬다.

 

 

문제의 목표는 가장 긴 회문의 길이다.

그렇다면 최대 회문 길이인 100부터 감소시키며 가장 먼저 찾은 회문으로 탐색 횟수를 줄여준다.

for(answer = SIZE; answer>0; --answer)
{
    if(FindLongestPelindrome(arr, answer))
        break;
    else if(FindLongestPelindrome(arr2, answer))
        break;
}

 

 

회문을 찾는 함수를 isPalindrome()으로 선언해주었다. 아까 전치행열을 만들어줬으니 이제 같은 열에서 행의 길이로만 탐색해주면 된다. 이 때 탐색을 시작하는 j와 회문의 길이 length가 배열 크기를 벗어나지 않도록 해준다.

bool FindLongestPelindrome(char arr[][SIZE+1], const int length)
{    
    for(int i=0; i<SIZE; ++i)
    {
        for(int j=0; j<SIZE-length; ++j) // 탐색 길이 제한
        {            
            if(isPalindrome(arr, length, i, j))
                return true;
        }
    }
    
    return false;
}

 

이 문제는 시간 초과 때문에 고생을 했기 때문에 다신 이러지 않으려고 쓰는 글이다.

1. 시간초과 소스
2. 시간초과 원인
3. 해결 방법

 

---

1. 시간초과 소스

• 회문을 찾는 방법
  • length길이의 문장을 100X100X100번 만든다. (100X100 배열에다가 최대 팰린드롬 길이가 100)

  std::string right;
  
  for(int k=0; k<length; ++k)
    right += map[i][j+k];// string연산을 length번한다. 
  
  if (right == std::string(right.rbegin(), right.rend())) // right의 역순 string을 생성한다.
    return length;

 

2.시간 초과 원인

string은 원래 메모리와 시간을 많이 잡아먹는다. 내부적으로 string 길이의 변화가 생기면 그 길이만큼 연속적인 메모리 주소 확보를 위해 새로 메모리를 잡아 복붙하는 과정이 필요하다. 그래서! string은 내가 1짜리 문자열을 만든다고 해도 혹시 몰라서 공간을 더 확보하며 메모리를 잡아먹는 짓도 한다. 얼만큼 확보하는지는 정확하게는 버전이나 운영체제에 달려잇을..걸? 아무튼 ..

 

string은 문자열 길이만큼 복사연산과 할당이 이루어지니까 잦은 string 연산이 문제라고 판단 했다. (연결 연산자와 Copy On Write 찾아보세요.)

 

그런데 나는 string 문자열을 length번 돌려가며 계속해서 만들어냈고, 회문을 검사할 때 또 string을 만드는 짓을 했다~!!

 

3. 해결 방법

회문을 검사하는 방법을 바꿨다. string을 새로 생성하지 않고 기존의 arr[]를 활용했다.

회문은 그 길이의 반이 나머지 반과 똑같기만 하면 된다!

기존은 length만큼 string을 생성했다면 변경 후는 length/2까지로 반복횟수를 줄이고 string을 생성하지도 않았다.

bool isPalindrome(char arr[][SIZE+1], const int length,const int i,const int j)
{
    for(int k=0; k<=length/2; ++k) 
    // 절반(포함)까지 회문 길이의 역순이랑 같다면 회문이 맞다!
    {	
        if(arr[i][j+k] != arr[i][**N-1-(j+k)**])
            return false;
    }

    return true;
}

 

💾  소스

실행시간: 0.13504s

#include <iostream>
#include <string>

const int SIZE = 100;
char arr[SIZE+1][SIZE+1];
char arr2[SIZE+1][SIZE+1]; // 전치 행렬

bool isPalindrome(char arr[][SIZE+1], const int length,const int i,const int j)
{
    for(int k=0; k<=length/2; ++k)
    {	
        if(arr[i][j+k] != arr[i][N-1-(j+k)])
            return false;
    }

    return true;
}

bool FindLongestPelindrome(char arr[][SIZE+1], const int length)
{    
    for(int i=0; i<SIZE; ++i)
    {
        for(int j=0; j<SIZE-length; ++j)
        {            
            if(isPalindrome(arr, length, i, j))
                return true;
        }
    }
    
    return false;
}

int main()
{
    int T = 10; //std::cin >> T;
    for(int tc=1; tc<=T; ++tc)
    {
        int answer = 0;
        std::cin >> answer;
        for(int i=0; i<SIZE; ++i)
        {
            for(int j=0; j<SIZE; ++j)
            {
                std::cin >> arr[i][j];
                arr2[SIZE-j-1][i] = arr[i][j];
            }
        }
        
        for(answer = SIZE; answer>0; --answer)
        {
            if(FindLongestPelindrome(arr, answer))
                break;
            else if(FindLongestPelindrome(arr2, answer))
                break;
        }
        
        std::cout << '#' << tc << ' ' << answer+1 << '\\n';
    }
    return 0;
}