nice!

[백준 14890번] 경사로 - Python으로 구현하기

문제 접근

• 경사로를 놓을 수 있는 방법 : 높은 곳 -> 낮은 곳  / 낮은 곳 -> 높은 곳
• 경사로가 겹치면 안되므로 경사로가 놓여진 부분은 따로 체크해주기
• 2d에서 행과 열을 모두 확인해봐야 되는 문제이다. 행에 대한 구현만 완료한 뒤 2d 행렬을 트랜스포즈하여 열을 확인하자.
• Python에서 2D array transpose : t_arr = list(zip(*arr))

생각해볼 점

• [i][j] , [j][i] 의 순서로 이중 반복문 하나로 한번에 처리 가능하다 => 사실 트랜스포즈 과정이 필요없다.

오답 분석

• 인덱스 표현에 주의하고 정확하게 하자! 한군데 틀리면 찾기 힘들다.
• 인덱스를 다루는 문제일 수록 경계값 처리 꼼꼼하게 확인하기

def row_solve(arr):
    global cnt
    chk = [[False] * n for _ in range(n)]
    for i in range(n):
        j = 0
        go_flag = True
        while j < n - 1:
            if arr[i][j] == arr[i][j + 1]:
                j += 1
                continue
            elif arr[i][j] - arr[i][j + 1] == 1:  # 높->낮
                if arr[i][j + 1:j+1+L].count(arr[i][j+1]) == L:
                    chk[i][j + 1:j + 1 + L] = [True] * L
                    j = j + L
                    continue
                else:
                    go_flag = False
                    break
            elif arr[i][j] - arr[i][j + 1] == -1:  # 낮->높
                if arr[i][j+1 - L:j+1].count(arr[i][j]) == L and True not in chk[i][j+1 - L:j+1]:
                    chk[i][j+1 - L:j+1] = [True] * L
                    j += 1
                    continue
                else:
                    go_flag = False
                    break
            else:
                go_flag = False
                break

        if go_flag:
            cnt += 1

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

cnt = 0
row_solve(map_data)
row_solve(list(zip(*map_data)))
print(cnt)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 14889번] 스타트와 링크 - Python으로 구현하기

문제 접근

• 두 팀으로 나누는 경우의 수를 어떻게 구할지?
• itertools 의 combinations 모듈 사용! n//2 개의 조합을 뽑아서 1팀과 2팀으로 나눔

생각해볼 점

• combinations 모듈 없이 어떻게 구현할지?

from itertools import combinations as cm
import math

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

min_ans=math.inf	# 정답

for case in cm(range(1,n+1),n//2):	# 두 팀으로 나눌 수 있는 경우의 수
    s1 = s2 = 0
    
    for i in case:	# 1팀 점수
        for j in case:
            s1+=datas[i-1][j-1]

    res = set(range(1, n + 1)) - set(case)	# 2팀 점수
    for i in res:
        for j in res:
            s2+=datas[i-1][j-1]
    min_ans=min(min_ans,abs(s1-s2))
print(min_ans)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 14888번] 연산자 끼워넣기 - Python으로 구현하기

문제 접근

• 주어진 연산자 개수내에 적절히 연산자를 조합하여 식 결과의 최댓값, 최솟값 찾기
• itertools 의 permutations 모듈 사용하여 모든 경우의수 확인
• set 을 사용하여 중복을 제거하자

생각해볼 점

• 재귀 함수로 구현 가능해보임

오답 분석

• 음수를 나누기 하는 경우 문제에 조건에 주어진 대로 처리

from itertools import permutations as pm

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

# 입력받은 명령어 저장
op=''
for idx,oper in enumerate(opers):
    op+=str(idx)*oper

op=list(map(int,op))
res_list=[]
for now_op in set(pm(op,len(op))):	# 경우의 수(중복 제거)
    res = nums[0]
    for idx in range(n-1):
        if now_op[idx] == 0:
            res+= nums[idx + 1]
        elif now_op[idx] == 1:
            res-= nums[idx + 1]
        elif now_op[idx] == 2:
            res *=nums[idx + 1]
        elif now_op[idx] == 3:
            res = res//nums[idx + 1] if res>0 else ((res*-1)//nums[idx+1])*-1	# 음수 나누기 조심
    res_list.append(res)

