-
1639. [Python]행운의 티켓Python_알고리즘/Silver IV 2023. 4. 17. 03:10
1. 문제
https://www.acmicpc.net/problem/1639
1639번: 행운의 티켓
첫째 줄에 문자열 S가 주어진다. 문자열 S는 1보다 크거나 같고, 9보다 작거나 같은 수로만 이루어져 있고, 길이는 50보다 작거나 같은 자연수이다.
www.acmicpc.net
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. 문제를 푸는데 도움이 되는 지식
- 브루트 포스
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
1246. [Python]온라인 판매 (0) 2023.04.30 2003. [Python]수들의 합 2 (0) 2023.04.18 1337. [Python]올바른 배열 (0) 2023.04.13 1920. [Python]수 찾기 (0) 2023.04.12 1755. [Python]숫자놀이 (0) 2023.04.11