Coding 공부

내 최초 풀이

# step 1 봄버맨 폭탄 설치 설치시간 동일
# step 2 정지
# step 3 폭탄이 설치되어 있지않은 모든칸에 폭탄을 설치
# step 4 1초가 지난후 3초전에 설치된 폭탄이 모두 폭발한다.
# step 5 step 3 ~ step 4 반복
dx = [1,-1,0,0]
dy = [0,0,1,-1]

R,C,N = map(int,input().split())
# R은 행 C은 열 N은 초
bomb = [list(input()) for _ in range(R)]
times = [[-1]*C for _ in range(R)]

for x in range(R):
    for y in range(C):
        if bomb[x][y] == 'O':
            times[x][y] = 3

        

for k in range(N):
    bomb_set = set()
    if k%2:
        for x in range(R):
            for y in range(C):
                times[x][y] -= 1
                if bomb[x][y] == '.':
                    times[x][y] = 3
                    bomb[x][y] = 'O'
    else:
        for x in range(R):
            for y in range(C):
                times[x][y] -= 1
                if times[x][y] == 0:
                    bomb_set.add((x,y))
                    for i in range(4):
                        nx = x + dx[i]
                        ny = y + dy[i]
                        if 0<=nx<R and 0<=ny<C:
                            bomb_set.add((nx,ny))
    for nx,ny in bomb_set:
        bomb[nx][ny] = '.'





for rows in range(R):
    print(''.join(bomb[rows]))

내 최초 풀이 방식은 문제의 방식을 그대로 따라한것이다.

문제를 보면 알수 있듯이 2의 배수의 시간일때는 폭탄을 설치해주는 것을 알 수 있다.

폭탄을 저장할 수 있는 리스트와 폭탄이 폭파되기까지 걸리는 시간을 저장해주기 위한 리스트를 두 종류를 준비해주었다.

그래서 2의 배수의 시간일때에는 폭탄을 설치해주고, 그 외의 시간에는 폭탄의 시간이 줄어들면서 터지는 폭탄의 위치들을 집합에 모아주고, 그것을 폭파해주는 방식으로 해주어 시뮬레이션을 해주었다.

이 풀이는 단순히 문제에 적혀져 있는 방식대로 시뮬레이션을 돌린거다 보니, 시간이 오래걸렸다.

# heecheol1508 클론코딩


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

if N%2 == 0:
    # 시간이 짝수일때는 무조건 전부 폭탄이 설치되기 때문에, 시간이 짝수일때는 전부 폭탄이 설치된 경우를 출력하면 된다.
    for _ in range(R):
        print('O'*C)
elif N == 1:
    # 1초일때는 초기 상태를 그대로 출력하면 된다.
    for row in board:
        print(''.join(row))
else:
    # 그 외의 시간일때는 나머지를 출력하면 된다.
    # 그런데 해당문제에서는 폭탄이 터지는 경우는 크게 2가지 밖에 없다.
    # 최초 설치된 폭탄 즉 0초에 설치된 폭탄이 터지는 경우와 
    # 2초에 설치된 폭탄 중에 최초 설치된 폭탄과 인접하지 않는 폭탄이 터지는 경우 2가지밖에 없다.
    # 그렇기 때문에 최초 설치된 폭탄이 터ㅣ는 시간대와 2초에 설치된 폭탄이 터지는 경우 두가지만 구분하면 된다.
    # 최초 설치된 폭탄이 터지는 시간대는 3초,7초,11초,15초로 4초 간격으로 터진다. 
    # 2초에 설치된 폭탄 중 최초 설치된 폭탄과 인접하지 않은 폭탄이 터지는 시간은 5초,9초,13초,17초이다.
    # 먼저 터지는 것은 최초 설치된 폭탄의 위치와 그와 인접한 폭탄이다. 그 부분만 폭탄이 터지는걸로 해주고 나머지는 폭탄이 설치된 걸로 만들어주면 된다.
    # 그래서 최초 폭탄이 터졌을때의 상황을 만들어주고, 그때의 시간이 3,7,11,15일때에는 그대로 출력하고,
    # 그때가 아닐때에는 2초에 설치된 폭탄이 터지는 경우이니 한번 더 폭탄이 터지는 것을 반복해주면 된다.
    bomb = []
    for x in range(R):
        for y in range(C):
            if board[x][y] == 'O':
                board[x][y] = '.'
                bomb.append((x,y))
            else:
                board[x][y] = 'O'
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    for bx,by in bomb:
        for i in range(4):
            nx = bx + dx[i]
            ny = by + dy[i]
            if 0<=nx<R and 0<=ny<C:
                board[nx][ny] = '.'

    times = (N-3)%4
    if not times:
        for row in board:
            print(''.join(row))
    else:
        bomb = []
        for x in range(R):
            for y in range(C):
                if board[x][y] == 'O':
                    bomb.append((x,y))
                    board[x][y] = '.'
                else:
                    board[x][y] = 'O'
        for bx,by in bomb:
            for i in range(4):
                nx = bx + dx[i]
                ny = by + dy[i]
                if 0<=nx<R and 0<=ny<C:
                    board[nx][ny] = '.'
        for row in board:
            print(''.join(row))