print(max(res_list))
print(min(res_list))

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 14503번] 로봇 청소기 - Python으로 구현하기

문제 접근

• 정말 주어진대로 구현해야되는 구현 문제
• 바라 보는 방향의 왼쪽을 표현하는 것이 관건
• 입력으로 주어진 방향의 왼쪽방향은 -1 씩 감소되고, 반대편 방향은 2가 차이 난다.(0,1인경우는 예외처리)
• 왼쪽방향 : n_dir = dir - 1 if dir>0 else 3 / 반대편 방향 : n_dir = dir - 2 if dir>1 else dir + 2

생각해볼 점

• 문제를 코드에 옮기기 전, 대략적으로 구성도를 짜고 작성하기

오답 분석

• 구현하면서 dir과 di가 헷갈리곤 했다. 변수 이름 잘 정해주기!

n,m=map(int,input().split())    # 맵 크기
r,c,dir = map(int,input().split())    # 로봇 r,c / 방향(0~3 : 북동남서)
map_data = [list(map(int,input().split())) for _ in range(n)]   # 빈칸0, 벽1
di = {0:[-1,0],1:[0,1],2:[1,0],3:[0,-1]}
while True:
    map_data[r][c] = 2  # 현재 위치 청소
    tmp_dir = dir
    chk_flag=False
    for _ in range(4):
        tmp_dir = dir-1 if dir>0 else 3 # 현재 보고있는 방향의 왼쪽부터 탐색
        nr=r+di[tmp_dir][0]
        nc=c+di[tmp_dir][1]
        if map_data[nr][nc]==0: # 왼쪽 방향에 청소 안한게 존재, 회전 후 한칸 전진

            dir=tmp_dir
            r,c=nr,nc
            chk_flag=True
            break
        else:
            dir=tmp_dir # 왼쪽 방향에 청소공간 없으면 회전

    if chk_flag:    # 왼쪽방향 청소안한게 있으면!
        continue

    tmp_dir = dir-2 if dir>1 else dir+2
    if map_data[r+di[tmp_dir][0]][c+di[tmp_dir][1]]==1:
        break
    else:
        r+=di[tmp_dir][0]
        c+=di[tmp_dir][1]

print(sum(map_data,[]).count(2))

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 14502번] 연구소 - Python으로 구현하기

문제 접근

• 바이러스의 확산 => BFS 알고리즘
• 벽을 세울 수 있는 경우의수 => itertools 모듈의 combinations, product
• 안전영역 확인 => chain, counter 모듈
• 메모리 효율성 문제로 제너레이터로 combinations 구현

생각해볼 점

• itertools 모듈 안쓰고 경우의수 어떻게 뽑으면 좋을지?
• copy 모듈을 이용하여 마지막 원상 복귀 코드 없애기

오답 분석

• 항상 불필요한 로직이 없는지 확인하기

# 연구소
import sys
input = lambda:sys.stdin.readline().rstrip()

from itertools import product,chain,combinations as cm
from collections import deque,Counter

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

dq=deque()
di =[[-1,0],[0,-1],[1,0],[0,1]] # 4방향
max_cnt=0

for wall in cm(list(product(range(n),range(m))),3):
    return_wall=True
    for w in wall:
        x,y=w
        if a[x][y]==1 or a[x][y]==2:    # 벽을 둘 수 없는 자리
            return_wall=False
            break
    if not return_wall: continue    # 벽 3개를 설치 못한 경우
    else:
        for w in wall:  # 벽 설치
            x,y=w
            a[x][y]=1

    # 바이러스들 deque에 삽입
    for i in range(n):
        for j in range(m):
            if a[i][j]==2:
                dq.append([i,j])

    # bfs
    while dq:
        x,y=dq.popleft()
        for k in range(4):
            nx=x+di[k][0]
            ny=y+di[k][1]
            if 0<=nx<n and 0<=ny<m and a[nx][ny]==0:
                dq.append([nx,ny])
                a[nx][ny]=-1

    c=Counter(chain(*a))    # 2차원 맵 -> 1차원 맵
    max_cnt=max(max_cnt,c[0])   # 0의 개수

    # 기존 맵으로 원상복귀
    for w in wall:
        x,y=w
        a[x][y]=0
    for i in range(n):
        for j in range(m):
            if a[i][j]==-1:
                a[i][j]=0
print(max_cnt)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!