99클럽 3기 1일차!

40일간의 99클럽 2기 여정이 끝나고 몇주간 폐관수련...을 하고 나니 어느덧 3기 시작일이 다가왔다. 그동안 얼마나 성장했는지도 궁금하고, 3기를 거치고 앞으로 얼마나 성장할지도 기대된다. 파이팅! 😊

비기너, 미들러, 챌린저 문제 모두 작성해놓았으니 참고해주세요!

Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다 😮😊

---

[Beginner] 자연수 뒤집어 배열로 만들기

[자연수 뒤집어 배열로 만들기]

• 먼저, 각 자리 자연수를 다루는 방법에 대해 생각해 보자.
  • String으로 형변환 후 뒤집고, 한 자리씩 나눈 다음 다시 형 변환
  • Integer 그대로 다루기
    • n%10 으로 마지막 자리를 추출하고, n//=10 으로 그 다음 자리를 추출하는 방식 반복

Solution 1.

return [*map(int, str(n)[::-1])]

• 또다른 뒤집는 방법으로는 reversed(str(n)) 을 이용할 수 있다.

Solution 2.

answer = []

while n:
	answer.append(n%10)
	n //= 10

return answer

---

[Middler] n^2 배열 자르기

[n^2 배열 자르기]

Solution 1) BFS $O(n^2)$ + Flatten $O(n^2)$ + Slicing $O(k)$ → TLE

• Description의 gif를 보자마자 BFS가 떠올랐다. 다 짜고 나서 뒤늦게 제한 사항을 보게 됐는데, $1 \le n \le 10^7$ 이기 때문에 BFS는 무조건 시간 초과가 난다.

def solution(n, left, right):
    arr = [[0]*n for _ in range(n)]

    delta = ((1, 0), (1, 1), (0, 1))
    prev = [(0, 0)]
    f = 1
    arr[0][0] = 1
    
    while prev:
        f += 1
        cur = []
        for y, x in prev:
            for dy, dx in delta:
                ny = y+dy
                nx = x+dx

                if 0<=ny<n and 0<=nx<n and not arr[ny][nx]:
                    arr[ny][nx] = f
                    cur.append((ny, nx))
        prev = cur

    return [e for row in arr for e in row][left:right+1]

Time Complexity : $O(n^2)$

• BFS : $O(n^2)$
• Flatten : $O(n^2)$
• Slicing : $O(k)$

---

Solution 2) 일반항 구해서 한 번에 초기화 $O(n^2)$ + Slicing $O(k)$ → TLE

• 특별한 알고리즘적 테크닉을 사용하는 것보다, 숫자가 채워지는 특정 패턴을 찾아서 한 번에 초기화하는 것이 필요해 보였다.

• 결론부터 말하면 이 방법도 배열의 값을 전부 계산해놓고 Slicing하는 것이기 때문에 $O(n^2)$으로 시간 초과가 난다.

• $n=3$인 경우에 대해 생각해 보자.

  • $1$은 첫 번째 줄의 첫 번째 칸에만,
  • $2$는 첫 번째 줄의 두 번째 자리, 두 번째 줄의 두 번째 칸까지
  • $3$은 첫 번째 줄의 세 번째 자리, 두 번째 줄의 세 번째 칸, 세 번째 줄의 세 번째 칸까지

• 이를 일반화시켜보면 다음과 같다.

  • ~번째 줄에 해당하는 행 인덱스를 $i$라 하고, ~번째 칸에 해당하는 열 인덱스를 $j$라 하자.
  • 자리에 채워지는 숫자는 $i$와 $j$ 중 큰 값에 영향을 받는다.

    	1번째 칸	2번째 칸	3번째 칸
    1번째 줄	max(1, 1)	max(1, 2)	max(1, 3)
    2번쨰 줄	max(2, 1)	max(2, 2)	max(2, 3)
    3번째 줄	max(3, 1)	max(3, 2)	max(3, 3)

  • $A_{i \cdot j} = \max(i, j)+1$

def solution(n, left, right):
	return [max(i, j)+1 for i in range(n) for j in range(n)][left:right+1]

Time Complexity : $O(n^2)$

• arr : $O(n^2)$
• Slicing : $O(k)$

---

Solution 3) 필요한 부분만 계산 $O(k)$ → AC

• BFS를 이용하는 방법에 비해 일반항을 구해서 한 번에 초기화하는 방식은 약 두 배 이상 빠르게 동작했으나, $O(n^2)$로 여전히 시간 초과를 피할 수는 없었다.

• 위 코드에서 더 소요 시간을 줄일 부분을 생각해 보면,

  • 전체 배열을 만든 다음 Slicing하는 것이 아니라, 처음부터 필요한 부분(Slicing할 부분)에 대해서만 계산하는 방법을 떠올릴 수 있다.
  • 그렇다면 Solution 2)의 $i$, $j$를 어떻게 대체할 것인가?
    • $k = i \times j$를 전체 배열에서의 요소의 개수라 하자.
    • $n \times n$ 크기의 배열에서 행 인덱스는 $k$를 행의 수($n$)로 나눈 몫이고, 열 인덱스는 $k$를 열의 수($n$)로 나눈 몫이다.

def solution(n, left, right):    
    return [max(i//n, i%n)+1 for i in range(left, right+1)]

Time Complexity : $O(k)$

• Slicing : $O(k)$

---

[Challenger] 뒤에 있는 큰 수 찾기

[뒤에 있는 큰 수 찾기]

Monotone Stack을 이용하여 $O(n)$에 풀 수 있는 오큰수 NGE(Next Greater Element) 문제이다.

Solution 1) 완전탐색 $O(n^2)$

n = len(numbers)
answer = [-1]*n

for i in range(n):
	for j in range(i+1, n):
		if numbers[i] < numbers[j]:
			answer[i] = numbers[j]
			break

return answer

---

Solution 2) Monotone Stack $O(n)$

def solution(numbers):
	n = len(numbers)
	answer = [-1]*n
	stack = []
	
	for i in range(n):
		while stack and numbers[stack[-1]] < numbers[i]:
			answer[stack.pop()] = numbers[i]
		stack.append(i)

	return answer

• 먼저, 뒤에 있는 큰 수를 찾은 결과를 저장하는 리스트 answer 를 -1로 초기화하자. (∵ Description - 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.)
• 빈 스택을 만든다. 여기에는 number의 값이 담기는 게 아니라, index들이 담긴다.
• numbers의 각 항목에 대해 순회한다.
  • 스택에 값이 존재하고,
  • 스택의 top이 가리키는 numbers의 값이 현재 값(numbers[i]) 보다 작다는 것 ⇒ 스택의 top이 가리키는 numbers의 뒤에 있는 큰 수는 현재 값(numbers[i])라는 것 ∴ pop하고 answer를 갱신해 주면 된다.
    
• 다음 항목에 대해서도 같은식으로 뒤에 있는 큰 수를 찾기 위해 스택에 index를 push한다.

Problems

• [BOJ 17298. 오큰수]
• [BOJ 2493. 탑]
• [BOJ 6198. 옥상 정원 꾸미기]
• [BOJ 6549. 히스토그램에서 가장 큰 직사각형]
• [BOJ 3015. 오아시스 재결합]