Python Algorithm Practice

3.1. Sequence of characters

N개의 문자열 데이터를 입력받아 앞에서 읽을 때나 뒤에서 읽을 때나 같은 경우(회문 문자열)이면 YES를 출력하고 회문 문자열이 아니면 NO를 출력하는 프로그램을 작성한다. 단 회문을 검사할 때 대소문자를 구분하지 않습니다.

n = int(input())
for i in range(n):
    s = input()
    s = s.lower()
    size = len(s)

    for j in range(size//2):
        if s[j] != s[-1-j]:
            print(f"#{i+1} NO")
            break
    else:
        print(f"#{i+1} YES")

# s[::-1]으로도 구현 가능함.

3.2. Extract only number

문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만듭니다. 만들어진 자연수와 그 자연수의 약수 개수를 출력합니다. 만약 “t0e0a1c2h0er”에서 숫자만 추출하면 0, 0, 1, 2, 0이고 이것을 자연수를 만들면 120이 됩니다. 즉 첫자리 0은 자연수화 할 때 무시합니다. 출력은 120를 출력하고, 다음 줄에 120의 약수의 개수를 출력하면 됩니다. 추출하여 만들어지는 자연수는 100,000,000을 넘지 않습니다.

s = input()
res = 0
for i in s:
    if i.isdigit():
        res = res*10 + int(i)

cnt = 0
for i in range(1,res+1):
    if res%i==0:
        cnt += 1
print(cnt)

3.3. Reverse cards

1부터 20까지 숫자가 하나씩 쓰인 20장의 카드가 아래 그림과 같이 오름차순으로 한 줄로 놓여있다. 각 카드의 위치는 카드 위에 적힌 숫자와 같이 1부터 20까지로 나타낸다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
                                       

카드의 위치를 바꾼다: 구간 [a, b] (단, 1 ≤ a ≤ b ≤ 20)가 주어지면 위치 a부터 위치 b까지의 카드를 현재의 역순으로 놓는다. 예를 들어, 현재 카드가 놓인 순서가 위의 그림과 같고 구간이 [5, 10]으로 주어진다면, 위치 5부터 위치 10까지의 카드 5, 6, 7, 8, 9, 10을 역순으로 하여 10, 9, 8, 7, 6, 5로 놓는다. 이제 전체 카드가 놓인 순서는 아래 그림과 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 10 9 8 7 6 5 11 12 13 14 15 16 17 18 19 20

이 상태에서 구간 [9, 13]이 다시 주어진다면, 위치 9부터 위치 13까지의 카드 6, 5, 11, 12, 13을 역순으로 하여 13, 12, 11, 5, 6으로 놓는다. 이제 전체 카드가 놓인 순서는 아래 그림과 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 10 9 8 7 6 5 11 12 13 14 15 16 17 18 19 20
1 2 3 4 10 9 8 7 13 12 11 5 6 14 15 16 17 18 19 20

오름차순으로 한 줄로 놓여있는 20장의 카드에 대해 10개의 구간이 주어지면, 주어진 구간의 순서대로 위의 규칙에 따라 순서를 뒤집는 작업을 연속해서 처리한 뒤 마지막 카드들의 배치를 구하는 프로그램을 작성하세요.

a = list(range(0,21))
for _ in range(10):
    s, e = map(int, input().split())
    for i in range((e-s+1)//2):
        a[s+i], a[e-i] = a[e-i], a[s+i]
a.pop(0)
print(a)

## 또는 s,e 받고 난 후 역배열 바꿔서 해도 됨 아래 참조
tmp = a[s-1:e]
a[s-1:e] = tmp[::-1]

3.4. Merge lists

오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

# sort로 바로 구할 수도 있지만 포인터 연습으로 구현

n1 = int(input())
l1 = list(map(int, input().split()))
n2 = int(input())
l2 = list(map(int, input().split()))

p1=p2=0
res = []
while p1<n1 and p2<n2:
    if l1[p1] <= l2[p2]:
        res.append(l1[p1])
        p1 += 1
    else:
        res.append(l2[p2])
        p2 += 1
if p1<n1:
    res = res + l1[p1:]
if p2<n2:
    res = res + l2[p2:]

for i in res:
    print(i, end=' ')

3.5. Sum of Numbers

N개의 수로 된 수열 $A[1], A[2], …, A[N]$ 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 $A[i]+A[i+1]+…+A[j-1]+A[j]$가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

n, m = map(int, input().split())
a = list(map(int,input().split()))
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        if m==sum(a[i:j+1]):
            cnt += 1
print(cnt)

## 다른 방법
lt = 0
rt = 1
tot = a[0]
cnt = 0

while True:
    if tot < m:
        if rt < n:
            tot += a[rt]
        else:
            break

    elif tot == m:
        cnt += 1
        tot -= a[lt]
        lt += 1

    else:
        tot -= a[lt]
        lt += 1

3.6. Sum of Matrix

5*5 격자판에 아래와 같이 숫자가 적혀있습니다.

         
10 13 10 12 15
12 39 30 28 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19

N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합니다.

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

max = 0
mrow = 0
mcol = 0
for i in range(n):
    mrow = mcol = 0
    for j in range(n):
        mrow += mat[i][j]
        mcol += mat[j][i]
    
    if mrow > max:
        max = mrow
    if mcol > max:
        max = mcol

rdiag = 0
ldiag = 0
for i in range(n): # diagonal
    rdiag += mat[i][i] # right diagonal
    ldiag += mat[i][n-i-1] # left diagonal
if rdiag > max:
    max = rdiag
if ldiag > max:
    max = ldiag

print(max)

3.7. Diamond

현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어져있다. N의 크기는 항상 홀수이다. 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다. 만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다.

         
10 13 10 12 15
12 39 30 28 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19

현수과 수확하는 사과의 총 개수를 출력하세요.

n = int(input())
mat = [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 += mat[i][j]
    if i < n//2:
        s -= 1
        e += 1
    else:
        s += 1
        e -= 1

print(res)

3.8. Sandglass

현수는 곳감을 만들기 위해 감을 깍아 마당에 말리고 있습니다. 현수의 마당은 N*N 격자판으로 이루어져 있으며, 현수는 각 격자단위로 말리는 감의 수를 정합니다. 그런데 해의 위치에 따라 특정위치의 감은 잘 마르지 않습니다. 그래서 현수는 격자의 행을 기준으로 왼쪽, 또는 오른쪽으로 회전시켜 위치를 변경해 모든 감이 잘 마르게 합니다. 만약 회전명령 정보가 2 0 3이면 2번째 행을 왼쪽으로 3만큼 아래 그림처럼 회전시키는 명령입니다.

         
10 13 10 12 15
12 39 30 28 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19
         
10 13 10 12 15
23 11 12 39 30
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19

첫 번째 수는 행번호, 두 번째 수는 방향인데 0이면 왼쪽, 1이면 오른쪽이고, 세 번째 수는 회전하는 격자의 수입니다. M개의 회전명령을 실행하고 난 후 아래와 같이 마당의 모래시계 모양의 영역에는 감 이 총 몇 개가 있는지 출력하는 프로그램을 작성하세요.

         
10 13 10 12 15
23 11 12 39 30
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19 
n = int(input())
mat = [list(map(int,input().split())) for _ in range(n)]
m = int(input())

for _ in range(m):
    row, tw, k = map(int,input().split())
    if tw == 0: # toward left 
        mat[row-1] = mat[row-1][k:]+mat[row-1][:k]
    else: # toword right
        mat[row-1] = mat[row-1][-k:]+mat[row-1][:-k]
        
s = 0
e = n
res = 0
for i in range(n):
    res += sum(mat[i][s:e])
    # print(mat[i][s:e])
    if i < n//2:
        s += 1
        e -= 1
    else:
        s -= 1
        e += 1
print(res)

3.9. Hill

지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요. 격자의 가장자리는 0으로 초기화 되었다고 가정한다. 만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.

             
0 0 0 0 0 0 0
0 5 3 7 2 3 0
0 3 7 1 6 1 0
0 7 2 5 3 4 0
0 4 3 6 4 1 0
0 8 7 3 5 2 0
0 0 0 0 0 0 0 
n = int(input())
mat = [list(map(int,input().split())) for _ in range(n)]

mat.insert(0, [0]*n) # upper padding
mat.append([0]*n) # lower padding

for i in mat:
    i.insert(0, 0) # left padding
    i.append(0) # right padding

dx = [-1, 0, 1, 0] # direction x
dy = [0, 1, 0, -1] # direction y
cnt = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if all(mat[i][j] > mat[i+dx[k]][j+dy[k]] for k in range(4)):
            cnt += 1
print(cnt)

3.10. Sudoku

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

                 
1 4 3 6 2 8 5 7 9
5 7 2 1 3 9 4 6 8
9 8 6 7 5 4 2 3 1
3 9 1 5 4 2 7 8 6
4 6 8 9 1 7 3 5 2
7 2 5 8 6 3 9 1 4
2 3 7 4 8 1 6 9 5
6 1 9 2 7 5 8 4 3
8 5 4 3 9 6 1 2 7

위 그림은 스도쿠를 정확하게 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 예시로 위에서 굵은 숫자)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다. 완성된 9×9 크기의 수도쿠가 주어지면 정확하게 풀었으면 “YES”, 잘 못 풀었으면 “NO”를 출력하는 프로그램을 작성하세요.

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

def check(mat):
    for i in range(9):
        chk1 = [0]*10 # row check
        chk2 = [0]*10 # col check
        for j in range(9):
            chk1[mat[i][j]] = 1
            chk2[mat[j][i]] = 1
        if sum(chk1) != 9 or sum(chk2) != 9:
            return False

    for i in range(3): # outer
        for j in range(3):
            chk3 = [0]*10 # 3x3 group check
            for i2 in range(3): # inner
                for j2 in range(3):
                    chk3[mat[i*3+i2][j*3+j2]] = 1
            if sum(chk3) != 9:
                return False
    return True
                
if check(mat):
    print("YES")
else:
    print("NO")

3.11. Mirrored String in Matrix

1부터 9까지의 자연수로 채워진 7*7 격자판이 주어지면 격자판 위에서 가로방향 또는 세로방향으로 길이 5자리 회문수가 몇 개 있는지 구하는 프로그램을 작성하세요. 회문수란 121과 같이 앞에서부터 읽으나 뒤에서부터 읽으나 같은 수를 말합니다.

빨간색처럼 구부러진 경우(87178)는 회문수로 간주하지 않습니다.

sys.stdin=open("input.txt", "r")
mat = [list(map(int, input().split())) for _ in range(7)]
cnt=0
for i in range(3):
    for j in range(7):
        tmp = mat[j][i:i+5]
        if tmp == tmp[::-1]:
            cnt+=1
        for k in range(2):
            if mat[i+k][j] != mat[i+5-k-1][j]:
                break
        else:
            cnt+=1
        
print(cnt)