수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/14719

문제 이해 

- 처음에는 예제만 적용해서 풀이를 작성했는데, 이는 범용적인 케이스를 고려하지 않았기에 틀렸다. 

- 그래서 풀이를 찾아보니 주어진 원소들을 하나씩 탐색하면서 i번째 원소의 왼쪽과 오른쪽 리스트에서 각각 최대값을 구한다. 

- 이 최대값 중 더 작은 값이 i번째 원소 높이가 낮아야 물이 고일 수 있다. 그래서 이 경우에만 높이 차이를 answer에 더해주면 된다. 

정답풀이 

h, w = map(int, input().split())
buildings = list(map(int, input().split()))

answer = 0
for i in range(1, w - 1):
    left_max = max(buildings[:i])
    right_max = max(buildings[i + 1:])
    
    compare = min(left_max, right_max)
    
    if buildings[i] < compare:
        answer += compare - buildings[i]
        
print(answer)

시도한 풀이 

같은 크기의 최대 높이가 2개 이상일 때 적용이 되지 않는다. 

h, w = map(int, input().split())
buildings = list(map(int, input().split()))

# 최대 높이를 기준으로 왼쪽, 오른쪽 나눠서 진행
# 양쪽 최대 높이 보다 한단계 작은 수가 높이가 되어서 물 채우면 됨
answer = 0
if buildings.count(0) <= w - 2:
    max_value = max(buildings)
    max_index = buildings.index(max_value)
    
    a = max(buildings[:max_index])
    for i in range(max_index):
        answer += a - buildings[i]
        
    if max_index + 1 < w and buildings[max_index + 1]:
        b = max(buildings[max_index + 1:])
        for i in range(max_index + 1, w):
            answer += b - buildings[i]
     
print(answer)

참고 블로그 : https://seongonion.tistory.com/115

- 문제 : https://www.acmicpc.net/problem/20055

문제 이해 

- 어떻게 풀어야 하는지 문제 자체가 이해가지 않았던 문제

- 로봇을 컨베이어 벨트에 올리는데 컨베이어 벨트의 0인덱스에만 로봇 박스를 올릴 수 있다. 

- 로봇을 올린 후 로봇은 한 칸씩 앞으로 갈 수 있는데, 이 때 앞 칸의 내구성이 1 이상이고, 로봇이 없어야 한다. 

- 각 컨베이어 벨트 칸에는 내구성이 주어지는데, 이는 로봇이 하나씩 지날때마다 1씩 감소한다. 

- 그리고 n번째 컨베이어벨트에서는 무조건 로봇을 내려야 한다. 

- 로봇을 올리고, 이동할 수 있을 때 이동하는 과정을 한단계라고 한다면, 이 단계를 총 몇 번해야하는지 출력하는 문제다. 

- 작동이 멈추는 조건은 컨베이어 벨트 칸의 내구성이 0인 벨트의 개수가 k개 이상일 경우이다. 

추가로 파이썬의 rotate()함수도 알게 되었는데, 이는 deque 라이브러리에 있는 함수로, rotate(1)을 하면 오른쪽으로 이동하고, 가장 뒤에 있는 것이 가장 앞으로 온다. 

- 예시

a = deque([1, 2, 3, 4, 5])
print(a)

a.rotate(1) # 오른쪽으로 이동
print(a)

# 출력
deque([1, 2, 3, 4, 5])
deque([5, 1, 2, 3, 4])

정답 풀이 

from collections import deque

n, k = map(int, input().split())
belt = deque(list(map(int, input().split())))
robot = deque([0] * n)
answer = 0

while True:
    belt.rotate(1)
    robot.rotate(1)
    robot[-1] = 0
    
    if sum(robot): #로봇이 존재할 때
        for i in range(n - 2, -1, -1):
            if robot[i] == 1 and robot[i + 1] == 0: # 다음 칸에 로봇 없고
                if belt[i + 1] >= 1 : #벨트 내구성 1이상
                    robot[i + 1] = 1
                    robot[i] = 0
                    belt[i + 1] -= 1
        robot[-1] = 0 # 맨 마지막에 있는 박스 내림 
        
    if robot[0] == 0 and belt[0] >= 1 : # 올리는 위치에 로봇 없고, 내구성 1이상
        robot[0] = 1
        belt[0] -= 1
    
    answer += 1
    if belt.count(0) >= k:
        break

print(answer)

참고 블로그

https://unie2.tistory.com/924

https://yeomss.tistory.com/290

- 문제 : https://www.acmicpc.net/problem/14503

문제 이해 

- 문제를 읽었을 때 탐색 문제라는 것은 파악을 했지만, 방향을 고려해야 하는 상황이 있어서 그 부분이 조금 어려웠다. 

- 청소기의 동작 방식은 다음과 같다 . 

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90도 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다

- 1번의 경우는 visit 행렬 값이 0인 곳인 경우 1로만 바꾸면 되고, 2번의 경우는 상하좌우에서 0인 칸이 없을 때 진행한다. 현재 위치의 방향에서 -1 할 수 있고, 돌아간 위치에서 상하좌우를 살펴서 빈 칸을 향해 움직인다. 만약 현재 방향에서 -1 칸 했는데 벽이라면 거기서 끝낸다. 3번은 상하좌우에서 visit 값이 0인 곳이 있으면 현재 방향에서 반시계 방향으로 90도 회전한 뒤 해당 방향을 앞쪽 칸 visit 값이 0인 경우에만 전진한다. 