위의 코드 같은 경우 백준의 heecheol1508님의 코드를 분석하고, 이해한뒤 클론코딩한 것이다.

문제를 보면 2의 배수시간일때에는 폭탄이 빈곳에 설치하기 때문에 모든 배열에 폭탄이 설치되는 것이 알 수 있다.

그래서 주어진 시간이 2의 배수이면 폭탄이 전부 설치된 것을 보여주면 된다.

그리고 폭탄이 터지는 경우는 2가지 케이스이다.

최초로 설치된 폭탄이 터지는 경우와 2초에 설치한 폭탄이 터지는 경우이다.

최초의 설치된 폭탄과 2초에 설치된 폭탄이 터질때 서로 영향을 못준다. 왜냐하면, 폭탄이 터지면서 상하좌우를 터트리고 연쇄 폭파가 일어나지 않기 때문에, 일종의 안전지대가 생성이 되는 것이다. 

그렇기 때문에 이런한 성향을 이용하여, 계산하면 된다.

최초 설치된 폭탄은 3초에 최초로 터지고 그 뒤로 7초 11초 15초 4의 간격으로 터진다.

그래서 처음에 설치된 폭탄들이 터졌을때의 상황을 만들어주고,

위의 시간이 아니면 2초에 설치된 폭탄들이 터지는 것을 구현해주면 된다.

# 16236번 아기상어
# N*N 크기에 물고기 M마리 아기상어 1마리
# 아기상어 초기 크기는 2,
# 자기보다 큰 물고기는 먹기x 지나가기 x
# 자기와 같은 물고기 먹기x, 지나가기 o
# 자기보다 작은 물고기 먹기 o 지나가기 o
# 아기상어는 자기 크기 만큼의 횟수만큼 물고기를 먹는다면 크기가 1 증가한다.
# 먹을 수 있는 물고기가 없으면 엄마상어에게 가기
# 먹을 수 있는 물고기가 1마리면 거리가 가장 가까운 물고기를 먹으러간다.
# 먹을수 있는 물고기가 가장 가까운 거리에 있는걸 먹는다. 위 1순위 왼쪽 2순위 위로 정렬 왼쪽으로 정렬 2중정렬
# 1~6 은 물고기 9은 아기상어 위치
dx = [-1,1,0,0]
dy = [0,0,-1,1]
N = int(input())
aquarium = [list(map(int,input().split())) for _ in range(N)]
fishs = []
for x in range(N):
    for y in range(N):
        if aquarium[x][y]:
            if aquarium[x][y] == 9:
                shark_x = x
                shark_y = y
time = 0
shark_size = 2
shark_eat = 0
flag = True
while flag:
    eat_fishs = []
    visited = [[0]*N for _ in range(N)]
    shark = []
    shark.append((shark_x,shark_y,0))
    visited[shark_x][shark_y] = 1
    while shark:
        x,y,distance = shark.pop(0)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < N and 0<= ny< N:
                if not visited[nx][ny]:
                    if aquarium[nx][ny] > shark_size:
                        continue
                    else:
                        visited[nx][ny] = 1
                        if aquarium[nx][ny] == shark_size or aquarium[nx][ny] == 0:
                            shark.append((nx,ny,distance+1))
                        else:
                            shark.append((nx,ny,distance+1))
                            eat_fishs.append((nx,ny,distance+1))
    if not len(eat_fishs):
        break
    else:
        eat_fishs.sort(key=lambda x: (x[2],x[0],x[1]))
        aquarium[shark_x][shark_y] = 0
        shark_x = eat_fishs[0][0]
        shark_y = eat_fishs[0][1]
        shark_eat += 1
        aquarium[shark_x][shark_y] = 9
        time += eat_fishs[0][2]
        if shark_eat == shark_size:
            shark_size += 1
            shark_eat = 0
