섹션 3. 탐색 & 시뮬레이션

1. 회문 문자열 검사

# 회문 문자열

# 1. for 문을 도는데, 리스트길이의 절반인덱스만 돌면서 비교하면됨

import sys

#sys.stdin = open("in1.txt", "rt")

n = int(input())



count = n // 2

for i in range(n):
    word = list(input())
    size = len(word)
    count = size // 2
    flag = True
    for wordIndex in range(count):
        if word[wordIndex].upper() != word[size-1-wordIndex].upper() :
            flag = False
            break
    print('#%d'%(i+1), end=' ')
    if flag == False:
        print('NO')
    else:
        print('YES')
        

2. 숫자만 추출

# 숫자만 추출
# ascii 48~57
import sys

sys.stdin = open("in5.txt","rt")


str = input()

result = 0
for s in str:
    if s.isdecimal():
        result = result*10 + int(s)



count=0
for i in range(1, result+1):
    if result % i == 0:
        count+=1
        
print(result)
print(count)

 

3. 카드 역배치

import sys

# 내 풀이
#sys.stdin = open("in1.txt", "rt")

# 오리지널 카드배열 만들기
arr = []
for i in range(1, 21):
    arr.append(i)
    

# 인풋 받기
for i in range(0, 10):
    a,b = map(int, input().split())
    # 범위를 돌면서 순서 바꾸기
    for idx in range(round((b-a+1) / 2)):
        temp = arr[a-1+idx] 
        arr[a-1+idx] = arr[b-1-idx]
        arr[b-1-idx] = temp       

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

 

import sys


# 답
# 스와프 사용하기 a, b = b, a
arr = list(range(1,21))

for _ in range(10): # _는 변수대입없이.아무변수없이 반복.
    s, e = map(int, input().split())
    for i in range((e-s+1)//2): # //는 몫
        arr[s+i-1], arr[e-i-1] = arr[e-i-1], arr[s+i-1]

for x in arr:
    print(x, end= ' ')


    

4. 두 리스트 합치기 

import sys

#sys.stdin = open("in1.txt", "rt")

# 내 풀이
arr = []
for _ in range(2):
    input()
    arr += (list(map(int, input().split())))

arr.sort()

for i in arr:
    print(i, end=' ')
    
내 풀이1 문제점: 8log8 퀵정렬

 

import sys

#sys.stdin = open("in1.txt", "rt")

# 내 풀이2
n = int(input())
nArr = list(map(int, input().split()))
m = int(input())
mArr = list(map(int, input().split()))

resultArr = []
p1, p2 = 0, 0
while True:
    if nArr[p1] <= mArr[p2]:
        resultArr.append(nArr[p1])
        p1+=1
    else:
        resultArr.append(mArr[p2])
        p2+=1
        
    if p1 == n:
        resultArr += mArr[p2:m]
        break
    elif p2 == m:
        resultArr += nArr[p1:n]
        break
for i in resultArr:
    print(i, end=' ')

 

import sys

#sys.stdin = open("in1.txt", "rt")

# 답
n = int(input())
nArr = list(map(int, input().split()))
m = int(input())
mArr = list(map(int, input().split()))

resultArr = []
p1=p2=0
while p1<n and p2<m:
    if nArr[p1] <= mArr[p2]:
        resultArr.append(nArr[p1])
        p1+=1
    else:
        resultArr.append(mArr[p2])
        p2+=1
        
if p1 < n:
    resultArr += nArr[p1:]
            
if p2 < m:
    resultArr += mArr[p2:]
    
for i in resultArr:
    print(i, end=' ')

5. 수들의 합

import sys

#sys.stdin = open("in1.txt", "rt")

# 내 풀이
n, m = map(int, input().split())
arr = list(map(int, input().split()))

answer = 0
for i in range(n):
    sum = 0
    while sum <= m and i < n:
        sum = sum + arr[i]
        i+=1
        if sum == m:
            answer+=1

print(answer)

내 풀이 문제점: 시간초과

 

import sys

#sys.stdin = open("in1.txt", "rt")

# 답
n, m = map(int, input().split())
a = list(map(int, input().split()))
lt = 0
rt = 1
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)
        
            

6. 격자판 최대합

import sys

#sys.stdin = open("in1.txt", "rt")


'''
내 풀이
1. 각 행의 합
2. 각 열의 합
3. 두 대각선의 합
'''
n = int(input())

arr = []
for i in range(n):   
    arr.append(list(map(int, input().split())))

resultArr = []

sumZ = sumQ = 0
for i in range(n):
    sumX = sumY = 0
    for j in range(n):
        sumX += arr[i][j]
        sumY += arr[j][i]

    resultArr.append(sumX)
    resultArr.append(sumY) 

    sumZ += arr[i][i]
    sumQ += arr[i][n-i-1]
    
resultArr.append(sumZ)
resultArr.append(sumQ)
resultArr.sort(reverse=True)
print(resultArr[0])

 

import sys

#sys.stdin = open("in1.txt", "rt")


'''
답
1. 각 행의 합
2. 각 열의 합
3. 두 대각선의 합
'''
n = int(input())

arr = [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 += arr[i][j]
        sum2 += arr[j][i]
    if sum1 > largest:
        largest = sum1
    if sum2 > largest:
        largest = sum2

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

7. 사과나무

import sys

#sys.stdin = open("in1.txt", "rt")


'''
내 풀이
1. 규칙을 찾자
2. 첫 줄은 N의 중앙값으로 시작
3. 점점 중앙값-1, 중앙값, 중앙값+1의 범위로 넓어짐
4. 넓어지다가 중앙값에 오면 그 다음부터는 줄어듬

'''
N = int(input())

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



sPoint = N // 2
ePoint = sPoint +1

result = 0
for i in range(N):
    arr = farmArr[i]
    result += sum(arr[sPoint:ePoint])
    
    if i < N // 2:
        sPoint -= 1
        ePoint += 1       
    else:
        sPoint += 1
        ePoint -= 1

    
        
print(result)        

 

import sys

#sys.stdin = open("in1.txt", "rt")


'''
답

'''
N = int(input())

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



sPoint = ePoint = N // 2

result = 0
for i in range(N):
    for j in range(sPoint, ePoint+1):
        result += farmArr[i][j]
    if i < N // 2:
        sPoint -= 1
        ePoint += 1       
    else:
        sPoint += 1
        ePoint -= 1
    
        
print(result)