[Section03] Python 알고리즘 문제풀이 05~08

Q5. 수들의 합 : N개의 수로 된 수열의 i번째 수부터 j번째 수까지의 합이 M이 되는 경우의 수

입력 :

N(1≤N≤10,000) M(1≤M≤300,000,000)

N개의 수열

출력 : 경우의 수

 

[내가 쓴 코드]

n, m = map(int, input().split())
a = list(map(int, input().split()));
count = 0

for i in range(n) :
    sum = a[i]
    if sum == m :
        count += 1
    elif sum < m :
        for j in range(i + 1, n) :
            sum += a[j]
            if sum == m :
                count += 1
            elif sum > m :
                break
    else :
        break
            
print(count)

 

[풀이 코드]

n, m = map(int, input().split()))

a = list(map(int, input().split()))

lt = 0
rt = 0
tot = a[0]
cnt = 0

while True :
    if tot < m :
    	if rt < n :
            tot += a[rt]
            rt += 1
        else :
            break
    elif tot == m :
    	cnt += 1
        tot -= a[lt]
        lt += 1
    else :
    	tot -= a[lt]
        lt += 1
print(cnt)

 

채점 시 마지막 5번에서 Time Limit Exceeded 발생,,, 뭔가 i~j의 합을 계산하고 다음 반복으로 넘어갈 때 합산했던 값을 저장해두고 재사용할 수 있는 방법을 찾아야할 것 같다고 생각했는데 풀이에서 해당 방식으로 풀었음

-> rt, lt라는 기준점을 사용하여 계산함

 

---

Q6. 격자판 최대합 : N*N의 격자판에서 각 행과 열, 두 대각선의 합이 가장 큰 수 출력

입력 :

N(1<=N<=50)

N * N 격자판

출력 : 최대합

 

[내가 쓴 코드]

n = int(input())
a = list()
b = list()

r1 = 0
r2 = 0

for i in range(n) :
    b = list(map(int, input().split()))
    a.append(b)
    
for i in range(n) :
    row = 0
    col = 0
    r1 += a[i][i]
    r2 += a[i][n-i - 1]
    for j in range(n) :
        row += a[i][j]
        col += a[j][i]
    b.append(row)
    b.append(col)
b.append(r1)
b.append(r2)

result = b[0]
for x in b :
    if x > result :
        result = x
        
print(result)

 

[풀이 코드]

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

largest = -2147000000

for i in range(n) :
    sum1 = sum2 = 0
    for j in range(n) :
    	sum1 += a[i][j]
        sum2 += a[j][i]
    if sum1 > largest :
    	largest = sum1
    if sum2 > largest :
    	largest = sum2
sum1 = sum2 = 0

for i in range(n) :
    sum1 += [i][i]
    sum2 += [i][n-i-1]
if sum1 > largest :
    largest = sum1
if sum2 > largest :
    largest = sum2
    
print(largest)

한줄로 배열을 받을 수 있다니... 또 for문 하나로 대각선과 행과 열의 합을 계산하고 싶었는데 그렇게 하지 않아도 되나봐,,, index로 배열 접근에 연습하는 문제였다고 생각!

 

---

Q7. 사과나무(다이아몬드) : N*N의 격자판에서 다이아몬드 형태에 포함되는 수의 합계 출력

입력 :

N(3<=N<=20) 단, N은 홀수

N * N 격자판

출력 : 다이아몬드 형태의 합계

 

[내가 쓴 코드]

n = int(input())
a = list()
result = 0

pivot = n // 2
step = pivot

for i in range(n) :
    a.append(list(map(int, input().split())))
    
for i in range(n) :
    if(i < n // 2) :
        for j in range(pivot, step + 1) :
            result += a[i][j]
        pivot -= 1
        step += 1
    else :
        for j in range(pivot, step + 1) :
            result += a[i][j]
        pivot += 1
        step -= 1
print(result)

 

[풀이 코드]

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
res = 0
s e = n//2

for i in range(n) :
    for j in range(s, e+1) :
        res += a[i][j]
    if i < n//2 :
        s -= 1
        e += 1
    else :
        s += 1
        e -= 1
print(res)

풀면서 너무 완벽하다. 라고 생각했는데,,, 접근은 잘 한 거 같은데 좀 더 고민해서 정리했으면 좋았을 거 같음

 

---

Q8. 곳감(모래시계) : N*N의 격자판을 M개의 회전명령에 따라 변경하고 모래시계 형태에 포함되는 수의 합계 출력

*회전명령 : 회전명령 정보가 2 0 3이면 2번째 행을 왼쪽으로 3만큼 아래 그림처럼 회전시킴

입력 :

N(3<=N<=20) 단, N은 홀수

N * N 격자판

M(1<=M<=10)

M개의 회전명령

출력 : 합계

 

[내가 쓴 코드]

n = int(input())
a = list()
for i in range(n) :
    a.append(list(map(int, input().split())))
    
m = int(input())
b = list()
result = 0

for i in range(m) :    #회전명령에 따락서 이동
    row, rl, step = (map(int, input().split()))
    row -= 1
    if step >= n :    #step이 n보다 클 경우 아래 식 적용
        step = step % n
    if rl == 0 :    #방향에 따라 회전
        keep1 = a[row][step:]
        keep2 = a[row][:step]
        a[row][:n-step] = keep1
        a[row][n-step:] = keep2
    else :
        keep1 = a[row][n-step:]
        keep2 = a[row][:n-step]
        a[row][:step] = keep1
        a[row][step:] = keep2

for i in range(n) :    #모래시계 모양으로 합산
    if(i < n//2) :
        for j in range(i, n - i) :
            result += a[i][j]  
    else :
        for j in range(n-i-1, i + 1) :
            result += a[i][j]

print(result)

 

[풀이 코드]

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
m = int(input())
for i in range(m) :
    h, t, k = map(int, input().split())
    if t == 0 :
        for _ in range(k) :
            a[h-1].append(a[h-1].pop(0))
    else :
        for _ in range(k) :
            a[h-1].insert(0, a[h-1].pop())
res = 0            
s = 0
e = n - 1

for i in range(n) :
    for j in range(s, e+1) :
        res += a[i][j]
    if i < n//2 :
        s += 1
        e -= 1
    else :
        s -= 1
        e += 1
        
print(res)

슬라이싱 활용하여 회전을 하였는데 풀이에서는 pop을 사용

 

 

*강의 : 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)