[문자열, 그리디] [1차] 추석 트래픽 (Lv.3)
걸린 시간
1시간 30분
접근 방식
예시 이미지에서 그리디를 바로 떠올렸다.
모든 구간의 끝부분에서 1초내의 타임라인 속 겹치는 타임라인이 몇 개 존재하는지 세어보는 방식으로 접근했다.
두 타임라인이 있다면 고정된 타임라인 기준 6가지 경우의 수가 있다.
1. 아예 이전 타임라인인 경우
2. 이전 타임라인이지만 1초 내에 걸친 경우
3. 1초를 포함하는 타임라인인 경우
4. 1초 내에 포함된 타임라인인 경우
5. 이후 타임라인이고 1초내에 걸친 경우
6. 아예 이후 타임라인인 경우
즉 1초 타임이 정해져있다면
(다른 타임의 끝시간 < 1초 타임의 시작시간) or (다른 타임의 시작시간 > 1초 타임의 끝시간)이면 겹치지 않는다.
사실 끝타임을 기준으로 정렬되어있기에 1, 2, 4번은 없는 경우다.
정답 코드
def solution(lines):
if len(lines) == 1:
return 1
answer = 0
timelines = []
for l in lines:
day, time, during = l.split(" ")
h, m, s = time.split(":")
s, ms = s.split(".")
total = int(h)*60*60*1000 + int(m)*60*1000 + int(s)*1000 + int(ms)
during = during[:-1]
response = 0
if during.find(".") != -1:
m, ms = map(int, during.split("."))
response = m*1000 + ms
else:
response = int(during) * 1000
timelines.append([total, response])
l = len(timelines)
for i in range(l):
cnt = 1
start = timelines[i][0]
end = timelines[i][0] + 999
for j in range(i+1, l):
if timelines[j][0] < start or timelines[j][0] - timelines[j][1] + 1 > end:
continue
cnt += 1
answer = max(answer, cnt)
return answer배운점
논리가 완벽하더라도 구현할 때 이상, 이하, 초과, 미만의 차이는 여전히 헷갈리는 것 같다.
index 함수보다 find 함수가 값이 없을 때 -1을 반환해서 더 유용한 것 같다.
[구현] [3차] 자동완성 (Lv.4)
걸린 시간
1시간 15분
접근 방식
유니크한 조합이 나왔을 경우 그 길이만큼 반환하는 방식으로 접근했다.
모든 단어를 정렬하면 알파벳순으로 되는데 이 상태에서 idx번째 글자에서 같은 알파벳들 끼리 묶어서 idx+1번째 글자들을 조사하다가 같은 알파벳이 없는 경우에 해당 유효 길이를 반환하는 방식이다.
go, gone, guild의 경우
0번째 글자는 모두 g이므로 0~2번째 단어의 1번째 글자를 탐색한다.
1번째 글자는 o, o, u 이므로
o에 해당하는 0~1번째 단어의 2번째 글자를 탐색하고,
u에 해당하는 2~2번째 단어의 2번째 글자를 탐색한다.
이 때 u에 해당하는 글자는 한 개 뿐이므로 2번째 글자에 해당하는 2를 반환한다.
다시 o로 돌아가서
2번째 글자는 ' ', n 이므로
공백일 경우 3번째 글자가 공백이므로 3-1을 반환한다.
그 다음 n을 조사하면 되지만 이 경우 유일한 글자이므로 3을 반환한다.
이런 식으로 재귀함수를 통한 DFS? 로 문제를 해결했다.
정답 코드
def check(words, start, end, depth):
if start == end:
if len(words[start]) >= depth:
return depth
else:
return depth - 1
cnt = 0
# 처음 depth를 확인할 때 빈칸이라면
if len(words[start]) == depth:
print("빈칸 발견", words[start], depth)
cnt += depth
start += 1
# 빈칸 다음이 끝이라면
if start == end:
return cnt + depth + 1
idx = start
word = words[start][depth]
for i in range(start, end):
# 다음 단어의 depth+1번째 글자가 다르다면?
if words[i+1][depth] != word:
print(idx, "~", i, "의", depth+1 , "번째 글자 체크")
val = check(words, idx, i, depth+1)
print("반환값", val)
cnt += val
word = words[i+1][depth]
idx = i+1
# 마지막에 도달하면 거길 끝idx로 해서 재귀함수 호출
if i == end - 1:
print(idx, "~", i+1, "의", depth+1 , "번째 글자 체크 (마지막)")
val = check(words, idx, i+1, depth+1)
print("반환값(마지막)", val)
cnt += val
print("cnt", cnt, "start", start, "end", end, "depth", depth)
return cnt
def solution(words):
words.sort()
return check(words, 0, len(words)-1, 0)배운점
이 문제는 문자열 검색을 최적화하는 Trie(트라이) 자료구조를 활용해 해결하는 것이 가장 효율적이라고 한다.
어쩐지 문자열 기반 해결법은 좀 빡셌다.
[DP] 최적의 행렬 곱셈 (Lv.3)
걸린 시간
50분 (포기) + 이해 30분
접근 방식
처음에 30분동안 고민하다가 잘못 곱해버리면 행렬 계산이 안되는 경우를 어떻게 분리할지 도저히 모르겠어서 질문하기 탭에서 힌트만 보려고 했다.
근데 문제 설명에는 없지만 이 문제는 행렬의 순서가 선형 연결 순서를 보장한다고 한다.
그래서 기존에 생각했던 큰 연결부분부터 곱하는 그리디로 해결할 수 있을거라 생각했지만
[[9, 10], [10, 9], [9, 1], [1, 2]]
위와 같은 반례를 통해 그리디는 안된다는 것을 깨달았다.
그리디를 사용할 시 9x10x9 + 9x9x1 + 9x1x2로 909가 되지만
10,9와 9,1을 먼저 곱하면 최솟값인 198이 나온다.
아무리 고민해도 모르겠어서 해설을 봤다.
https://school.programmers.co.kr/questions/34123
점진적으로 n을 늘리면서 n개의 행렬 조합의 최솟값을 저장하는 2차원 배열을 쓰는 DP 방식으로 푸는 것이었다.
정답 코드
def solution(matrix_sizes):
l = len(matrix_sizes)
DP_list = [[10000000000 for _ in range(l)] for _ in range(l)]
for i in range(l):
DP_list[i][i] = 0
for i in range(l):
for j in range(l-i):
a = j
b = j+i
for k in range(a, b):
DP_list[a][b] = min(DP_list[a][b], DP_list[a][k] + DP_list[k+1][b] + (matrix_sizes[a][0] * matrix_sizes[k][1] * matrix_sizes[b][1]))
return DP_list[0][l-1]배운점
여전히 깔끔한 풀이 코드를 보면 벽이 느껴진다.
이 문제와 같은 점진적으로 하나씩 2차원 DP 배열을 채워나가는 경우는 3중 for문에서 k값을 어떻게 주어줘야하는지, 점화식은 어떻게 작성하는지를 잘 따져봐야 할 것 같다.
그리고 이 문제는 선형 연결 순서를 보장한다는 말이 없어서 더 헤맸던 것도 있어서 뭔가 이상하면 30분쯤에 질문하기를 살짝 살펴보는 것도 좋을 것 같다.
