백준 17251번 Python / Dynamic Programming

문제풀이 GitHub

https://github.com/Seokii/baekjoon

GitHub - Seokii/baekjoon: Daily Commit for Baekjoon

 

문제링크

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

17251번: 힘 겨루기

 

풀이 (시간 초과)

n = int(input())
arr = list(map(int, input().split()))
judge = 0

for i in range(1, n):
    red_team = arr[:i]
    blue_team = arr[i:]
    # print(f'red team : {red_team},   blue team: {blue_team}')
    if max(red_team) > max(blue_team):
        judge += 1
    elif max(red_team) < max(blue_team):
        judge -= 1

# print(judge)
if judge > 0:
    print('R')
elif judge < 0:
    print('B')
else: print('X')

처음 적어서 제출한 풀이입니다.

리스트 슬라이싱을 나눌 수 있는 횟수만큼 for문으로 반복해서 조건문을 수행하는 구조입니다.

조건문을 수행해 홍팀이 이기면 judge 변수에 +1을, 청팀이 이긴다면 변수에 -1을 계산합니다.

최종적으로, judge변수의 값이 0보다 크면 'R'을 출력, 0보다 작으면 'B'를 출력 0이라면 'X'를 출력합니다.

이렇게 코드를 작성해서 제출을 했지만 시간 초과가 나왔습니다.

시간을 조금씩 줄여보려고 다른 방식으로도 시도했지만 시간초과가 나왔습니다.

 

풀이 (정답)

n = int(input())
arr = list(map(int, input().split()))

max_value = max(arr)
search = []
cnt = 0

for i in arr:
    if i == max_value:
        search.append(cnt)
    cnt += 1

if len(search) > 1:
    start = search[0]
    end = search[-1]
    B = start
    X = end - start
    R = n - 1 - B - X
else:
    B = search[0]
    R = n-1-B

if B > R: print('B')
elif R > B: print('R')
else: print('X')

위의 시간초과 코드에서 다르게 생각한 방식 중에서는

값을 입력받을 때, 가장 큰 최댓값들의 인덱스를 받아 계산을 해주는 방식이었습니다.

가장 큰 값의 위치만 안다면 나누었을 때 어느 쪽이 이기는지 쉽게 계산할 수 있기 때문입니다.

그런데, while문을 통해 일일이 최댓값을 찾다 보니 계산량이 많아져 그 또한 시간 초과가 발생했습니다.

 

시간 초과를 줄이기 위해서 계속 생각을 했는데,

처음 리스트를 받을 때,

max()함수를 사용해 최댓값을 찾을 때,

for문에 직접 값을 비교하며 카운트를 통해 한 번에 인덱스를 찾을 때,

이렇게 총 3번만 리스트를 순회하고 주어진 인덱스 값만을 통해 바로 계산했습니다.

그 결과, 원래는 41% ~ 44% 정도에서 채점하다 시간 초과가 발생했었는데 정상적으로 정답처리가 되었습니다.

 

인덱스 값만 알면 정답을 바로 찾을 수 있습니다.

예제 입력 1을 예시로 들어 '/'로 나누는 것을 표시했을 때,

9 / 15 18 7 13 11 -> B

9 15 / 18 7 13 11 -> B

9 15 18 / 7 13 11 -> R

9 15 18 7 / 13 11 -> R

9 15 18 7 13 / 11 -> R

가장 큰 값인 18을 기준으로 승패가 나뉘게 됩니다.

따라서, 나누는 횟수(n-1)와 최댓값(18)이 위치한 인덱스 값만 안다면 쉽게 정답을 구할 수 있습니다.

위의 예시는 최댓값이 1개이며 인덱스 값이 2이기 때문에

처음 2번 나눌 때까지는 오른쪽(청팀)이 승리합니다. = 인덱스 값

그리고 나머지는 왼쪽(홍팀)이 승리합니다. = n-1(나누는 횟수) -인덱스 값(청팀 승리 횟수)

 

하지만, 최댓값이 여러 개가 존재한다면 다음과 같이 계산합니다.

최댓값이 등장하는 첫 번째 인덱스 값(start)과 마지막 인덱스 값(end)을 구합니다.

청팀이 이기는 횟수 = 인덱스 값(1개일 때와 같은 원리)

비기는 횟수 = end - satrt (최댓값이 여러 개라면 서로 나누어가지는 경우)

홍팀이 이기는 횟수 = n-1(나누는 횟수) -B(청팀이 이기는 횟수) -X(비기는 횟수)

 

마지막에는 각 횟수를 비교해 출력하면 바로 정답을 구할 수 있습니다.