[BOJ, 백준] 25502 등차수열? 등비수열? Python

 

문제는 다음과 같습니다.

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

 

즉, 어떤 명령어마다 인덱스에 해당되는 수를 바꿔주면서 바뀐 수열이 등차수열인지, 등비수열인지 확인하는 프로그램을 짜는 것이 목표가 되겠습니다.

 

만약 어떠한 수열이

1. 등차수열 -> 공차가 전부 동일하다는 것

2. 등비수열 -> 공비가 전부 동일하다는 것

이 부분에 포커싱을 하게 된다면 해당하는 수열이 어떠한 수열인지 확인하기 굉장히 간편해지겠습니다.

 

import math
import sys
from collections import defaultdict
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
difference = defaultdict(int)
divide = defaultdict(int)

for i in range(0, len(A) - 1):
    t = A[i + 1] - A[i]
    difference[t] += 1
    s = math.gcd(A[i + 1], A[i])
    s1, s2 = A[i + 1] // s, A[i] // s
    divide[(s1, s2)] += 1

for i in range(0, M):
    idx, x = map(int, input().split())
    idx -= 1
    if idx == 0:
        difference[A[1] - A[0]] -= 1
        s = math.gcd(A[1], A[0])
        s1, s2 = A[1] // s, A[0] // s
        divide[(s1, s2)] -= 1

        A[0] = x
        difference[A[1] - A[0]] += 1
        s = math.gcd(A[1], A[0])
        s1, s2 = A[1] // s, A[0] // s
        divide[(s1, s2)] += 1

    elif idx == N - 1:
        difference[A[-1] - A[-2]] -= 1
        s = math.gcd(A[-1], A[-2])
        s1, s2 = A[-1] // s, A[-2] // s
        divide[(s1, s2)] -= 1

        A[-1] = x
        difference[A[-1] - A[-2]] += 1
        s = math.gcd(A[-1], A[-2])
        s1, s2 = A[-1] // s, A[-2] // s
        divide[(s1, s2)] += 1
    else:
        difference[A[idx] - A[idx - 1]] -= 1
        difference[A[idx + 1] - A[idx]] -= 1
        s = math.gcd(A[idx], A[idx - 1])
        s1, s2 = A[idx] // s, A[idx - 1] // s
        divide[(s1, s2)] -= 1
        s = math.gcd(A[idx + 1], A[idx])
        s1, s2 = A[idx + 1] // s, A[idx] // s
        divide[(s1, s2)] -= 1

        #이전값을 바탕으로 만들어진 것들 삭제 후 업데이트
        A[idx] = x
        difference[A[idx] - A[idx - 1]] += 1
        difference[A[idx + 1] - A[idx]] += 1
        s = math.gcd(A[idx], A[idx - 1])
        s1, s2 = A[idx] // s, A[idx - 1] // s
        divide[(s1, s2)] += 1
        s = math.gcd(A[idx + 1], A[idx])
        s1, s2 = A[idx + 1] // s, A[idx] // s
        divide[(s1, s2)] += 1

    #아마 이 과정에서 시간 초과가 나오는 상황

    xx = A[1] - A[0]
    ss = math.gcd(A[1], A[0])
    yy = (A[1] // ss, A[0] // ss)
    t = A[1] / A[0]
    if difference[xx] == N - 1 and xx > 0 and int(xx) == xx:
        print("+")
    elif divide[yy] == N - 1 and yy[0] > 0 and yy[1] > 0 and t == int(t):
        print("*")
    else:
        print("?")

 

 

첫번째 반복문에서 기존 주어진 수열에서 인접항간의 차와 공비를 나타낼 수 있는 tuple을 저장해주고

다음 반복문에서는 주어진 idx에 해당하는 작업을 수행해줍니다.

(이때 주어지는 idx가 가장 처음인지, 마지막인지, 그렇지 아닌지 케이스를 나눠줘야합니다. 바꿔줘야하는 갯수가 다르기 때문입니다.)

 

마지막 #이후에서는 제가 이전에 실패했던 부분인데 다음과 같은 방식으로 체크를 했더니 문제가 풀리게 되었습니다.