[Section03] Python 알고리즘 문제풀이 09~11

Q9. 봉우리 : N*N 격자판에서 자신의 숫자가 상하좌우의 수보다 큰 봉우리의 개수 찾기

입력 :

N(1<=N<=50)

N*N 격자판

출력 : 봉우리 개수

 

[내가 쓴 코드]

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

a.insert(0, [0]*n)  #첫 행 0으로 초기화
a.append([0]*n)  #마지막 행 0으로 초기화

for x in a :  #첫 열과 마지막 열 0으로 초기화
	x.insert(0, 0)
    x.append(0)
#여까지 강의보고 초기화 함!

for i in range(1, n + 1) :
    for j in range(1, n + 1) :
        if a[i][j] <= a[i][j+1] :
            continue
        elif a[i][j] <= a[i+1][j] :
            continue
        elif a[i][j] <= a[i][j-1] :
            continue
        elif a[i][j] <= a[i-1][j] :
            continue
        else :
            count += 1
print(count)
#무작정 상하좌우 탐색함

 

[풀이 코드]

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    
dx = [-1, 0, 1, 0]    #해당 탐색 리스트를 사용할 것임
dy = [0, 1, 0, -1]

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)

dx, dy 활용하여 all로 한번에 탐색....... 파이썬 짱이네요

 

 

---

Q10. 스토쿠 검사 : 9*9 크기의 보드에서 스토쿠를 정확하게 풀었는지 체크

입력 : 완성된 9*9 스토쿠

출력 : YES | NO

 

[내가 쓴 코드]

a = [list(map(int, input().split())) for _ in range(9)]  #스토쿠 입력받기

#index가 9개 생성될 수 있도록 아래 3가지 배열을 0으로 초기화
number_row = [0 for _ in range(9)]  #행
number_col = [0 for _ in range(9)]  #열
number = [0 for _ in range(9)]  #3*3
check = False  #한번이라도 중복되면 break 걸기 위한 플래그

for i in range(9) :
    for j in range(9) :
        number_row[a[i][j] - 1] += 1  #index를 활용하여 해당 수가 있으면 + 1
        number_col[a[j][i] - 1] += 1
        
        #3*3 사각형을 추출하여 검사하는 부분,,,,
        if (i == 0 or i == 3 or i == 6) and (j == 0 or j == 3 or j == 6) :
            for k in range(i, i + 3) :
                for m in range(j, j + 3) :
                   number[a[k][m] - 1] += 1
            if max(number) != 1 :  #1이 아니라는 것은 중복된 수가 발생했다는 뜻
                print("NO")
                check = True
                number = [0 for _ in range(9)]  #초기화
                break
            number = [0 for _ in range(9)]  #초기화
    if check :
        break
            
    if max(number_row) != 1 or max(number_col) != 1 :  #행과 열 검사
        print("NO")
        number_row = [0 for _ in range(9)]
        number_col = [0 for _ in range(9)]
        break
    
    number_row = [0 for _ in range(9)]
    number_col = [0 for _ in range(9)]

else :  #for-else문 사용하여 break가 걸린 상황이 없다면 YES 출력
    print("YES")

 

[풀이 코드]

def check(a) :
    for i in range(9) :
        ch1 = [0]*10  #행체크
        ch2 = [0]*10  #열체크
        for j in range(9) :
            ch1[a[i][j]] = 1  #존재하는 숫자 인덱스에 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")

일단 너무너무 구림. 핑계를 대보자면 시간이 촉박했고,,, 아팠고,,,, 어쩌구,,,,

생성된 배열도 너무 많고 초기화 하는 부분도 구리고 반복문 조건문 구조도 깔끔하지 못 함

 

함수 써도 되는구나.... 그룹 탐색 방법과 숫자 체크하는 리스트에 1을 대입하는가와 +=1 한 것에 차이가 있음

 

 

---

Q11. 격자판 회문수 : 7*7 크기의 격자판에서 길이가 5인 회문수의 개수

입력 : 7*7 격자판

출력 : 회문수의 개수

 

[내가 쓴 코드]

a = [list(map(int, input().split())) for _ in range(7)]  #격자판 입력받기
result = 0  #회문수의 개수

p = list()  #대충 생성한 변수명

for i in range(7) :  #행의 관점에서 회문수 찾기, 길이가 7이니 3번 체크하면 됨
    for j in range(3) :
        part = a[i][j:j + 5]
        for k in range(2) :
            if part[k] != part[-1 -k] :  #회문수 아님
                break
        else :
            result += 1
            
for i in range(7) :  #열의 관점에서 찾기...
    for j in range(3) :
        for k in range(j, j + 5) :
            p.append(a[k][i])
        for m in range(2) :
            if p[m] != p[-1 -m] :
                p = []
                break
        else :
            result += 1
            p = []   

print(result)

 

[풀이 코드]

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)

다음 스터디는 더 성실하기...

 

 

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