✅ BOJ IT 기업 문제 풀이
🎈 13305 주유소
n개의 도시가 있고 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하고자 한다.
처음 출발 시 차에 기름이 없어 기름을 넣고 반드시 출발해야하며 1km 이동 시 1리터의 기름을 사용한다.
각 도시 별 리터 당 비용이 주어지고, 도시 간 이동에는 도로 길이가 주어질 때 최소 비용을 구하는 문제
입출력은 다음과 같다.
- 입력 : 첫 줄에 도시 수, 다음 줄에는 두 도시를 연결한 길이가 주어지고, 마지막 줄에는 리터 당 도시 별 가격이 주어진다.
- 출력 : 이동하는데 있어 최소 비용을 구하는 문제
import sys
input = sys.stdin.readline
n = int(input())
roads = list(map(int, input().split()))
cost = list(map(int, input().split()))
price = cost[0]
answer = 0
for i in range(n-1):
if price > cost[i]:
price = cost[i]
answer += price * roads[i]
print(answer)< 풀이 과정 >
출발 시 반드시 기름을 넣어야하므로 기름을 넣는 양은 다음 도시까지의 길이만큼 넣어 주어야 한다.
따라서 최초 비용 발생은 첫 도시의 리터만큼 발생한다.
이후 for문으로 n-1까지 진행하며 현재 가격이 이후 가격보다 크면, 비용을 갱신하고 도시 간 길이인 roads마다 해당 비용을 곱하여 최소 비용을 구할 수 있다.
🎈 20920 영단어 암기는 괴로워
첫 줄에 영어 단어 개수 n과 외울 단어 길이 m이 주어지고 n줄에 걸쳐 영단어가 주어질 때 한 줄에 한 단어씩 앞 줄에 위치한 단어부터 출력하는 문제 (m이상의 단어만 외우고자 한다)
우선순위 적용은 다음과 같다
- 자주 나올수록 앞에 배치
- 단어 길이가 길수록 앞에 배치
- 알파벳 사전 순으로 앞에 있는 단어 먼저 배치
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
dic = {}
for _ in range(n):
word = input().rstrip()
if len(word) < m:
continue
if word in dic:
dic[word][0] += 1
else:
dic[word] = [1, len(word), word]
answer = sorted(dic.items(), key = lambda x: (-x[1][0], -x[1][1], x[1][2]))
for i in answer:
print(i[0])< 풀이 과정 >
dic자료구조를 활용한 풀이
비교할 대상은 단어가 나온 횟수, 단어 길이, 단어(사전순비교) 이다.
for문에 걸쳐 단어를 입력받고, 길이가 m이하면 넘어간다
이후 dic에 word가 없다면 횟수, 길이, 단어를 넣어주고 있다면 횟수+ 1을 해준다.
이후 나온 횟수, 길이는 내림차순, 단어는 오름차순으로 정렬하여 최종적으로 키값만 뽑아서 출력한다.
🎈 2075 N번째 큰 수
숫자 n과 nxn크기의 그래프에 n보다 크거나 같은 값의 숫자들로 채워져있을때 n번째 큰 수를 구하는 문제
import sys
input = sys.stdin.readline
import heapq
n = int(input())
heap = []
for i in range(n):
number = list(map(int, input().split()))
if not heap:
for num in number:
heapq.heappush(heap, num)
else:
for num in number:
if heap[0] < num:
heapq.heappush(heap, num)
heapq.heappop(heap)
print(heap[0])< 풀이 과정 >
리스트를 새로 만들어 extend함수를 이용해 구축하고 index를 활용하여 계산했지만 메모리 초과가 나왔다. 그러나 위 인덱스 활용을 통한 풀이를 진행하면 시간복잡도가 급격히 증가했다. (10**9라는 범위로 인해..)
따라서 heapq를 활용한 최소 힙으로 문제를 구현하고자 했다.
우선 빈 heap을 만들고, n줄만큼 number를 입력받는다.
이후 heap이 비어있으면 number 원소를 각각 num이라 칭한 후 push해준다.
반대로 heap이 비어있지 않다면 number 원소인 num에 대해 heap의 최솟값이 num보다 작다면 이를 교체해주는 작업을 반복한다
위 과정을 거치면 heap은 n길이를 유지하면서 n번째 큰 수를 항상 0번째 인덱스로 저장하며 최소힙을 유지한다.
🎈 21921 블로그
X일 동안 가장 많이 들어온 방문자 수와 기간이 몇개 있는지 구하는 문제로 입출력은 다음과 같다.
- 입력: 첫줄에 블로그 시작하고 지난 일 수 N과 X가 공백으로 주어진다. 둘째 줄에는 블로그 1일차부터 N일차까지 하루 방문자 수가 공백으로 주어진다.
- 출력: 첫 줄에 X일동안 가장 많이 들어온 방문자 수를 출력하고 만일 0이라면 SAD를 출력, 최대 방문자 수가 0이 아니라면 둘째 줄에 기간이 몇개 있는지 출력한다.
import sys
input = sys.stdin.readline
n, x = map(int, input().split())
day = list(map(int, input().split()))
if max(day) == 0:
print('SAD')
else:
visitor = sum(day[:x])
max_visit = visitor
cnt = 1
for i in range(x, n):
visitor += day[i]
visitor -= day[i-x]
if visitor > max_visit:
max_visit = visitor
cnt = 1
elif visitor == max_visit:
cnt += 1
print(max_visit)
print(cnt)< 풀이 과정 >
max값 찾는 리스트와 기간 별 최대 횟수를 구하는 counting 리스트를 따로 만들어 구현했으나 시간초과가 발생했고 투포인터로 접근하나 했으나 슬라이딩 윈도우라는 기법을 활용한 문제
즉 한 칸씩 옮기면서 이전 칸까지의 결과는 겹치므로 중복된 항목을 응용하는 기법
구현한 코드를 풀이하면 다음과 같다.
- 주어진 일자별 최대값이 0인 경우 SAD를 출력한다
- 아닌 경우, 초기값으로 day[:x]까지의 범위를 합한 것을 visitor로 저장하고 이후 값들과 비교를 위해 max_visit을 새로 만들어준다. 그리고 동일한 최댓값을 갖는 기간이 또 있는지 확인을 위해 cnt 변수를 생성해준다.
- for문으로 x~n을 탐색하며 visitor 값을 해당 범위 내 x기간으로 변경해주며 max_visit과 비교해 max_visit 값을 변경해준다. 만일 동일한 경우 cnt를 1늘려준다.
✅ 문제 풀이 - Programmers LV3
🎈 퍼즐 조각 채우기
table 위에 놓인 퍼즐 조각을 이용해 game_board의 빈 공간에 다음 조건을 거쳐 적절히 올려놓고자 한다.
- 조각은 한 번에 하나씩 채워 넣는다
- 조각을 뒤집을 수 없고 회전시킬 수 있다
- game_board에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있어서는 안된다.
최종적으로 game_board에 비어있는 칸 들 중 총 몇 칸을 채울 수 있는지 구하는 문제
import copy
# 테이블에서 주어진 블록들 회전하기
def rotate(table):
n = len(table)
rotated_table = [[0]*n for _ in range(n)]
for i in range(n):
for j in range(n):
rotated_table[j][n-1-i] = table[i][j]
return rotated_table
# 탐색 진행 position : 기준이 되는 좌표 (해당 좌표로 옮기는데)
def dfs(board, x, y, position, n, num):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 현 기준 점 저장
result = [position]
# visit 처리
board[x][y] = 2
# 상하좌우 4방향으로, 다음 위치가 num인 경우에 한해 dfs탐색 결과 더해주기
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<n and board[nx][ny] == num:
result += dfs(board, nx, ny, [position[0] + dx[i], position[1] + dy[i]], n, num)
return result
def solution(game_board, table):
answer = 0
n = len(game_board)
# 현 game_board 내 빈칸 dfs 탐색 진행
blank = []
for i in range(n):
for j in range(n):
if game_board[i][j] == 0:
blank.append(dfs(game_board, i, j, [0, 0], n, 0))
# 4번 회전에 대해 각 table 모두 회전 처리 후
for i in range(4):
table = rotate(table)
# 블록 추가 이후의 결과 반영 위해 copy_table 생성
copy_table = copy.deepcopy(table)
for j in range(n):
for k in range(n):
# table에서 블록이 존재하면, puzzle 결과 저장
if copy_table[j][k] == 1:
puzzle = dfs(copy_table, j, k, [0, 0], n, 1)
# game_board 빈칸에 puzzle이 들어간다면 blank 채워주고 answer에 퍼즐 수 넣어주기
# 이어서 결과 확인 위해 copy_table 복사
if puzzle in blank:
blank.remove(puzzle)
answer += len(puzzle)
table = copy.deepcopy(copy_table)
# 주어진 빈칸에 puzzle이 맞지 않으면 table 다시 복사해서 진행
else:
copy_table = copy.deepcopy(table)
return answer< 풀이 과정 >
dfs를 활용하여 재귀 탐색으로 구현한 풀이
풀이 참조
해당 문제는 위 작성된 블로그를 통해 참고하였다 ✍️
풀이 과정은 다음과 같다.
- rotate함수 : 주어진 table에서의 블록을 회전하기 위해 i, j -> j, n-1-i로 좌표 변경
- dfs함수 : 현 그래프, 좌표, 기준점, 그래프 범위, 좌표상 숫자를 매개변수로 입력받아 4방향으로 탐색을 진행하며 다음 위치 역시 원하는 좌표상 숫자와 일치하면 result에 다음 dfs결과를 더하면서 진행
- solution 함수 : 우선 주어진 game_board에서 빈칸을 모두 blank 리스트에 저장해준다.
이후 4번 탐색을 진행하며(주어진 table 회전 수와 동일) 기존 table이 변화하는 과정을 보기 위해 deepcopy를 해준다.
table에 좌표 상 숫자가 1이면 블록이 있는 것이므로 puzzle을 dfs함수를 통해 구해주고, 해당 퍼즐 좌표가 blank에 속하면 블록을 채울 수 있으므로 채워주고 결과가 바뀐 copy_table을 table로 다시 deepcopy를 진행한다.
만일 blank에 puzzle이 속하지 않는다면 블록을 채울 수 없는 것이므로 결과 반영이 안된 table을 다시 deepcopy하여 copy_table을 이용하여 탐색을 이어 진행한다.
