1639. [Python]행운의 티켓

1. 문제

 

https://www.acmicpc.net/problem/1639

1639번: 행운의 티켓

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 브루트 포스

 

3. 파이썬 코드

 

number = input()
check_length = len(number)
answer_list = []

# 행운의 티켓을 확인할 길이가 홀수인 경우 변수에서 -1 해서 짝수로 만들어준다.
if check_length % 2 == 1:
    check_length -= 1

# 탐색할 길이가 0인 경우 반복문 종료
while check_length > 0:
    # 인풋으로 들어온 길이와 확인할 길이가 같은경우
    if len(number) == check_length:
        # total_1, total_2 라는 변수를 선언하여 왼쪽값과 오른쪽값의 합을 계산
        total_1 = 0
        total_2 = 0
        # 확인할 길이(check_length)//2 를 진행하면 중앙값이 되므로 중앙값을 기준으로 왼쪽 오른쪽을 나눔
        number_1 = number[:check_length//2]
        number_2 = number[check_length//2:]
        # 중앙값 길이만큼 반복문을 통해서 왼쪽값과 오른쪽값의 합을 구함
        for i in range(len(number_1)):
            total_1 += int(number_1[i])
            total_2 += int(number_2[i])
        # 합이 같은경우 행운의 티켓이므로 정답 리스트에 추가
        if total_1 == total_2:
            answer_list.append(check_length)
    # 확인할 길이가 인풋 값과 다른 경우
    else:
        # cnt 라는 변수를 통해서 브루트포스를 진행
        cnt = 0
        # 0부터 check_length 길이만큼 문자를 잘라서 탐색하기위해 반복분을 진행하되 인풋값의 길이와 같으면 종료
        while cnt+check_length <= len(number):
            # 값을 구하는 방식은 위와 동일
            total_1 = 0
            total_2 = 0
            answer = number[cnt:cnt+check_length]
            number_1 = answer[:check_length//2]
            number_2 = answer[check_length//2:]
            for j in range(len(number_1)):
                total_1 += int(number_1[j])
                total_2 += int(number_2[j])
            # 초기값으로 0이 주어지기 때문에 0이 아닌 조건도 추가했음
            if total_1 == total_2 and total_2 != 0 and total_1 != 0:
                answer_list.append(check_length)
            # 반복문이 끝날때마다 인덱스 위치를 변경해야 하기 때문에 +1 해줌
            cnt += 1
    # 모든 반복문이 끝날때마다 check_length 값들을 -2 씩해줌 값이 짝수이기 때문에
    check_length -= 2
# while 문이 끝날경우 answer_list 에 값이 없으면 0 있으면 max 값 출력
if len(answer_list) == 0:
    print(0)
else:
    print(max(answer_list))

 

4. 문제를 풀고난 후 생각

 

• 문제에서 주어진 길이의 문자열 이 홀수인지 짝수인지를 먼저 판단해야한다.
• 행운의 티켓이 좌우 대칭으로 합이 같아야 하므로 짝수인 경우 그대로 진행하지만 홀수인 경우 -1 을 해서 짝수로 바꿔준다.
• 이후 문자의 처음 길이를 받아와서 길이를 -2 씩해나가며 모든 값들을 탐색하며 좌우 대칭인 행운의 값을 구한다.
  
  => 123231을 예시로 살펴보면 문자의 길이는 6이고 1~6번 문자열을 가지고 중앙을 나눠 좌, 우 값들을 비교해본다.
  => 좌 : 123 / 우: 231 두 좌우값의 합이 6으로 동일함으로 이 수는 행운의 숫자가 되며 이때 문자열의 길이는 6이 된다.
  
  
• 위의 과정을 한번 진행한 후 좌우 값이 같으므로 6이라는 길이를 리스트에 추가한다. ( 최대값을 구하는 거여서 굳이 리스트에 넣지 않고 그냥 바로 출력해도 됐을 것 같다는 생각이 든다. )
• 다음으로 6에서 -2를 진행한 4를 가지고 값을 찾아본다.
  
  => 123231 에서 1~4인 1232 를 가지고 좌,우 를 나눠서 비교해본 후 다음 인덱스인 2323을 가져와서 비교하고 3231 을 가져와 값을 비교해 나가는 식으로 길이가 0보다 클때까지 반복문을 시행했다.
  
  
• 위의 과정이 다 끝난 후 마지막에 리스트에 저장된 값들 중 가장 큰 값을 출력하고 만약 리스트의 길이가 0 인 경우 0을 출력하는 식으로 문제를 해결했다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트 포스