2) 탐색&시뮬레이션

1. 회문 문자열 검사

해답 #1: 문자열을 하나씩 s에 입력받아 s의 len 절반만큼 for문을 돌아 앞과 뒤의 문자를 비교해준다.

n = int(input())
res = []
for i in range(n):
    s = input() #문자열 하나씩 입력받아 처리
    s = s.upper() #전부 대문자화
    size = len(s)
    for j in range(size//2):
        if s[j]!=s[-1-j]:
            res.append("#%d NO" %(i+1))
            break
    else:
        res.append("#%d YES" %(i+1))

for x in res:
    print(x)

해답 #2: 이게 간지다..

n = int(input())
res = []
for i in range(n):
    s = input() #문자열 하나씩 입력받아 처리
    s = s.upper() #전부 대문자화
    if s==s[::-1]:
        res.append("#%d YES" %(i+1))
    else:
        res.append("#%d NO" %(i+1))
    
for x in res:
    print(x)

2. 숫자만 추출

• isdigit() / isdecimal(): isdigit()이 더 넓은 범위를 숫자로 인정

내 풀이:

s = input() #섞인 문자열
num=''
for i in range(len(s)):
    if s[i].isdigit():
        num+=s[i]
num = int(num)
res = 0
for i in range(1,num+1): #약수: 1~num
    if num%i==0:
        res+=1

print(num)
print(res)

해답:

s = input()
res=0
for x in s:
    if x.isdecimal():
        res = res*10+int(x)
print(res)

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

3. 카드 역배치

내 풀이: 파이썬 문자열의 귀재?

def reverse(a,b,arr):
    tmp = arr[a-1:b]
    tmp = tmp[::-1]
    
    return tmp


arr = [i for i in range(1,21)]
for _ in range(10):
    a,b = map(int,input().split())
    ret = reverse(a,b,arr)
    arr[a-1:b] = ret

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

해답:

a = list(range(21)) #0~20
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) #0번 index 없애기
for x in a:
    print(x,end=' ')

4. 두 리스트 합치기

해답: 이미 정렬된 두 리스트를 합쳐서 새로 정렬을 할 경우에는 합친 리스트의 길이 n번만에 정렬이 가능하다!

포인터 p1, p2를 둬서 하나씩 크기를 비교하여 합쳐보자.

N = int(input())
arr1 = list(map(int,input().split()))
M = int(input())
arr2 = list(map(int,input().split()))

p1=p2=0
res=[]
while p1<N and p2<M:
    if arr1[p1]<arr2[p2]:
        res.append(arr1[p1])
        p1+=1
    elif arr1[p1]==arr2[p2]:
        res.append(arr1[p1])
        res.append(arr2[p2])
        p1+=1
        p2+=1
    else:
        res.append(arr2[p2])
        p2+=1
        
while p1<N:
    res.append(arr1[p1])
    p1+=1
while p2<M:
    res.append(arr2[p2])
    p2+=1
for x in res:
    print(x,end=' ')

# 깔쌈한 풀이!
n = int(input())
a = list(map(int,input().split()))
m = int(input())
b = list(map(int,input().split()))

p1=p2=0
c=[]
while p1<n and p2<m:
    if a[p1]<=b[p2]:
        c.append(a[p1])
        p1+=1
    else:
        c.append(b[p2])
        p2+=1

if p1<n:
    c=c+a[p1:] #p1~끝까지 붙여주기
if p2<m:
    c=c+b[p2:]
for x in c:
    print(x,end=' ')

5. 수의 합

해답: lt~rt까지의 부분합 tot를 구하자! (투 포인터 어렵당..)

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

lt=0
rt=1
tot=a[0] #첫번째값 저장
res=0

while True: 
    if tot<m: #오른쪽값 더하기
        if rt<n:
            tot+=a[rt]
            rt+=1
        else:
            break #무조건 걸림
    elif tot==m: #왼쪽값 빼주기
        res+=1
        tot-=a[lt]
        lt+=1
    else: #왼쪽값 빼주기
        tot-=a[lt]
        lt+=1        
 
print(res)

6. 격자판 최대합

해답: 행,열의 합을 구할 때 어차피 그 중 가장 큰 합을 출력하는 것이므로 각 합들을 배열에 저장하는 것이 아니라 계속해서 값을 비교하여 largest에 갱신

