[SWEA] 파이썬 1216. 회문2 | 그리디 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV14Rq5aABUCFAYi&categoryId=AV14Rq5aABUCFAYi&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=2 

SW Expert Academy

 

 

문제 해결 포인트

- 발견된 회문중 가장 긴 길이를 발견시마다 탐욕스럽게 취하므로 그리디 알고리즘이라고 할 수 있다.

 

- 읽음과 동시에 행별 가장 긴 회문 찾기 & 열값을 행으로 저장(이후 사용 하기 위함)

- 가장 긴 회문을 찾는 것이므로 100부터 2까지 줄여가며 회문 발견시 탐색 종료

- 회문은 길이가 n일 때 다음과 같이 나누어 볼 수 있다.

홀수	list[ : n//2] == list[n//2 + 1 : ][::-1]
짝수	list[ : n//2] == list[n//2 : ][::-1]

 

그림으로 다시 생각해보면 길이에 따라 다음과 같이 비교해보면 된다는 말이다.

- 열에서 가장 긴 길이를 구한 뒤 열에 대해 다시 한 번 동일한 수행을 해주면 열과 행중 가장 긴 길이를 얻어낼 수 있다.

 

 

작성 코드

 

for _ in range(1, 11):  # 10개 테스트
    test = int(input())
    board = [[] for i in range(100)]  # 열을 행 형태로 저장하기 위한 공간
    maxNum = 0

    for i in range(100):  # 행
        line = [i for i in input()]
        for l in range(100):  # 각 열 값을 append하여 행으로 만들기
            board[l].append(line[l])

        for j in range(100, 3, -1):  # 100부터 2까지 회문 길이를 줄여가며 탐색
            tf = False  # 회문을 찾았는지 체크
            for k in range(0, 101-j):
                temp = line[k:k+j]  # 회문이 될 가능성 있는 것

                if temp[:j//2] == temp[j//2:][::-1] or temp[:j//2] == temp[j//2+1:][::-1]:  # 회문
                    tf = True
                    break
            if tf:  # 회문 찾았을 때
                maxNum = max(maxNum, j)  # 지금까지 찾은 길이 vs 해당 행 가장 긴 것
                break  # 가장 먼저 찾은 회문이 그 행의 가장 큰 수이므로 다음 행 탐색

    for i in range(100):  # 열, 행에서 얻어낸 결과를 가지고 수행
        for j in range(100, 3, -1):  # 100부터 2까지 회문 길이를 줄여가며 탐색
            tf = False  # 회문을 찾았는지 체크
            for k in range(0, 101-j):
                temp = board[i][k:k+j]  # 회문이 될 가능성 있는 것

                if temp[:j//2] == temp[j//2:][::-1] or temp[:j//2] == temp[j//2+1:][::-1]:  # 회문
                    tf = True
                    break
            if tf:  # 회문 찾았을 때
                maxNum = max(maxNum, j)  # 지금까지 찾은 길이 vs 해당 열 가장 긴 것
                break  # 가장 먼저 찾은 회문이 그 열의 가장 큰 수이므로 다음 열 탐색

    print("#{} {}".format(test, maxNum))

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