print(time)
            
    

 아기상어 문제는 조건들을 정리하는 것이 먼저였다.

1. 상어보다 작거나 같은 크기의 물고기들은 지나갈수 있다.

2. 상어는 자기보다 작은 물고기만 먹는다.

3. 가장 가까운 물고기를 먼저 먹는다.

4. 같은 위치에 존재하면, x축이 작은 것을 1순위, y축이 작은것이 2순위이다.

5. 상어의 크기의 개수만큼의 물고기를 먹으면 상어가 커진다.

이 부분을 정리하고 풀면 쉬웠다.

기본적으로 BFS를 하는대신 상대적인 거리를 측정하기 위한 distance를 넣어주었다.

그래서 상어가 먹을 수 있는 모든 물고기의 위치를 파악해주고, 거리를 측정해주었다.

여기서 시간을 더 줄이고 싶으면, 어차피 BFS이기 때문에 최소거리로 측정이 된다.

그러므로, 최초로 먹을수 있는 물고기와의 거리를 측정하고 그 거리보다 큰 것들이 나오는 순간 BFS를 멈춰도 된다.

하지만 시간제한이 널널한 편이었고, 첫시도였기 때문에, 머리로만 생각하고 넘어갔다.

위와 같이 먹을 수 있는 물고기목록을 구한뒤에는 lambda를 통한 다중정렬을 해서 문제 조건에 맞게 오름차순으로 정리해준다.

그리고 선택된 물고기의 위치를 상어의 위치로 바꿔주고, 상어의 크기와 상어의 먹은 물고기의 수를 비교해줘서 같아지면 상어의 크기를 키워주고 먹은 물고기 수를 초기화 시켜줬다.

이 문제에서 시간이 좀 걸렸던 요인은 움직인 상어의 이전 위치의 좌표를 초기화 안 시켜줘서 생겼다. 그냥 상어의 최초위치만 파악하고 난뒤에는 상어의 위치는 지속적으로 추적이 가능하므로, 그냥 상어의 값을 0으로 바꿔주는게 더 편할수 있을 것 같다.

import sys
from collections import deque
# 까다로웠던 점 
# 회전은 전부 판별이 되고 난뒤에, 작동한다
gears =[ list(deque(map(deque,sys.stdin.readline().split()))) for _ in range(4)]

K = int(sys.stdin.readline())
# 12시 0, 3시 2, 9시 6
# N극은 0 S극은 1
for _ in range(K):
    index,rotate = list(map(int,sys.stdin.readline().split()))
    leftindex = index-1
    leftrotate = -rotate
    rightrotate = -rotate
    rightindex = index+1
    rotatelist = []
    while leftindex >=1:
        origingear = list(gears[leftindex][0])
        leftgear = list(gears[leftindex-1][0])
        if origingear[6] == leftgear[2]:
            break
        else:
            rotatelist.append([leftindex-1,leftrotate])
        leftrotate = -leftrotate
        leftindex-=1
    while rightindex <=4:
        origingear = list(gears[rightindex-2][0])
        rightgear = list(gears[rightindex-1][0])
        if origingear[2] == rightgear[6]:
            break
        else:
            rotatelist.append([rightindex-1,rightrotate])
        rightrotate = -rightrotate
        rightindex+=1
    for rotateindex,rotation in rotatelist:
        gears[rotateindex][0].rotate(rotation)
    gears[index-1][0].rotate(rotate)


result = 0

for i in range(4):
    tw = gears[i][0].popleft()
    if tw == '1':
        result += 2**i

print(result)

이 문제에서 까다로웠던 점은 한번 사이클이 다 돌고 난뒤에 회전을 한다는 것이다. 그 부분을 처음에 놓쳤기에 틀렸다.

deque 모듈에는 rotate라는 메소드가 있으며, 양수를 적으면, 양수만큼 오른쪽으로 이동하고, 음수를 적으면 음수의 크기만큼 왼쪽으로 이동하는 것을 이용하여, 반시계와 시계방향의 회전을 구현했다.

print(ord(input()))

