[SWEA] 회문

회문 1

SW Expert Academy

SW Expert Academy

회문은 앞뒤가 똑같은 전화번호가 아니라 거꾸로 해도 똑같은 단어가 되는 단어다.

즉 abcba나 abba 같은 것들

회문 1에서는 일정한 2차원 배열을 주고 길이가 n인 회문이 몇개 존재하는지를 파악해야 한다.

 

회문을 푸는 방법으로 다음과 같이 크게 두가지 방법을 사용했다.

방법1. 문자열 뒤집기

거꾸로 해도 똑같은 문자열이 나와야 하므로 문자열 자체를 뒤집어 둘을 비교하는 방법으로 풀었다.

문자열은 다음처럼 뒤집는게 제일 속편하다.

정답코드

 

회문 2

SW Expert Academy

SW Expert Academy

회문 2는 회문 1과 같은 2차원 배열이 주어지는데 크키가 100이고 n 대신 가장 긴 회문의 길이를 찾아내야 한다.

여기서도 방법 1 처럼 문자열을 뒤집어서 해결하면 되는데 통과하긴 해도 시간이 너무 오래걸린다.

왜냐하면 매 열마다 크기가 다른 회문을 찾아야 하기 때문.

예를들어 (0,0)에서 회문을 찾기 시작한다면 크기가 100부터 시작해서 99, 98, 97.. 이렇게 모든 경우를 찾아야 하고

그 다음 (0,1)에서도 크기가 99부터 시작해서 98, 97.. 이렇게 나가야 하기 때문이다.

따라서 새로운 방법을 고안했다.

방법 2. 반복문 이용하기

방식 자체는 우아하지 않지만, 내가 넣어준 기준 위치를 바탕으로 좌우의 문자열이 같은지를 판단한다.

즉 내가 (0,5)를 넣어주면 (0,4)와 (0,6)이 같은지를 보고 그 다음 (0,3)과 (0,7)이 같은지를 본다.

또한 회문의 길이가 짝수인 경우는 (0.5)와(0.6)이 같은지를 보고 (0,4)와 (0,7)이 같은지를 보면 된다.

이렇게 하면 기준 한번당 반복문이 한번만 돌아가면 되므로 방법 1보다 훨씬 빠르게 실행할 수 있다.

정답 코드

만약 방법 1로 푼다면 다음처럼 오래걸린다.