[3]알까기 스터디 -섹션3_1주차(일요일)

알까기 스터디 - 파이썬 알고리즘 문제풀이 _섹션 3

문제 1 - 회문 문자열 검사

n = int(input())

for i in range(n) :
    Origin = input()
    Origin = Origin.lower() # 대소문자 구분을 없애기위해 모두 소문자로 
    Test = Origin[::-1]
    isTrue = True
    for j in range(len(Origin)//2) :
        if Origin[j] != Test[j] :
           isTrue = False

    print("#%d %s" %(i+1 ,'YES' if isTrue==True else 'NO'))  # 파이썬 출력방법 

• 혼자 푼 풀이
• 섹션 2에서 출력방법을 알게되어 수월하게 풀었다.

강사님 풀이 2

n = int(input())

for i in range(n) :
    Origin = input()
    Origin = Origin.lower()
    Test = Origin[::-1]
    if Test == Origin :
        print('#%d %s' %(i+1, 'YES'))
    else :
        print('#%d %s' %(i+1, 'NO'))

아.. 이렇게 간단하게 풀수도있구나

그런데 이렇게 파이써닉한 방법도 좋지만 면접에서 직접해보라고 하는 경우도 있다고 한다.

강사님 풀이 1

n = int(input())

for i in range(n) :
    Origin = input()
    Origin = Origin.lower()
    for j in range(len(Origin)//2) :
        if Origin[j] != Origin[-1-j] :
            print('#%d %s' %(i+1, 'NO'))
            break
    else : # break에 걸리지않았다면 
        print('#%d %s' %(i+1, 'YES'))

문제 2 - 숫자만 추출

import re
s = input()
s = re.sub(r'[^0-9]','',s)# 숫자를 제외한 문자들을 제거 

def divisorcnt(value) : # 약수 구하기 
    ans = 0
    for i in range(1,(int(value)+1)) :
        if (value % i)==0 :
            ans+= 1 
    print(ans)
print(int(s))
divisorcnt(int(s))

• 내가 푼 풀이

문제 3 - 카드 역배치

• 강사님 풀이

  a = list(range(21)) # 0부터 20까지 
  

for _ in range(10) :
s,e = map(int,input().split())
for i in range(((e-s)+1)//2) : # swap 개수
a[s+i], a[e-i] = a[e-i],a[s+i]
a.pop(0) # 0번 인덱스의 값을 제거

for val in a :
print(val, end = ' ')

 <br>

 - 풀이를 들은 후 몇일 후 혼자푼 풀이 

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

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

> 나는 출력할 때 1번부터 출력했는데 pop을 이용해 인덱스값을 지정하여 원소를 제거하는 방법도 있음을 배웠다. 



<br><br>
  ### 문제 4 - 두 리스트 합치기 

  ```py
  n = int(input())
flist = list(map(int,input().split()))
m = int(input())
Seclist = list(map(int,input().split()))

ans = []
p1,p2 = 0,0 

while p1 < n and p2 < m :
    if flist[p1] <= Seclist[p2] :
        ans.append(flist[p1])
        p1 +=1
    else :
        ans.append(Seclist[p2])
        p2 +=1

if p1 < n : # append로 붙이면 리스트형태로 붙기 때문에! '+' 기호를 이용해서 붙인다. 
    ans = ans + flist[p1:]
if p2 <m :
    ans = ans + Seclist[p2:]

for val in ans:
    print(val, end=' ')

• O(n) 만에 풀 수 있다.
• 합쳐서 sort하면 nlogn 이다.

### 문제 5 - 수들의 합

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

lt = 0
rt = 1
tot =nums[0]
cnt = 0
while True :
    if tot < m :
        if rt < n:
            tot+= nums[rt]
            rt+=1
        else : # rt == n일때 
            break
    elif tot == m :
        cnt+=1
        tot -= nums[lt]
        lt +=1 
    else :
        tot -= nums[lt]
        lt+=1 
print(cnt)

문제 6 - 격자판 최대합

import sys
sys.stdin = open("input.txt","r")

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+= a[i][i]
    sum2 += a[i][n-i-1]

if sum1 > largest :
    largest = sum1
if sum2 > largest :
    largest = sum2
print(largest)

문제 7 - 사과나무 (다이아몬드)

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)

문제 8 - 곳감 (모래시계)

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)) # 맨 앞의 값을 pop하여 뒤에 삽입 
    else :
        for _ in range(k) :
            a[h-1].insert(0,a[h-1].pop()) # 맨 뒤의 값을 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)

문제 9 - 봉우리

dx = [-1,0,1,0]
dy = [0,1,0,-1]

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)
cnt = 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)) :
            cnt+=1
print(cnt)

문제 10 - 스도쿠 검사

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

a=[list(map(int, input().split())) for _ in range(9)]
if check(a):
    print("YES")
else:
    print("NO")

문제 11 - 격자판 회문수

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

cnt = 0
for i in range(3) :
    for j in range(7) :
        tmp = board[j][i:i+5]
        if tmp == tmp[::-1] :
            cnt += 1
        for k in range(2) :
            if board[i+k][j] != board[i+5-k-1][j] :
                break
        else :
            cnt+=1
print(cnt)