# 출력을 할때에도 여러번 반복하는 것이면 곱해서 하자 곱하기가 된다.


import sys
N = int(sys.stdin.readline())
array = [0 for _ in range(10001)]
for _ in range(N):
    num = int(sys.stdin.readline())
    array[num] += 1
for k in range(10001):
    print(f'{k}\n'*array[k],end='')

처음에 출력을 할떄

if array[k]:
   for _ in range(array[k]):
        pirnt(k)

위와 같은 식으로 했었다. 그랬더니 무수한 메모리 초과 오류가 발생했다.

아마도 매번 range(array[k]) 만큼의 리스트를 만들어줘야했기에, 메모리가 초과 된것 같다.

크게 두가지 방법이 있는것 같아다.

sys에 있는 write를 이용해 출력을 하는방법과

print()를 횟수만큼 곱해서 하는방법이 있었다.

그 중에서 나는 후자를 선택했다.

N = int(input())

if N >= 90:
    print('A')
elif N >= 80:
    print('B')
elif N >= 70:
    print('C')
elif N >= 60:
    print('D')
else:
    print('F')

# 7576번 문제 
# 1은 익은 토마토 0은 익지않은 토마토

N,M = map(int,input().split())

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

dx = [-1,1,0,0]
dy = [0,0,1,-1]
tomatocnt = 0
total = N*M
tomato = []
for x in range(M):
    for y in range(N):
        if tomatoarray[x][y] == 1:
            tomato.append((x,y))
            tomatocnt += 1
        elif tomatoarray[x][y] == -1:
            total -= 1
result = -1
day = 0
if total == tomatocnt:
    result = 0
else:
    while tomato:
        new_tomato = []
        for x,y in tomato:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<M and 0<=ny<N:
                    if not tomatoarray[nx][ny]:
                        tomatoarray[nx][ny] = 1
                        new_tomato.append((nx,ny))
                        tomatocnt += 1


        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomato = [row[:] for row in new_tomato]
        else:
            result = -1
            break



print(result)

익은 토마토를 기준으로 상하좌우로 인접한 토마토들만 익는다. 

1일차의 토마토가 익힌 인접 토마토들이 2일차에 새로운 토마토들을 익히게 된다.

그러므로 1일차의 토마토들은 필요 없어진다.

이런한 점을 이용해, 반복문을 통해 새롭게 익은 토마토들을 찾아내고, 그때 토마토 개수를 늘려준다. 

그리고 난뒤 전체 행렬의 크기와 토마토 개수가 같으면 반복문을 탈출하고,

새롭게 익은 토마토들이 있으면, 더 익힐 가능성이 있으므로, 그 리스트를 복사해서 반복해준다.

하지만 새롭게 익은 토마토들이 없으면, 더이상 익힐 가능성이 없으므로, 반복문을 탈출해서 -1을 출력해주면 된다.

# 7569 토마토

M,N,H = map(int,input().split())

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

tomatoarray =[ [list(map(int,input().split())) for _ in range(N)] for _ in range(H)]
# tomato dz dx dy
# H,N,M

total = N*M*H
tomatocnt = 0
tomatos = []
result = -1
day = 0
for x in range(N):
    for y in range(M):
        for z in range(H):
            if tomatoarray[z][x][y] == 1:
                tomatos.append((x,y,z))
                tomatocnt += 1
            elif tomatoarray[z][x][y] == -1:
                total -= 1
if total == tomatocnt:
    result = 0
else:
    while tomatos:
        new_tomato = []
        for x,y,z in tomatos:
            for i in range(6):
                nx = x + dx[i]
                ny = y + dy[i]
                nz = z + dz[i]
                if 0<=nx<N and 0<=ny<M and 0<=nz<H:
                    if not tomatoarray[nz][nx][ny]:
                        tomatoarray[nz][nx][ny] = 1
                        tomatocnt += 1
                        new_tomato.append((nx,ny,nz))
        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomatos = [row[:] for row in new_tomato]
        else:
            result = -1
            break
print(result)

이 문제는 7576번 문제의 3D 버전이다 여기서 조심해야할 것은 3차원이고, x,y,z의 순서를 조심해주면 된다.

보통 문제를 풀때 나같은 경우 x축을 행으로 하고 y축을 열로 한다. 자신만의 기준을 가지고, 헷갈리지 않게 조심하면 될 것 같다.

기본 원리는 7576번하고 같다.