- 반시계 방향 90도를 돌았을 때를 구현하기 위해 dx, dy도 그에 맞춰서 설정해줘야 한다. 

    - 0, 1, 2, 3 은 각각 북, 동, 남, 서 방향을 의미한다. 

    - 북(0)에서 반시계 90도를 돌면 서(3), 서(3)에서 반시계 90도를 돌면 남(2), 남(2)에서 반시계 90도를 돌면 동(1), 동(1)에서 반시계90도를 돌면 북(0)이다. 

    - 이는 현재 방향을 d라고 한다면 반시계 방향으로 90도 돌 경우 그 위치는 (d + 3) % 4를 의미한다. 

    - 그래서 dx, dy는 순서대로 북, 동, 남, 서 를 가리켜야 한다. 

- 작동 순서는 1, 2, 3으로 되어있지만 로직은 3, 1, 2 순서로 진행되어야 한다. 청소할 수 있는 칸을 확인한 다음, 청소할 수 있으면 하고, 청소할 수 있는 칸이 없다면 그때 뒤로 후진하고 벽을 만난다면 break를 해야한다. 

- 한 칸 전진한다는 의미는 x, y = x + dx[d], y + dy[d] 한다는 것이며, 한 칸 후진한다는 의미는 x, y = x - dx[d], y - dy[d] 한다는 의미이다. 

정답 풀이 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
x, y, d = map(int,input().split())

matrix = []
visit = [[0] * m for _ in range(n)]

# d => 0,3,2,1 순서로 돌아야한다.
dx = [-1,0,1,0]
dy = [0,1,0,-1]

for _ in range(n):
    matrix.append(list(map(int,input().split())))

# 처음 시작하는 곳 방문 처리
visit[x][y] = 1
cnt = 1

while True:
    flag = False
    # 4방향 확인
    for _ in range(4):
        # 한번 돌았으면 그 방향으로 작업시작
        d = (d+3)%4
        
        # 현재 방향에서 반시계 방향 90도 회전
        nx, ny = x + dx[d], y + dy[d]
        
        # 상하좌우에서 접근할 수 있고, 방문하지 않은 위치 존재
        if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:
            if not visit[nx][ny]:
                visit[nx][ny] = 1
                cnt += 1
                x, y = nx, ny
                #청소 한 방향이라도 했으면 다음으로 넘어감
                flag = True
                break
                
    if not flag: # 4방향 모두 청소가 되어 있을 때,
        if matrix[x - dx[d]][y - dy[d]] == 1: #후진했는데 벽
            print(cnt)
            break
        else:
            x, y = x - dx[d], y - dy[d]

참고 블로그 : https://resilient-923.tistory.com/164

- 문제 : https://www.acmicpc.net/problem/20006

문제 이해 

- 처음에 player명의 플레이어들이 들어와서 방에 참여하거나 방을 만드는 게임이다 

- 각 방에는 참여인원이 member로 제한되고, 참여도 처음 들어간 사람의 레벨이 기준이 되어 그 레벨에서 -10에서 +10 인 레벨만 입장이    가능하다. 

- 만약 들어갈 수 있는 방이 없다면 새로 방을 만든다. 

- 이렇게 각 플레이어에 대해 방 입장을 다 시켰으면 각 방 별로 member의 수만큼 있는 곳은 Started!를 출력하고, 그 방에 있는 플레이어의 레벨과 닉네임을 닉네임을 오름차순으로 한 뒤 출력한다. 

- 만약 방의 인원수가 member 보다 작다면 Waiting!을 출력하고, 각 방에 있는 플레이어의 레벨과 닉네임을 닉네임을 오름차순으로해서 출력하면 된다. 

- 이 문제에서 생각을 좀 해야했던 부분은 각 방에 들어가는 조건이 인원수와 기준레벨로 두 가지였다는 것과 마지막에 방에 있는 플레이어    의 레벨과 닉네임을 출력하는 것이었다. 

  그러면 각 정보를 모두 배열에 넣었어야 했기에 배열 answer를 다음과 같이 설정했다. 

  만들어진 방 순서대로 들어간다는 조건도 있었는데, 이는 순서대로 방을 생성한 뒤 방을 왼쪽부터 순차대로 진행하면 된다. 

(인덱스 -> 방 번호), [인원수, 기준 레벨, [레벨, 닉네임]]

- answer에 들어가는 각 방 정보를 다음과 같이 한 다음에 각 인원수와 기준 레벨로 방 참여 여부를 결정하고, 그렇지 않다면 새로 방을 만    들어 주면 된다. 

정답 풀이 

import sys
input = sys.stdin.readline

players, member = map(int, input().split())

answer = [] # 방이 생성되어서 들어감 (인덱스 -> 방 번호), [인원수, 기준 레벨, [레벨, 닉네임]]
for i in range(players):
    level, nickname = input().split()
    level = int(level)
    flag = False
    
    for j in range(len(answer)):
        if answer[j][0] < member: 
            if answer[j][1] - 10 <= level <= answer[j][1] + 10:
                answer[j].append([level, nickname])
                answer[j][0] += 1
                flag = True
                break
    if not flag: # 기존에 있는 방에 못 들어감
        answer.append([1, level, [level, nickname]])
        
for i in range(len(answer)):
    if answer[i][0] == member :
        print('Started!')
        result = sorted(answer[i][2:], key = lambda x : x[1])
        for j in range(member):
            print(result[j][0], result[j][1])
    else: 
        print('Waiting!')
        result = sorted(answer[i][2:], key = lambda x : x[1])
        for j in range(answer[i][0]):
            print(result[j][0], result[j][1])