이 문제는 주어진 엄청나게 긴 숫자열(1000개 숫자)에서 연속으로 13개의 숫자의 곱 중 가장큰 숫자를 찾는 문제입니다. 일직선으로 생각하면 되고, 대각선이나 세로가 아닌 horizental로 생각하고 해결하면 됩니다.
가장 처음으로 생각할 부분은 이 문제를 가장 원초적으로 어떻게 풀 것인지를 생각하고, 차차 난이도가 있는 제약이 들어올 것을 고려하여 최적화하는 단계로 진화를 시키면 되겠습니다. 우선 원초적으로 어떻게 풀면 될까요?? 뭐... 그냥...
첫번째 ~ 13번째 수까지의 곱을 구하고
두번째 ~ 14번째 수까지의 곱을 구하고
...................
...................
천번째-12번째 ~ 천번째 수까지의 곱을 구해서 가장큰 수를 뽑으면 되겠습니다.
1. 원초적으로 풀기
# Problem 8 (min)
if __name__ == '__main__':
tc = int(input())
for t in range(tc):
n, k = input().strip().split(' ')
n, k = int(n), int(k)
target = input().strip()
maxMul = 1
for i in range(len(target)):
if i+k > len(target): break
temp = 1
for j in range(k):
temp *= int(target[i+j])
if temp > maxMul: temp, maxMul = maxMul, temp
print(maxMul)우선 Python은 input()으로 받는 데이터를 무조건 문자열로 처리하기때문에, target은 따로 int( )변환하지 않고 사용합니다. 그래야 원하는 자리수를 배열처럼 바로 찾아서 사용이 가능하기 때문입니다. 그리고 실제로 계산할때만 int( )로 변환해서 사용하면 되지요.
크으... 너무나 단순하게 풀어서 해결했습니다.
2. 최적화해서 풀기
얼마나 가혹한 상황을 생각해야 할지는 모르겠지만, 우선 Test Case는 100개 / 구하고자 하는 Size는 최대 13개 / 들어오는 숫자의 집합은 최대 1000개 로 생각해 보겠습니다. 한개를 구할때는 당연히 1초내에 나오지만 이게 100번을 하게되면 왠지 1초를 넘어갈 것 같습니다.
그럼 어떻게 최적화가 가능할까요?? 여러가지 방법이 존재하겠지만, 저는 아래의 방식으로 최적화 했습니다.
- 0이 구하고자 하는 Size에 있다면, 이는 계산할 필요가 없습니다. 왜냐하면 0을 곱하면 결국 0이기 때문이죠. 그렇게 되면 그 구간은 아예 건너띄고 계산하면 됩니다.
- Size만큼 항상 순차적으로 곱하지 않고, 그 다음 순서에서는 바로전에 곱해진 결과에 새로운 수를 곱하고... 한개 Shift 됨에 따라 없어지는 숫자를 나누면... Size만큼의 loop없이 바로 연산이 가능해집니다.
이 정도만 되도, 많은 최적화가 된 것 같습니다.
# Problem 8 (max)
def calcMaxStatus(target, status, k):
mulRes = 1
if status+k > len(target): return 0, len(target)
for i in range(status, status+k):
if target[i] == '0':
mulRes = 0
return mulRes, i-1
mulRes *= int(target[i])
return mulRes, status+k-1
if __name__ == '__main__':
tc = int(input())
for t in range(tc):
n, k = input().strip().split(' ')
n, k = int(n), int(k)
target = input().strip()
maxMul = 0
prevMul = 0
status = 0
while status < len(target):
if target[status] == '0': mulRes, status = calcMaxStatus(target, status+1, k)
elif status == 0: mulRes, status = calcMaxStatus(target, status, k)
elif target[status] != '0':
mulRes = prevMul * int(target[status]) / int(target[status-k])
status += 1
prevMul = mulRes
if mulRes > maxMul: mulRes, maxMul = maxMul, mulRes
print(int(maxMul))이제 좀 길어졌네요... 위의 2가지를 반영한 코드입니다. 코드를 보면 로직이 이해가 갈 것으로 생각하고 설명은 생략하기로 하겠습니다. 다른사람이 코딩한 것을 분석해 보는것도 관점을 넓힐수 있는 한가지 방법이라고 생각하기 때문입니다. 그럼 한번 보시고 질문은 언제든지 주시면 답변드리겠습니다.
-Ayotera Lab-
댓글