2023년 7월 30일 알고리즘 문제풀이
백준 5904번
1차 시도
나의 생각
재귀 함수를 통해 각 문자열을 구할 수 있었다. 또한 그 문자열의 길이도 규칙적이므로 몇번째 재귀에서 n번째 문자열이 등장하는지를 알아내어 그 문자열의 index를 통해 구하였다. 하지만 메모리 초과와 시간 초과로 인하여 오답처리 되었다.
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
def moo(k):
if k == 0:
return 'moo'
return moo(k-1)+'m'+'o'*(k+2)+moo(k-1)
i = -1
while True:
i += 1
tmp = moo(i)
if len(tmp) >= n:
print(tmp[n-1])
break
2차 시도
나의 생각
문자열을 구하면 안된다고 생각하였다. 다음 문자열이 이전 차례의 문자열 두개에 하나의 규칙적인 문자가 껴있는 형태라는 사실에 집중하였다. 예를 들어 S(10)의 몇번째 문자열인지는 S(9)의 문자열을 통해 알 수 있다. 원리는 다음과 같다.
어떤 자연수 i를 차수로 하는 문자열을 3부분으로 나눈다.
(1) 차수를 i-1로 하는 문자열, (2) 1개의 m과 (i+2)개의 o로 이루어진 문자열, (3) (1)과 같은 문자열
셋 중 어디에 속하느냐를 통해 문자가 무엇인지 알 수 있다. 어떤 차수의 문자열의 길이를 구하면, 그 다음 차수의 문자열의 길이를 구한다.그 문자열에 n번째 글자가 존재한다면 위 원리를 통해 어디에 속해있는지 구한다.
(1)에 속한다면 현재 차수의 문자열에서 구하는 것과 마찬가지 일 것이다. 하지만 이 경우는 존재하지 않는다. 이 경우는 한 번 더 이전 차수에서 필터링 되었을 것이기 때문이다.
(2)에 속한다면 n에서 현재 차수의 길이만큼을 뺀 후 살펴본다. 첫번째만 ‘m’이고, 나머지는 ‘o’이다.
(3)에 속한다면 n에서 현재 차수의 길이만큼을 빼고 m과 o의 갯수의 합인 (i+3)을 또 빼준다. 여기 문자열은 (1)과 동일하므로 n에서 뺀 값을 현재 문자열에서 구하면 된다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
# legnth는 문자열의 길이, i는 차수
def search(k,length,i):
if k == 1:
print('m')
return
elif k == 2 or k == 3:
print('o')
return
next_length = 2*length+i+3
if k > next_length:
search(k,next_length,i+1)
else:
if k > length and k <= i+3+length:
if k - length == 1:
print('m')
else:
print('o')
return
else:
k -= (length+i+3)
search(k,3,1)
search(n,3,1)
백준 9935번
1차 시도
나의 생각
폭탄의 문자열 길이를 생각한 후 스택을 통해 하나씩 문자열에 넣으며 항상 마지막만 체크하여 폭탄이 완성되었는지 검사하는 방법을 생각하였다.
폭탄은 어떤 문자가 들어오는 순간에 완성될 수 밖에 없다
폭탄이 터져 새로운 문자열이 만들어져도 그 안에 새롭게 폭탄이 생길 수 없다. 다음 새롭게 들어오는 문자열을 통해 폭탄이 완성될 뿐이다. 이유는 문자가 이어붙어져 만들어지는 순간에 폭발해야 하기 때문이다. 예제에서 C4가 문자열이였는데 4가 들어와서 C옆에 붙여지는 순간 폭발하는 것이 당연하다. 안터지다가 갑자기 나중에 붙어있던 C4가 터질리는 없으니까.. 따라서 터져서 문자열이 새롭게 만들어져도 다음 문자열이 들어오는 때에만 검사하면 된다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
word = list(sys.stdin.readline().rstrip())
bomb = sys.stdin.readline().rstrip()
n = len(bomb)
arr = []
ans = ''.join(word[:3])
for i in range(len(word)):
arr.append(word[i])
if len(arr) < n:
continue
k = len(arr)
tmp = ''.join(arr[k-n:])
if tmp == bomb:
for _ in range(n):
arr.pop()
if arr:
print(*arr,sep='')
else:
print('FRULA')
백준 1933번
1차 시도
나의 생각
빌딩의 왼쪽 좌표를 기준으로 정렬하였다. 빌딩마다 순회하며 최소 힙을 통해 가장 큰 빌딩의 높이를 업데이트하였다. 저장할 때 2차원으로 오른쪽 좌표도 저장하여 새로운 빌딩의 왼쪽 좌표가 현재 가장 높은 빌딩의 오른쪽 좌표보다 오른쪽에 있다면 그 빌딩을 heap에서 제거하도록 구현하였다. 최고높이의 빌딩은 다른 빌딩을 검사하는 것과 별개로 업데이트 되야 하는데, 그 부분이 부족했다. 그 결과, 아무 빌딩도 없이 0인 값이 중간에 나올 수 있음에도 필터링하지 못하였다.
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys
from heapq import heappush, heappop
n = int(sys.stdin.readline())
buildings = []
for _ in range(n):
l,h,r = map(int,sys.stdin.readline().split())
buildings.append([l,r,h])
buildings.sort(key=lambda x:x[0])
arr = []
ans = []
for i in buildings:
if not arr:
heappush(arr,[-i[2],i[0],i[1]])
continue
new_i = [-i[2],i[0],i[1]]
heappush(arr,new_i)
while True:
if arr[0][2] < new_i[1]:
heappop(arr)
else:
break
if not ans or arr[0][0] != ans[-1]:
ans.append(arr[0][1])
ans.append(-arr[0][0])
print(ans)
2차시도
나의 생각
빌딩을 heap에 넣을때 끝나는 것까지 미리 넣는다. 그 후 다음 빌딩이 들어올 때 이전 빌딩이 끝나고 들어왔다면 그대로 두고, 끝나기 전에 들어왔다면 미리 넣어논 것을 제거한 후 업데이트한다. 마지막 쯤에 이런 생각이 들었다. ‘어떤 빌딩이 시작되고, 더 큰 빌딩이 들어왔다가 처음 들어온 빌딩보다 먼저 끝났다면?’… 쉽게 말하자면 A시작-B시작-B끝-A끝 의 순서라면 내 로직은 엉망진창이 된다. 결론은 실패. 완성도 못했다.
결과
실패
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import sys
from heapq import heappush, heappop
n = int(sys.stdin.readline())
buildings = []
for _ in range(n):
l,h,r = map(int,sys.stdin.readline().split())
heappush(buildings,[l,h,r])
arr = []
ans = []
x = 0
h = 0
lim = 0
while buildings:
tmp = heappop(buildings) # 빌딩 선정
if not arr: # 아직 그려진 스카이라인이 없음
ans.append(tmp[0]) # 지금 들어온 빌딩의 왼쪽
ans.append(tmp[1]) # 지금 들어온 빌딩의 높이
ans.append(tmp[2]) # 지금 들어온 빌딩의 오른쪽(새로운 빌딩 나타나지 않을 경우를 대비)
ans.append(0) # 끝나면 높이는 다시 0으로 바뀜
h = tmp[1]
lim = tmp[2]
heappush(arr,[-tmp[1],tmp[2]])
continue
if tmp[0] < lim: # 선정한 빌딩의 왼쪽 좌표가 이전 빌딩의 오른쪽좌표보다 먼저 나타남
ans.pop() # 설정해둔 오른쪽좌표와 높이 0 삭제
ans.pop() # 설정해둔 오른쪽좌표와 높이 0 삭제
heappush(arr,[-tmp[1],tmp[2]]) # 빌딩 heap에 저장
if ans[-1] < -arr[0][0]: # 최대힙을 통한 빌딩의 높이가
ans.append(tmp[0])
ans.append(tmp[1])
ans.append(tmp[2])
ans.append(0)
print(ans)
3차 시도
나의 생각
너무 어려워서 다른 사람의 풀이 내용을 보며 이해하였다. 이걸 혼자 생각해야한다니… 난 아직 갈길이 정말 멀다. 혹여나 어려워하는 사람을 위해 최대한 자세히 설명해보겠다.
buildings: 건물의 index와 점의 좌표, 점의 성질(시작점인지 끝점인지)를 저장하는 배열
heights : 건물의 index에 알맞게 건물의 높이를 저장할 배열(최대힙을 위해 음수로 저장한다.)
ends 건물의 index에 알맞게 건물의 끝점을 저장할 배열
heap: 현재 상황에서 높이가 존재하는 건물들을 저장할 배열(heap)
arr: 이미 지나가서 처리가 완료된 끝점들을 저장할 배열(set)
ans: skyline이 업데이트 될 때마다 정답을 위해 변동상황을 저장할 배열
건물로 생각하지 않고 건물의 두 점을 하나의 단위로 생각한다. 건물의 왼쪽 좌표와 오른쪽 좌표를 각각 시작점과 끝점이라고 할 수 있다. 끝점 이후에는 해당 건물의 높이가 스카이라인에 적용되지 않기 때문이다. 입력에서 건물의 높이와 시작점, 끝점 3개가 한꺼번에 주어지지만, 배열에 담을때는 각 점의 좌표와 빌딩의 높이만 저장하고, 시작점인지 끝점인지를 표기하는 flag를 추가하였다. 그리고 각 빌딩의 index를 표기하고 그에 알맞게 높이를 위한 배열과 끝점을 위한 배열에도 데이터를 추가하였다. 이로서 각 빌딩의 index를 통해 높이, 점의 좌표, 시작점인지 끝점인지 등 다양하게 알 수 있게 되었다.
입력받은 빌딩 정보를 점의 성질에 따라 두개로 나누어 저장하였는데, 이를 정렬하였다. 겹치는 상황에서 누가 우선순위를 가지는 지를 기준으로 정렬하였다. 점의 좌표를 오름차순으로 하여 정렬한 후, 시작점을 우선으로 해주었다. 끝점은 그 점 이후로 빌딩이 없어져 높이가 0이 된다는 뜻이다. 반대로 시작점은 그 점 이후로 빌딩이 나타나 높이가 존재한다는 뜻이다. 스카이라인은 더 큰 높이값을 기준으로 만들어지니 높이가 존재하는 시작점을 신경써야한다. 따라서 시작점이 끝점보다 우선된다. 둘 다 같은 시작점이라면 높이가 더 높은 점을 신경써야한다. 가장 높은 빌딩만 스카이라인에 나타나기 때문이다. 그 후 현재 스카이라인이 그려지는 최고 높이를 저장하는 변수도 설정하였다.
저장한 모든 점들을 순회한다. 시작점이라면 새로운 빌딩이 나타나니 heap에 저장한다.
혹시 현재 skyline이 그려지는 높이보다 클 경우 새롭게 그려지니 변수 `h`를 업데이트하고 정답 배열 `ans`에도 저장한다.
heap에는 h와 상관없이 저장하는데, 현재 h인 빌딩이 끝날 경우에 최고 높이가 될 수도 있기 때문이다.
순회하다가 끝점을 만난다면 우선 arr 처리할 것이기 때문에 arr에 담는다.
즉 `arr`에는 이미 처리가 된 끝점도 저장되지만 어떤 빌딩이 사라져야하는 지를 검사하기 위한 배열이기도 하다.
그리고 현재 높이가 존재하는 빌딩들이 담긴 heap을 순회하며 조사하게 된다. heap의 0번 index에는 가장 높은 빌딩의 높이와 끝점이 나타나게 되는데, 이 빌딩의 끝점이 arr에 존재하지 않는다면 아직 사라질 필요가 없으니 heap에 대한 조사를 멈춘다. arr에 존재한다면? 끝난 빌딩이니 heappop으로 삭제하고, 새로운 heap[0]이 나타나게 된다. 새로운 최대 높이의 빌딩도 끝점이 arr에 존재하는지 검사한다. 이를 반복하다 끝점이 지나가거나 이미 만난 빌딩이 더이상 존재하지 않으면 heap 조사를 멈춘다.
이 때 heap에 아무것도 남아있지 않다면 현재상황에서 높이가 존재하는 빌딩이 없다는 뜻이니 스카이라인이 그려지지 않게 된다.
따라서 `h` 를 0으로 설정한다. 존재한다면 `heap[0]`이 가장 높이가 높은 빌딩일테니 이를 `h`로 설정한다. 이 두 경우 모두 `h`가 업데이트 되었으니 정답 배열 `ans`에도 저장해야 한다.
결과
이해
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import sys
from heapq import heappush, heappop
n = int(sys.stdin.readline())
buildings = [] # 빌딩들을 담을 배열
heights = [0] * n # 빌딩의 높이를 담을 배열
ends = [0] * n # 빌딩의 오른쪽 점을 담을 배열
heap = []
arr = set() # 지나간 끝점들을 저장해둘 배열
for i in range(n):
l,h,r = map(int,sys.stdin.readline().split())
buildings.append([l,i,1]) # 시작점이라면 좌표와 index, 1을 저장
buildings.append([r,i,0]) # 끝점이라면 좌표와 index, 0을 저장
heights[i] = h # index로 높이 저장
ends[i] = r # index로 끝점 저장
#빌딩들을 정렬한다. 먼저 시작하는 순서대로, 그 다음은 시작점이 먼저 오도록, 그다음은 높이가 높은 순서대로.
buildings.sort(key=lambda x: (x[0], -x[2], -heights[x[1]]))
h = 0 # 최고높이 저장 변수
ans = [] # 정답을 담아둘 배열
# 여기 범위를 n으로 하면 안되는 이유 : 시작점 끝점 나눴으니 n의 2배가 buildings의 길이
for i in range(len(buildings)):
point, index, flag = buildings[i] # 각각 좌표, index, 시작점인지 끝점인지 나타내는 flag
if flag == 1: # 시작점이라면?
if h < heights[index]: # 현재 최고 높이보다 크다면?
h = heights[index] # 새롭게 업데이트
ans.append((point,h)) # 스카이라인이 변경되었으니 정답 배열에 추가
heappush(heap,(-heights[index],ends[index])) # heap에 높이와 끝점을 추가한다. 최대heap을 위해 음수로 저장
else: # 끝점이라면?
arr.add(point) # 끝점을 만났으니 이 좌표는 담아둔다.
while heap: # heap이 비어 있지 않다면 반복한다.
if heap[0][1] not in arr: # 최대높이 빌딩의 끝점이 set에 없다면? => 아직 끝점을 만나지 않은 빌딩이라면?
break # 검사를 멈춘다.
heappop(heap) # set에 있다면 이미 끝난 빌딩이므로 제거한다.
if not heap: # 현재 스카이라인을 그릴 빌딩이 없다면?
if h:
h = 0 # 현재 높이 0으로 업데이트
ans.append((point, h)) # 업데이트되었으니 정답 배열에 추가
else: # 스카이라인을 그릴 빌딩이 있다면?
if -heap[0][0] != h: # 기존의 최고높이 빌딩이 아니라면
h = -heap[0][0] # 새로운 최고 높이 업데이트
ans.append((point, h)) # 정답 배열에 추가
for i in ans:
print(i[0], i[1], end=' ') # 업데이트 될때마다 정답배열에 추가했으니 각각 출력한다.