n = int(input())
a=[] #2차원배열 n*n
for _ in range(n):
    a.append(list(map(int,input().split())))
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+=a[i][i]
    sum2+=a[i][n-i-1]
if sum1>largest:
    largest=sum1
if sum2>largest:
    largest=sum2
    
print(largest)

7. 사과나무

해답: 연속된 구간의 합을 구할 때 포인터 s,e를 움직여서 더해주는 걸 잊지말자!

n = int(input())
for _ in range(n):
    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)

8. 곳감(모래시계)

pop함수의 유용함,,

• append(): array.append(x) 형태로 쓰이고, x를 array 뒤에 덧붙인다.
• extend(): array.extend(iterable) 형태로 쓰이고, append와 다른 점은 괄호안에 iterable 자료형만 받는다.
• insert(): array.insert(i,x): array의 i 위치 앞에 x를 삽입한다.

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

for _ in range(m):
    x,y,z = map(int,input().split())
    
    if y==0: #왼
        for _ in range(z):
            a[x-1].append(a[x-1].pop(0))
    else: #오
        for _ in range(z):
            a[x-1].insert(0,a[x-1].pop())

s=0
e=n-1
res=0
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)

9. 봉우리

append()와 insert()를 적절하게 써서 가장자리를 전부 0으로 만든다.

n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
a.insert(0,[0]*n)
a.append([0]*n)
for x in a:
    x.insert(0,0)
    x.append(0)

dx=[-1,0,1,0]
dy=[0,1,0,-1]
res=0
for i in range(1,n+1):
    for j in range(1,n+1):
        tmp=0
        for k in range(4):
            if a[i][j]>a[i+dx[k]][j+dy[k]]:
                continue
            else:
                tmp=1
        if tmp==0:
            res+=1

print(res)

• all(): all(iterable) 함수는 iterable의 모든 요소가 참이면 True를 반환하는 함수이다.
• any(): any(iterable) 함수는 iterable 중 단 하나라도 참이 있으면 True를 반환하는 함수이다.

n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
a.insert(0,[0]*n)
a.append([0]*n)
for x in a:
    x.insert(0,0)
    x.append(0)

dx=[-1,0,1,0]
dy=[0,1,0,-1]
res=0
for i in range(1,n+1):
    for j in range(1,n+1):
        if all(a[i][j]>a[i+dx[k]][j+dy[k]] for k in range(4)):
            res+=1
            
print(res)

10. 스토쿠 검사

'중복여부' 조건을 어떻게 처리할까? → 나온 숫자를 체크하는 ch배열([0]*10짜리 1차원배열)을 만든다.

세번째 조건 '3*3 보드에 중복없이 나타내기' 처리가 어려움

#완성된 9*9스도쿠
a = [list(map(int,input().split())) for _ in range(9)]

ch1 = [0]*10 #행
ch2 = [0]*10 #열
ch3 = [0]*10 #3*3
res = True
for i in range(9):
    for j in range(9):
        ch1[a[i][j]]=1
        ch2[a[j][i]]=1
    if sum(ch1)!=9 or sum(ch2)!=9:
        res = False
    
for i in range(3):
    for j in range(3):
        for k in range(3):
            for s in range(3):
                ch3[a[i*3+k][j*3+s]]=1
        if sum(ch3)!=9:
            res = False

if res==True:
    print("YES")
else:
    print("NO")

11. 격자판 회문수

문자열 처리[::-1]는 '행'에서만 사용가능하기 때문에 유의해야 한다!

해답 #1:

a = [list(map(int,input().split())) for _ in range(7)]
res=0
#행
for i in range(7):
    for j in range(3):
        tmp=a[i][j:j+5]
        if tmp==tmp[::-1]:
            res+=1
#열
for i in range(7):
    for j in range(3):
        tmp=[]
        for k in range(5):
            tmp.append(a[j+k][i])
        if tmp==tmp[::-1]:
            res+=1
        
print(res)

해답 #2:

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

for i in range(7):
    for j in range(3):
        tmp=a[i][j:j+5]
        if tmp==tmp[::-1]:
            res+=1
        for k in range(2): #5//2
            if a[j+k][i]!=a[j+5-k-1][i]:
                break
        else:
            res+=1
        
print(res)