방구석프로의 이야기

https://school.programmers.co.kr/learn/courses/30/lessons/12909

문제 해결을 위한 과정

이 문제의 경우 괄호를 (, )로 분리하면 쉽게 해결할 수 있는 문제였습니다.

각각 (의 경우 1을 더하고, )인 경우 1을 빼주면 되는데 )부터 시작하면 올바르지 않은 괄호이고 결과는 음수, (()) 이렇게 올바른 경우는 1 + 1 - 1- 1이므로 결과는 0, ((()) 올바르지 않은 괄호는 1 + 1 + 1 - 1 - 1 이므로 양수 즉 올바르지 않은 경우입니다. 이를 문제에 적용하면 쉽게 해결할 수 있습니다.

소스코드

def solution(s):
    answer = True
    res = 0
    
    for i in range(len(s)):
        if s[i] == "(":
            res += 1
        else:
            res -= 1
        if res < 0:
            return False
    if res == 0:
        return True
    else:
        return False

https://school.programmers.co.kr/learn/courses/30/lessons/42627

문제 해결을 위한 과정

이 문제의 경우 heapq를 이용하면 해결할 수 있는 문제였습니다.

과정을 설명하면 다음과 같습니다.

1. jobs 리스트 정렬

2. 맨 처음 인덱스에 해당하는 값을 이용해 finish, answer 할당(finish는 작업이 끝나는 시간, answer는 대기 시간)

3. 다시 jobs 리스트를 정렬하며 finish 보다 request가 이전인 경우(작업 중에 들어온 요청인 경우) heapq에 삽입

4. heapq가 존재하면 가장 짧은 duration을 가진 작업을 이용해서 finish, answer 재할당

5. heapq가 존재하지 않으면 jobs리스트를 정렬하며 맨 처음 인덱스에 해당하는 값을 이용해 finish, answer 할당

이 부분에서 8번 18번 테스트 케이스를 틀렸었는데 이는 동일 request에 여러 작업이 들어올 수 있기 때문입니다. 따라서 jobs 리스트를 정렬 시 lambda를 이용해서 request기준으로 오름차순을 하고, 만약 request가 같다면 duration으로도 오름차순 정렬을 해주면 됩니다.

소스코드

import heapq

def solution(jobs):
    answer = 0
    length = len(jobs)
    length2 = len(jobs)
    jobs.sort(key = lambda x: (x[0], x[1]))
    finish = 0
    finish = jobs[0][1] + jobs[0][0]
    answer += jobs[0][1]
    jobs.pop(0)
    length2 -= 1
    
    while length2 != 0:
        jobs.sort(key = lambda x: (x[0], x[1])) 
        q = []
        for i in range(len(jobs)):
            request, time = jobs[i]
            if request <= finish:
                heapq.heappush(q, (time, request, i))
        if len(q) != 0:
            time, request, idx = heapq.heappop(q)
            if request <= finish: # 하드디스크 작업 수행 중 들어온 요청인 경우
                finish = finish + time
                answer += finish - request
                length2 -= 1
                jobs.pop(idx)
            else:
                heapq.heappush(q, (time, request, idx)) # 하드디스크가 작업 수행을 하지 않는 경우   
        else:
            jobs.sort(key = lambda x: (x[0], x[1])) 
            request, time = jobs[0] # 가장 앞에 작업 수행
            finish = request + time
            answer += finish - request
            jobs.pop(0)
            length2 -= 1
    answer = answer // length
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42583

문제 해결을 위한 과정

이 문제의 경우 deque를 이용하면 쉽게 해결할 수 있는 문제였습니다.

과정은 다음과 같습니다.

1. 다리에 존재하는 트럭들 한 칸 이동시키기 - queue를 (truck, cnt)로 pair 형태로 넣어두면 cnt를 1 증가시키는 걸로 가능

2. 1의 과정 이 후 제일 앞에 있는 트럭의 cnt가 bridge_length와 같다면 popleft 해주기. (다리를 다 이동한 경우)

3. 다리에 존재하는 트럭들의 무게를 확인하여 남은 트럭 중 제일 앞에 트럭을 올려도 올라가는지 확인

    3-1. 올라갈 수 있다면 다리에 올리기

    3-2. 올라갈 수 없다면 다리에 올리지 않기

소스코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    finish = deque()
    moving = deque()
    length = len(truck_weights)
    
    while True:
        if len(finish) == length:
            break
        answer += 1
        for i in range(len(moving)): # 이동
            truck, cnt = moving[i]
            moving[i] = truck, cnt + 1           
        if len(moving) != 0:
            truck, cnt = moving[0] 
            if cnt == bridge_length: # 다리 다 이동하면 finish로 이동
                finish.append(moving.popleft())
        tempWeight = 0
        for i in range(len(moving)):
            truck, cnt = moving[i]
            tempWeight += truck
        if len(truck_weights) != 0 and tempWeight + truck_weights[0] <= weight:
            moving.append((truck_weights[0], 0))
            truck_weights.pop(0)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42586

문제해결을 위한 과정

이 문제는 각 배열을 조회하면서 해당하는 speeds를 더해주면 됩니다. 그 후 100이 넘는지 확인한 뒤(작업 완료) 완료된 작업만큼을 꺼내주면 되는 문제입니다. 단 이때 해당하는 인덱스의 speeds도 꺼내줘야 합니다. 소스코드는 다음과 같습니다.

소스코드

def solution(progresses, speeds):
    answer = []
    while True:
        if len(progresses) == 0:
            break
        for i in range(len(progresses)):
            progresses[i] += speeds[i]
        cnt = 0
        for i in range(len(progresses)):
            if progresses[i] >= 100:
                cnt += 1
            else:
                break
        for i in range(cnt):
            progresses.pop(0)
            speeds.pop(0)
        if cnt > 0:
            answer.append(cnt)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/12906

문제 해결을 위한 과정

이 문제는 배열의 길이 1,000,000 이므로 이중 For문이 아닌 단일 for문으로 해결해야 합니다.
현재 인덱스와 다음 인덱스를 비교해서 다른 경우에만 answer 리스트에 append 해주는 식으로 쉽게 해결할 수 있습니다.

소스코드

def solution(arr):
    answer = []
    arr.append("a")
    for i in range(len(arr)-1):
        if arr[i] != arr[i+1]:
            answer.append(arr[i])
    return answer

https://www.acmicpc.net/problem/17140

문제 해결을 위한 과정

이 문제는 구현 문제로 문제의 과정을 코드로 작성하면 쉽게 해결할 수 있었습니다. 다만 예제 6번의 경우, R C가 각각 3 3 이므로 정렬을 한번 하면 3, 3이 존재하지 않으므로 이 경우는 그냥 pass 하면 해결할 수 있습니다.

소스코드

R, C, K = map(int, input().split())

graph = []
for _ in range(3):
  graph.append(list(map(int, input().split())))

ans = 0

def graphSort(graph):
  for i in range(len(graph)):
    numArr = [0] * 101
    temp = []
    maxNum = 0
    for j in range(len(graph[i])):
      numArr[graph[i][j]] += 1
    for k in range(1, 101):
      if numArr[k] != 0:
        temp.append((k, numArr[k]))
        maxNum += 2
    temp.sort(key = lambda x: (x[1], x[0]))
    if maxNum >= 100:
      maxNum = 100
    tempArr = []
    for k in range(0, maxNum, 2):
      tempArr.append(temp[k//2][0])
      tempArr.append(temp[k//2][1])
    graph[i] = tempArr
  maxCol = 0
  for i in range(len(graph)):
    maxCol = max(maxCol, len(graph[i]))
  for i in range(len(graph)):
    tempNum = maxCol - len(graph[i])
    for j in range(tempNum):
      graph[i].append(0)
      
while True:
  if ans > 100:
    ans = -1 
    break
  if len(graph) >= R and len(graph[0]) >= C:
    if graph[R-1][C-1] == K:
      break
  ans += 1
  rowCnt = len(graph)
  colCnt = len(graph[0])
  if rowCnt >= colCnt: # R연산
    graphSort(graph)
  else: # C 연산
    a = len(graph) # 행 정보
    b = len(graph[0]) # 열 정보
    tempGraph = [[0] * a for _ in range(b)]
    for i in range(b):
      for j in range(a):
        tempGraph[i][j] = graph[j][i]      
    graphSort(tempGraph)
    a = len(tempGraph)
    b = len(tempGraph[0])
    orgGraph = [[0] * a for _ in range(b)] 
    for i in range(b):
      for j in range(a):
        orgGraph[i][j] = tempGraph[j][i]      
    graph = orgGraph

print(ans)

https://www.acmicpc.net/problem/15683

문제 해결을 위한 과정

이 문제의 경우 백트래킹을 이용해서 풀 수 있었습니다. 가장 중요한 건 각 cctv별로 이동할 수 있는 부분을 다음과 같이

direction = [
  [[0], [1], [2], [3]],
  [[0, 2], [1, 3]],
  [[0, 1], [1, 2], [2, 3], [3, 0]],
  [[0, 1, 3], [0, 1, 2], [1, 2, 3], [2, 3, 0]],
  [[0, 1, 2, 3]]
]

리스트 형태로 표현할 수 있어야 한다는 것 입니다. 1번(0번 인덱스) 카메라는 한 번에 한 방향만을, 2번(1번 인덱스) 카메라는 위아래 혹은 좌우를, 3번(2번 인덱스) 카메라는 90도만큼 두 개의 방향을, 4번 (3번 인덱스) 카메라는 한 번에 세 방향을, 5번(4번 인덱스) 카메라는 상하좌우 모두를 감시할 수 있습니다. 이 것을 코드로 표현하면 위의 소스코드와 같습니다.

이때 백트래킹(dfs)으로 모든 경우를 조회하면 해결할 수 있었습니다. 단 이때 원본 배열(graph)에 현재 감시 상황을 덮어씌우면 안 되므로 copy.deepcopy를 이용해 새로운 복사 배열을 생성하여 넘겨주어야 합니다.

소스코드

import copy

n, m = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
ans = int(1e9)
direction = [
  [[0], [1], [2], [3]],
  [[0, 2], [1, 3]],
  [[0, 1], [1, 2], [2, 3], [3, 0]],
  [[0, 1, 3], [0, 1, 2], [1, 2, 3], [2, 3, 0]],
  [[0, 1, 2, 3]]
]

camera = []
graph = []

for _ in range(n):
  graph.append(list(map(int, input().split())))
for i in range(n):
  for j in range(m):
    if 1 <= graph[i][j] <= 5:
      camera.append((i, j, graph[i][j]))

def dfs(depth, tempGraph):
  global ans
  if depth == len(camera):
    cnt = 0
    for i in range(n):
      for j in range(m):
        if tempGraph[i][j] == 0:
          cnt += 1
    ans = min(ans, cnt)
    return 

  temp = copy.deepcopy(tempGraph)
  x, y, cctv = camera[depth]
  for i in range(len(direction[cctv-1])):
    for j in range(len(direction[cctv-1][i])):
      tx, ty = x, y
      while True:
        nx = tx + dx[direction[cctv-1][i][j]]
        ny = ty + dy[direction[cctv-1][i][j]]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
          break
        if temp[nx][ny] == 6:
          break
        if temp[nx][ny] == 0:
          temp[nx][ny] = cctv
        tx, ty = nx, ny
    dfs(depth + 1, temp)
    temp = copy.deepcopy(tempGraph)
    tx, ty = x, y
dfs(0, graph)
print(ans)

https://school.programmers.co.kr/learn/courses/30/lessons/42626

문제 해결을 위한 과정

이 문제는 heapq를 이용하면 쉽게 해결할 수 있는 문제였습니다. 매번 정렬을 한다면 효율성의 문제가 생길 수 있으므로 최소힙을 이용해 O(logN)으로 가장 작은 값을 꺼내면 됩니다. 이 때 2개씩 꺼내어 더 맵게 하는 과정을 거치는데 q의 길이가 1이라면 두번을 꺼낼 수 없으므로 예외처리를 따로 해주시면 됩니다.

소스코드

import heapq

def solution(scoville, K):
    answer = 0
    q = []
    for i in range(len(scoville)):
        heapq.heappush(q, scoville[i])
    while True: 
        if len(q) >= 2:
            num1 = heapq.heappop(q)
            num2 = heapq.heappop(q)
        elif len(q) == 1:
            num1 = heapq.heappop(q)
            if num1 < K:
                answer = -1
                break
        if num1 >= K:
            break
        answer += 1
        heapq.heappush(q, (num1 + num2 * 2))
    
    return answer