왼쪽 구간을 왼쪽에서 오른쪽으로 진행하면서 최대 높이가 되기 전까지 높이가 높아질때마다 스택에 넣어준다.
구간을 구해주어야 하므로, 스택의 맨 마지막에는 최대 높이가 될 때의 지점도 저장해 준다.
오른쪽 구간을 오른쪽에서 왼쪽으로 진행하면서 최대 높이가 되기 전까지 높이가 높아질때마다 스택에 넣어준다.
구간을 구해주어야 하므로, 스택의 맨 마지막에는 최대 높이가 될 때의 지점도 저장해 준다.
(1)번과 (2)번 스택을 활용하여 왼쪽 구간과 오른쪽 구간의 넓이를 구해준다.
마지막으로, 최대 높이 구간 넓이를 구해서 더해준다.
왼쪽 -> 오른쪽으로 찾았을때의 최대 높이가 되는 지점
오른쪽 -> 왼쪽으로 찾았을 때의 최대 높이가 되는 지점
(2)에서 (1)을 빼준 값에 1을 더한 값이 최대 높이에서의 구간 합이다.
소스 코드
import sys
from bisect import bisect_left, bisect_right
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
block = []
for _ in range(N):
L, H = map(int, input().split())
block.append([L, H])
def rfind(arr, a):
for i in range(len(arr)-1, -1, -1):
if arr[i] == a:
return i
return -1
def lfind(arr, a):
for i in range(len(arr)):
if arr[i] == a:
return i
return -1
block.sort(key=lambda x:x[0])
block_value = list(map(lambda x:x[1], block))
max_block_value = max(block_value)
left = []
right = []
p = 0
# 왼쪽 구간 저장
while p < len(block) and block[p][1] != max_block_value:
if not left:
left.append(block[p])
elif left and left[-1][1] <= block[p][1]:
left.append(block[p])
p += 1
left.append(block[p])
# 오른쪽 구간 저장
p = len(block)-1
while p >= 0 and block[p][1] != max_block_value:
if not right:
right.append(block[p])
elif right and right[-1][1] <= block[p][1]:
right.append(block[p])
p -= 1
right.append(block[p])
right.sort(key = lambda x:x[0])
area = 0
# 왼쪽 구간 너비 합
for i in range(1, len(left)):
area += left[i-1][1] * (left[i][0] - left[i-1][0])
# 오른쪽 구간 너비 합
for i in range(1, len(right)):
area += right[i][1] * (right[i][0] - right[i-1][0])
# 높이가 가장 큰 부분의 너비 합
lindex = lfind(block_value, max_block_value)
rindex = rfind(block_value, max_block_value)
area += max_block_value * (block[rindex][0] - block[lindex][0] + 1)
print(area)
문자의 개수를 카운팅하다가 문자의 개수가 0이 아닌 3의 배수가 된다면, 다음에 나와야 하는 문자는 해당 문자가 되어야 한다.
따라서, 따로 플래그를 두어 개수가 3의 배수가 될 때의 문자를 저장해 두고, 바로 다음 문자가 해당 문자인지 체크하면 된다.
맨 마지막이 3의 배수가 딱 될때의 케이스는 따로 빼서 처리해 준다.
경우에 따라 OK, FAKE 출력
소스 코드
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
for i in range(n):
M = input()
counter = defaultdict(lambda: 0)
check = True
next_flg = False
next_chr = ''
for ch in M:
if not check:
break
if next_flg:
if ch != next_chr:
check = False
next_flg = False
continue
counter[ch] += 1
if counter[ch] % 3 == 0:
next_flg = True
next_chr = ch
# 다음에 문자가 하나 더 나와야 하는 경우
if next_flg:
check = False
if check:
print("OK")
else:
print("FAKE")
다른때와 다르게, 최단 경로를 저장하는 distance를 2차원 배열로 지정해주어야 해서 특이한 경험이었음.
[0, 0]에서 시작하여 현재 이동할 수 있는 좌표 중 가장 최소로 벽을 부수어야 하는 좌표로 먼저 이동하여 갱신한다.
상,하,좌,우로 이동하면서 거리 갱신이 가능한 경우 최소 히프에 넣어주는 방식으로 구현
벽이 있는 경우는 1을 더해주고, 벽이 없는 경우는 0을 더해주는데, 그냥 입력 배열에 저장되어있는 값을 더해준다.
마지막에, distance[N-1][M-1]을 출력해준다.
원래 이런 문제는 BFS로만 풀었었는데 다익스트라 알고리즘으로도 풀리네.. BFS로 풀면 중복이 훨씬 많이 일어나서 비효율적이긴 할듯.
소스 코드
import sys
import heapq
input = lambda: sys.stdin.readline().rstrip()
M, N = map(int, input().split())
matrix = [list(map(int, list(input()))) for _ in range(N)]
distance = [[int(10e9)] * M for _ in range(N)]
distance[0][0] = 0
heap = []
heapq.heappush(heap, [0, 0, 0])
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
while heap:
dist, x, y = heapq.heappop(heap)
if distance[x][y] != dist:
continue
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if 0 <= nx and nx < N and 0 <= ny and ny < M:
if distance[nx][ny] > dist + matrix[nx][ny]:
distance[nx][ny] = dist + matrix[nx][ny]
heapq.heappush(heap, [distance[nx][ny], nx, ny])
print(distance[N-1][M-1])
처음엔 그냥 무턱대고 BFS로 풀이를 진행하였으나.. 큐에 데이터가 너무 많이 들어가게 되서 그런지 메모리 초과가 계속해서 발생하였다ㅜㅜ
그래서 BFS처럼 큐에 데이터가 가득 쌓이지는 않으니까 DFS로 풀이를 바꾸어서 진행하였다.
현재 위치에서 동,서,남,북으로 다음 위치로 이동할 때, 다음 위치에 있는 말이 이전까지 방문한 알파벳에 포함되어있지 않다면 DFS 진행
재귀함수를 호출하면서 다음 방문 위치와 현재 방문한 알파벳들도 같이 넘겨주어야 한다.
DFS를 진행하면서 최대 이동 거리를 계속해서 갱신시켜준다.
큐에 데이터가 많이 쌓이게 되면 메모리 초과가 발생하니 BFS뿐 아니라 DFS로도 풀이를 해야 하는걸 배움. 또한 방문처리 할때 set 자료구조에 너무 의존하지 말고, 알파벳은 최대 26개이니까 방문 알파벳들을 문자열로 쭉 연결한 다음 set 연산자가 아닌 in 연산자를 사용하여도 크게 문제될 건 없어보임.
소스 코드
import sys
input = lambda: sys.stdin.readline().rstrip()
R, C = map(int, input().split())
matrix = [list(input()) for _ in range(R)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0
def solve(visited_str, x, y):
global R, C
skip = True
answer = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx and nx < R and 0 <= ny and ny < C:
if matrix[nx][ny] not in visited_str:
skip = False
answer = max(answer,
1 + solve(visited_str + matrix[nx][ny], nx, ny))
if skip:
return 1
else:
return answer
print(solve(matrix[0][0], 0, 0))
아래 소스는 F('stories_filed') + 1 자체를 SQL Syntax로 만들어버려서 reporter.stories_filed의 값이 1 증가하는 쿼리가 실행된다. 이 때, reporter.stories_filed의 값을 갱신하는것이 아님. 데이터베이스 자체의 SQL문 실행
reporter.stories_filed 값을 실제 저장된 값으로 업데이트하기 위해선 모델을 데이터베이스에서 다시 불러와주어야 한다.
F Object는 save() 이후에도 모델에 남아있는 문제가 있으며, 각 save()에 적용된다. 따라서 초기 값이 1이라고 할 때, 처음 save 연산자를 해주면 SQL문이 실행되어 2가 되는데, 다음에 또 save 연산을 해주면 또 SQL문이 실행되어 3이 된다.이 과정을 해결해주기 위해서는 refresh_from_db()를 사용해주면 된다.
여기서, 알파벳 ['a', 'n', 't', 'i', 'c']는 기본적으로 무조건 들어가야 된다는 점을 알 수 있음.
따라서, K가 5보다 작은 경우는 불가능하므로 0을 출력해주면 되고, 5보다 큰 경우는 두가지로 나눌 수 있다.
기본적으로 ['a', 'n', 't', 'i', 'c']는 들어가야 함.
(1)에서 제외한 알파벳들 중 (K-5)개를 뽑음.
1번과 2번을 합치면 하나의 케이스가 된다.
각각의 케이스별로 총 몇개의 단어를 읽을수 있는지 체크하고, 최댓값을 갱신하면 된다.
위 과정을 Set 자료구조로 하였는데.. 자꾸 메모리 초과가 나와서 풀이를 좀 찾아보니 비트 마스킹 기법을 사용한다고 한다. 알파벳 위치를 기준으로 비트 '1'을 이동시키는 방식
a인 경우 001, b인 경우 010, c인 경우 100, ... , ab인 경우 011, ...
전체 단어들에 대해 각 단어들을 알파벳 별로 미리 비트화를 시켜준다.
hello의 경우, 알파벳이 h,e,l,o가 있으므로 대응되는 비트값을 1로 수정
각각의 케이스 비교단계에서 케이스 또한 비트화를 시켜준 다음 and 연산자를 해준다.
케이스에서 ['a', 'n', 't', 'i', 'c', 'k']를 뽑았다고 할 때, 단어가 antic인 경우 모두 공통적으로 a, n, t, i, c의 비트가 1로 조정되어 있으므로, and연산자를 해주면 a,n,t,i,c에만 1로 지정되어 있을 것이다.
and 연산자의 결과가 케이스의 비트와 같은 경우 읽을 수 있는 단어이므로 카운팅
비트 마스킹이 set보다는 빠르므로 set이 속도 문제로 안된다면, 고려해보아야 한다는걸 배우게 되었다..
소스 코드
import sys
from itertools import combinations
input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
words = [0] * N
base = ['a', 'n', 't', 'i', 'c']
for i in range(N):
word = list(input())[4:-4]
for ch in word:
words[i] |= (1 << ord(ch) - ord('a'))
answer = 0
if K < 5:
pass
else:
alpha = 'bdefghjklmopqrsuvwxyz'
append_case = list(combinations(list(alpha), K-5))
for case in append_case:
make_bit = 0
for ch in base:
make_bit |= (1 << ord(ch) - ord('a'))
for ch in case:
make_bit |= (1 << ord(ch) - ord('a'))
count = 0
for i in range(len(words)):
if words[i] & make_bit == words[i]:
count += 1
answer = max(answer, count)
print(answer)
보면 N값과 M값이 굉장히 크기 때문에 전수조사 하게 되는 경우 시간초과가 100% 날거라 생각됨.
따라서, 친구들이 심사를 받는데 걸리는 시간을 기준으로 이분탐색을 진행함.
범위는 최소 0, 최대 1000000000 * 10^9를 잡아주어야 한다.
이유는 입국심사대에 1명이 있으며, 친구들이 1000000000명, 그리고 걸리는 시간이 10^9인 경우를 고려
중간값을 기준으로 중간값일때 심사받는 친구의 수가 M보다 크거나 같으면 시간을 줄여야 하므로 정답 저장후 왼쪽 구간, M보다 작은 경우는 정답을 저장하진 말고 오른쪽 구간을 진행하면 된다.
저장된 정답을 출력해 준다.
소스 코드
import sys
input = lambda : sys.stdin.readline().rstrip()
N, M = map(int, input().split())
T = [int(input()) for _ in range(N)]
left = 0
right = (1000000000 * int(10e9)) + 1
answer = 0
while left <= right:
mid = (left + right) // 2
# 중간값일때, 심사받는 사람의 수 구함
evaluated_people_count = 0
for time in T:
evaluated_people_count += (mid // time)
# 심사받는 사람의 수가 M보다 작으면 시간을 늘려야 하므로 오른쪽 구간
# M보다 크거나 같으면 시간을 줄여야 하므로 왼쪽 구간
if evaluated_people_count >= M:
answer = mid
right = mid - 1
else:
left = mid + 1
print(answer)