문제를 좀 더 쉽게 설명하자면 길이가 N개인 수열이 있는데 여기서 두 개를 뽑아 서로 곱한 값을 모든 경우의 수에서 다 더한 뒤 1000000007로 나눈 값을 출력하라는 뜻이다.
즉, 수학의 조합(Combination)을 떠올리면 된다.
하지만 제한 조건을 잘 봐야한다.
수열의 길이는 최대 500000(50만)이 될 수 있으며 평소 조합을 구하는 방식대로 첫 번째 원소부터 완전 탐색, 두 번째 원소부터 완전 탐색 ... 이렇게 반복하면 O(n^2)의 시간 복잡도가 걸리므로 시간 초과가 날 수밖에 없다.
따라서 어떻게 해야되나 고민을 해본 결과 예제에서 힌트를 얻을 수 있었다.
예제는 '1 x 2 + 2 x 3 + 1 x 3 = 11' 이렇게 있었다.
이걸 원래 조합 구하는 방식으로 순서를 조금 바꿔보면 '1 x 2 + 1 x 3 +2 x 3 = 11' 이렇게 나타낼 수 있고 조금만 더 이해하기 쉽게 바꾸면 '1 x (2 + 3) +2 x 3= 11' 이렇게 나타낼 수 있다.
즉 문제가 원하는 답은 각 원소와 해당 원소의 뒷 원소들의 합을 곱하고이를 다 더한 값에 1000000007로 나눈 결과를 원하는 것이었다.
이렇게 하면 처음 수열의 합을 구할때 O(n), 수열 탐색할 때 O(n), 총 O(n)의 시간 복잡도가 걸리므로 시간 초과가 나지 않을 것이다.
다음은 전체 코드다.
n=int(input())
num_list=list(map(int,input().split()))
sum_list=sum(num_list)
res=0
for i in num_list:
sum_list-=i
res=(res+i*sum_list)%1000000007
print(res)
원리만 떠올린다면 구현 자체는 아주 쉬운 문제였다.
3번째 줄에서 sum() 함수는 O(n)의 시간 복잡도가 걸린다.
5번째 줄의 반복문에서는 해당 원소를 리스트의 합에서 빼주고 해당 원소와 리스트의 합을 곱한 값을 결과값(res)에 더하면서 1000000007의 나머지로 갱신하면 끝이다.
이진 탐색 트리(Binary Search Tree)를 기반으로 최대 힙은 항상 루트 노드가 가장 큰 원소임을, 최소 힙은 항상 루트 노드가 가장 작은 원소임을 보장하는 자료구조가 힙이다.
여기서 중요한 점은 항상 루트 노드를 보장한다는 점이다.
즉, 루트 노드를 제외한 나머지 노드는 정렬되어 있지 않기 때문에 리스트의 정렬이 필요한 상황이 아닌, 최솟값 혹은 최댓값이 필요한 상황에서 사용 가능하다.
물론 삽입과 삭제가 발생해도 갱신을 통해 항상 루트 노드는 특성을 유지하며 갱신 과정에서 범위를 절반씩 줄이기 때문에 O(logn)의 아주 효율적인 시간 복잡도가 걸린다.
만약 N개의 Data가 있는 리스트에서 최댓값 혹은 최솟값을 매번 찾아야 한다면 O(n)의 시간 복잡도가 걸리는 선형 탐색보다 힙을 사용하는 게 훨씬 효율적이다.
예시는 그림을 통해 최대 힙으로 설명할 것이며 최소 힙도 같은 원리로 작동한다.
최대 힙의 삽입 연산
먼저 최대 힙의 삽입 연산이다.
가장 끝 부분에 원소를 넣는다.
그리고 힙의 특성을 유지하기 위한 갱신 과정을 거치는데 이 과정을 Heapify라고 한다.
따라서 최대 힙이기에 삽입된 6과 부모 노드인 5를 비교해봤을 때 부모 노드가 더 작으므로 서로 교환해준다.
그다음 교환한 부모 노드로 가서 다시 해당 노드와 부모 노드를 비교해주는데 여기선 부모 노드가 더 크므로 힙의 특성을 지키고 있기 때문에 갱신 과정은 종료된다.
최대 힙의 삭제 연산
다음은 최대 힙의 삭제 연산이다.
삭제는 항상 루트 노드를 제거함으로써 최댓값의 반환을 보장하고 마지막 원소를 루트 노드로 가져온다.
여기부터 힙의 특성을 유지하기 위한 Heapify가 진행되는데 자식 노드와 비교해서 자신보다 큰 원소가 있다면 교환을 하고 해당 자식 노드로 넘어간다.
이때 자식 노드가 하나만 있다면 그 하나와 비교를 하고 두 개가 있다면 그중 아무거나 자신보다 큰 원소와 교환을 한다.
물론 둘 다 교환할 필요가 없다면 갱신 과정은 종료되지만 해당 그림에선 6과 7 둘 다 현재 노드보다 크므로 왼쪽 노드인 7과 교환을 한 후 왼쪽 노드로 내려가겠다.
왼쪽으로 내려간 현재 노드와 자식 노드들을 비교했을 때 오른쪽 자식인 6이 더 크므로 오른쪽 자식과 교환을 한 후 내려갔지만 더 이상 자식 노드가 없으므로 여기서 갱신 과정은 종료된다.
갱신 과정을 보다 보면 알겠지만 항상 부모 노드와 자식 노드와의 관계에서 힙 특성을 유지하게끔 변경하는 과정이 일어나는 것을 알 수 있다.
이를 통해 갱신 과정은 범위가 절반씩 줄어드므로 O(logn)의 시간 복잡도가 걸리는 것을 알 수 있고 이진 탐색 트리(Binary Search Tree)와는 다르게 형제 노드끼리의 크기 차이는 신경 쓸 필요가 없다는 것도 확인할 수 있다.
구현
물론 이 힙의 삽입, 삭제 과정을 구현하는 것은 어렵진 않지만 고려할 요소들과 실수 가능성을 생각하면 시간제한이 있는 코딩 테스트에서 직접 구현하는 것은 상당히 비효율적이다.
다행히 다양한 이름으로 라이브러리가 있는데 파이썬에서는 heapq라는 모듈을 사용하면 된다.
따라서 해당 포스팅에서는 heapq의 사용방법을 익히도록 하겠다.
import heapq
data_list=[]
input_data=[5,9,3,1]
print("최소 힙 초기 원소 :",data_list)
for i in input_data:
print(i,"추가")
heapq.heappush(data_list,i)
print(data_list)
print("\n최소 힙 루트 노드의 원소 :",data_list[0],end="\n\n")
for i in range(len(input_data)):
print(heapq.heappop(data_list),"삭제")
print(data_list)
print("\n기존 input 리스트 :",input_data)
heapq.heapify(input_data)
print("Heapify 후 input 리스트 :",input_data)
print("\n최대 힙 초기 원소 :",data_list)
for i in input_data:
print(i,"추가")
heapq.heappush(data_list,(-i,i))
print(data_list)
print("\n최대 힙 루트 노드의 원소 :",data_list[0][1],end="\n\n")
for i in range(len(input_data)):
print(heapq.heappop(data_list)[1],"삭제")
print(data_list)
파이썬에서는 힙 구조를 만들 때 새로운 자료구조를 취급하는 게 아니라 기존의 리스트에 heapq란 모듈을 통해 힙의 특성을 가지며 heapq는 크게 3가지 함수가 있다.
원소를 넣는 heappush(), 원소를 삭제하는 heappop(), 리스트를 힙의 형태로 변환하는 heapify()다.
또한 heapq는 기본적으로 최소 힙의 특성을 가진다.
첫 번째 반복문을 통해 input_data의 원소를 하나씩 삽입하면서 최소 힙을 유지하는 것을 알 수 있다.
두 번째 반복문은 heappop()을 통해 루트 노드를 제거하면서도 최소 힙의 특성을 유지하는 것을 알 수 있다.
또한 18번째 줄을 통해 기존의 리스트를 힙의 형태로 변환하는 것도 확인할 수 있다.
3번째 반복문에서는 기본적으로 최소 힙의 특성을 갖는 heapq를 최대 힙으로 활용하기 위해서 튜플로 원소를 삽입한 것을 알 수 있다.
기존의 원소에 -1을 곱하여 음수로 만들고 해당 음수 값과 양수 값을 같이 넣으면 음수 값을 통해 최소 힙으로 정렬된다.
음수 값을 통해 최소 힙으로 정렬이 되므로 같이 들어간 양수 값은 자동적으로 최대 힙으로 정렬이 되는 원리를 이용한 것이고 튜플로 넣었기 때문에 pop() 할 때 인덱스 1로 접근한 것을 30번째 줄에서 확인할 수 있다.
결과 화면
모듈 import도 쉽고 함수도 어렵지 않아서 한 두 번 보면 쉽게 익힐 수 있을 것이다.
먼저 저 숫자가 들어간 동그라미는 노드(Node)라고 하며 노드를 잇는 선은 간선(Edge)라고 한다.
노드는 Data를 뜻하며 간선은 Data끼리의 연결을 뜻한다.
트리에서의 첫 시작 노드는 뿌리라 해서 루트 노드(Root Node)라 한다.
모든 시작은 이 루트 노드에서 이루어지며 연결 리스트(Linked List)를 알고 있다면 더미 노드(Dummy Node)와 같은 역할이다. (물론 루트 노드는 Data를 갖고 있다는 점이 다르긴 하다.)
연결된 노드를 기준으로 상위에 있는 노드는 부모 노드(Parent Node), 하위에 있는 노드는 자식 노드(Child Node)라 한다.
즉, 루트 노드는 부모 노드가 없고 대부분의 노드는 서로 부모 노드, 자식 노드가 될 수 있으며 제일 끝단의 자식 노드가 없는 노드들은 단말 노드(Leaf Node, 리프 노드)라 한다.
그림에서도 알 수 있듯이 루트 노드를 제외한 모든 노드들은 단 하나의 부모 노드만 가질 수 있고 이 때문에 Cycle이 생기지 않으면서 모든 노드가 연결된다.
또한 하나의 노드에서 자식 노드로 뻗어나가는 간선의 수를 차수(Degree)라고 한다.
각 노드마다 차수는 다를 수 있으며 최대 차수는 하나의 노드가 가지는 최대 간선의 수를 뜻한다.
따라서 해당 그림에서는 루트 노드가 3개의 간선을 가지므로 이 트리는 Degree가 3인 트리라고 할 수 있다.
깊이는 루트 노드에서 해당 노드까지 도달하는데 경유한 간선의 개수를 뜻한다.
또한 Level은 깊이가 동일한 노드들의 집합이다.
Level이 같은 노드들을 형제 노드(Sibling Node)라고 하며 루트 노드의 Level을 정의하는데 다소 차이가 있는 것 같다.
어떤 자료에서는 Level 0부터 시작하고 어떤 자료에서는 Level 1부터 시작하는데 깊이가 기준이 되기 때문에 큰 차이는 없을 것 같다.
다만 Level 1부터 시작한다면 각 노드는 Depth+1=Level이기 때문에 보다 쉬운 이해를 위해 Level 0부터 시작하여 Depth=Level로 맞춰서 글을 작성하였다.
루트 노드를 제외하고 나머지 노드들을 루트 노드로 생각한다면 기존의 트리에서 일부분을 트리로 생각할 수 있다.
이것을 서브 트리(Sub Tree)라고 하며 보통 이진 트리(Binary Tree)에서 왼쪽 서브 트리(Left Sub Tree), 오른쪽 서브 트리(Right Sub Tree)로 구분 짓는다.
보통 알고리즘 문제나 필기 문제로 이진 트리가 나오므로 이진 트리에 대해 설명하겠다.
이진 트리 (Binary Tree)
트리에 대해서 이해가 잘 됐다면 이진 트리는 별거 없다.
이름에서도 알 수 있듯이 트리에서 최대 차수가 2인 트리를 이진 트리라고 하기 때문이다.
물론 이진 트리도 형태에 따라 3가지로 분류한다.
편향 이진 트리, 완전 이진 트리, 포화 이진 트리
편향 트리(Skewed Binary Tree)는 모든 노드가 왼쪽 혹은 오른쪽 자식만 갖고 있는 형태이다.
완전 이진 트리(CompleteBinary Tree)는 마지막 Level을 제외한 모든 Level의 노드가 완전히 채워져 있으며 마지막 Level의 노드들은 왼쪽부터 채워져 있는 형태이다.
포화 이진 트리(Full Binary Tree)는 완전 이진 트리에서 마지막 Level의 노드들도 채워져 있는, 즉 이진 트리가 보유할 수 있는 최대 노드를 가진 형태가 포화 이진 트리다.
이진 트리 순회 (Binary Tree Traversal)
이진 트리의 순회는 총 4가지가 있다.
전위 순회 (Pre-order)
중위 순회 (In-order)
후위 순회 (Post-order)
레벨 순회 (Level-order)
1번부터 3번까지는 왼쪽 서브 트리, 현재 노드, 오른쪽 서브 트리 중에 현재 노드를 언제 탐색하느냐에 따라 이름이 바뀌는 방식이고 레벨 순회는 루트 노드부터 같은 레벨인 노드를 차례로 탐색하는 방식이므로 너비 우선 순회(Breadth-first Traversal)라고도 한다.
따라서 전위 순회는 현재 -> 왼쪽 -> 오른쪽, 중위 순회는 왼쪽 -> 현재 -> 오른쪽, 후위 순회는 왼쪽 -> 오른쪽 -> 현재 순서로 방문하는 방식으로 단순하게 어느 지점에서 현재 노드를 출력하느냐의 차이일 뿐이다.
또한 레벨 순회는 그래프 탐색의 BFS(Breadth First Search)와 같이 큐를 사용하는 방법이므로 굳이 다루진 않겠다.
이진 트리
오른쪽과 같은 이진 트리를 예시로 들어보자.
순회를 하기 전에 조금 더 구체적인 설명을 하자면 루트인 3인 노드를 기준으로 왼쪽으로 내려가면 현재 노드가 1인 서브 트리, 오른쪽으로 내려가면 현재 노드가 5인 서브 트리로 생각할 수 있다.
각 서브 트리에서 다시 서브 트리로 내려갈 수 있는 구조이다.
즉, 전위 순회는 3->1->0->2->5->4->6, 중위 순회는 0->1->2->3->4->5->6, 후위 순회는 0->2->1->4->6->5->3 순으로 탐색하게 된다.
순회 구현
트리를 구현하는 방법은 다양하지만 자세한 건 이진 탐색 트리 포스팅에서 다루도록 하겠다.
이번 포스팅에서는 딕셔너리를 이용하여 구현했다.
딕셔너리의 키(Key)는 현재 노드의 값을 뜻하고 값(Value)은 길이가 2인 리스트로 선언하여 0번째 인덱스는 왼쪽 자식의 값, 1번째 인덱스는 오른쪽 자식의 값을 뜻한다.
이때 자식 노드가 없는 것을 표현하기 위해 '*'로 선언하여 숫자가 존재할 때만 해당 자식 노드로 이동하도록 구현하면 된다.
전체 코드를 통해 설명하겠다.
def preorder(root):
print(root,end=" ") #현재 노드 출력
if binary_tree[root][0]!="*": #왼쪽 자식 노드가 존재하면 이동
preorder(binary_tree[root][0])
if binary_tree[root][1]!="*": #오른쪽 자식 노드가 존재하면 이동
preorder(binary_tree[root][1])
def inorder(root):
if binary_tree[root][0]!="*":
inorder(binary_tree[root][0])
print(root,end=" ")
if binary_tree[root][1]!="*":
inorder(binary_tree[root][1])
def postorder(root):
if binary_tree[root][0]!="*":
postorder(binary_tree[root][0])
if binary_tree[root][1]!="*":
postorder(binary_tree[root][1])
print(root,end=" ")
root=3
binary_tree={3:[1,5],1:[0,2],0:['*','*'],2:['*','*'],5:[4,6],4:['*','*'],6:['*','*']}
print("전위 순회시작")
preorder(root)
print("\n\n중위 순회시작")
inorder(root)
print("\n\n전위 순회시작")
postorder(root)
구성을 보면 상당히 간단하단 것을 알 수 있다.
단순히 현재 노드의 값을 출력하는 부분이 어디에 위치하느냐에 따라 구분된다는 것을 알 수 있다.
따라서 한 가지를 이해하면 다른 것도 쉽기 때문에 Preorder로 설명하겠다.
시작은 루트부터 출발하여 각 함수의 매개변수로 넘겨준다.
해당 노드를 출력하고 만약 해당 노드의 왼쪽 자식 노드가 존재한다면 왼쪽 자식 노드의 값을 매개변수로 넘기고 재귀 호출한다.
그다음 오른쪽 자식 노드가 존재한다면 오른쪽 자식 노드의 값을 매개변수로 넘기고 재귀 호출한다면 알아서 반복하게 된다.
순회의 결과
여기까지가 이진 트리에 대한 이론이지만 이를 실제 적용하기엔 다소 제한이 있다.
이진 트리를 직접 구현하여 사용하는 것은 이진 탐색 트리(Binary Search Tree)라고 하며 삽입과 삭제에 여러 가지 조건이 붙기 때문이다.
또한 트리도 사람마다 편한 방식이 다르기 때문에 다양한 구현 방법과 이진 탐색 트리의 작동 방식을 다음 포스팅에서 학습하도록 하겠다.
지문에서 N번째 숫자를 묻고 N은 1,000,000(백만) 이하의 자연수 혹은 0이므로 상당히 큰 숫자들을 비교해야 할 것 같지만 정작 주의해야 할 조건은 딱 하나다.
앞 자릿수부터 뒤로 갈수록숫자가 작아져야 한다.
예시에 나온 322처럼 같은 숫자가 연속해서 등장해도 감소하는 수가 아니므로 생각 가능한 최대 숫자는 9876543210이다.
물론 이 숫자 또한 90억이 넘는 숫자이므로 0부터 9876543210까지 차례대로(선형적으로) 감소하는 숫자인지 판단하려면 엄청난 연산 횟수가 나올 수밖에 없다.
하지만 이 숫자들을 자릿수를 기준으로 비교한다면 얘기가 달라진다.
즉, 1자리 수부터 10자리 수까지 앞자리보다 작은 숫자들만 이어 붙여준다면 불필요한 연산을 획기적으로 줄일 수 있다.
이 과정에서 백 트래킹을 재귀로 구현하며 무한 루프에 빠지지 않도록 탈출 조건을 잊지 않도록 한다.
아이디어만 떠올린다면 구현 자체는 어렵지 않은 문제이므로 전체 코드를 보면서 설명하겠다.
def add_digit(digit,num): #자리수에 따라 증가
if digit==1:
decreasing.append(num)
else:
for i in range(num%10):
add_digit(digit-1,num*10+i)
def backtracking(digit): #백트래킹 시작
for i in range(digit-1,10):
add_digit(digit,i)
decreasing=[] #감소하는 숫자 리스트
for i in range(1,11):
backtracking(i)
n=int(input())
if n>=len(decreasing): #감소하는 숫자가 없을 때
print(-1)
else:
print(decreasing[n])
크게 구성을 함수 두 개, 메인으로 나누었다.
물론 메인에서 중첩 for문을 통해 1자리 수부터 10자리 수까지 가능한 숫자들을 매개변수로 보낸다면 하나의 함수만 써도 되지만 직관적인 이해를 돕기 위해 기능을 분리하여 함수 두 개로 구현하였다.
첫 번째 함수 add_digit은 특정 자릿수까지 감소하는 숫자를 이어 붙이는 함수고 두 번째 함수 backtracking은 1 자릿수부터 10 자릿수까지 백 트래킹을 반복하는 함수다.
함수의 특성상 먼저 선언되어있어야 호출 가능하므로 조금 복잡하지만 함수의 흐름대로 설명하겠다.
먼저 12번째 줄에 decreasing으로 감소하는 숫자들을 넣을 리스트를 선언했다.
그리고 13번째 줄은 자릿수를 매개변수로 백 트래킹을 시작하기 위한 반복문이고 이해가 쉽도록 1부터 10까지 반복한다.
즉 1 자릿수부터 10자리 수까지 찾겠다는 의미이다.
그럼 8번째 줄인 backtracking 함수로 넘어가는데 이미 받은 digit변수와 같이 0부터 9까지 숫자를 파라미터로 넘긴다.
이 0부터 9는 실제 감소하는 수가 될 숫자들이다.
그렇게 add_digit으로 넘어가면 digit이 1자리일 때는 더 이상 추가할 숫자가 없으므로 decreasing 리스트에 숫자를 넣고 함수가 자동 종료된다.
만약 digit이 2 이상일 땐 뒷자리에 숫자를 추가해야 하므로 반복문을 통해 digit을 감소시킨 후 재귀 호출한다.
이때 추가해야 할 숫자가 바로 앞자리 숫자보다 작아야 하므로 num%10을 통해 바로 앞자리 숫자를 구하고 해당 숫자 미만까지만 반복문을 돌린다.
물론 2자리 수 이상부터는 첫자리에 0이 올 수 없지만 num%10은 0이라 for문을 수행하지 않아서 고려하지 않아도 된다.
또한 뒷자리에 숫자를 이어 붙이므로 원래 숫자인 num에 10을 곱해서 자릿수를 늘린 후 i를 더하면 원하는 숫자가 된다.
위의 재귀가 끝나면 decreasing 리스트에는 0부터 9876543210까지 감소하는 수가 들어가게 되고 N을 입력받아서 리스트의 인덱스를 벗어나면 불가능한 수이므로 -1을 출력, 벗어나지 않으면 해당 인덱스의 숫자를 출력하면 통과한다.
결과 화면
아무래도 이 문제가 골드로 측정된 것은 숫자를 자릿수로 비교하는 생각의 전환, 백 트래킹 적용 때문인 것 같다.
비교적 코드도 짧고 구현도 쉬운 편이기 때문이다.
아마 다양한 문제를 접하다 보면 이 정도 아이디어와 구현은 쉽게 떠올리고 구현할 수 있을 것이다.
prices의 가격들은 매초 변하는 가격을 뜻하고 가격이 떨어지지 않는 기간은 현재 가격보다 더 낮은 가격이 나온 시간까지 매초(가격의 수) 세면 된다는 뜻이다.
그래서 예시에서 \1은 그 뒤에 \1보다 낮은 시간이 없기 때문에 4초(4개의 가격) 동안 가격이 떨어지지 않는 것이고 마지막 \3은 그 뒤에 남아있는 시간이 없기 때문에 0초가 된 것이다.
단지 지문에서 "가격이 떨어지지 않은 기간은 몇 초인지"라고만 있었기에 이를 헷갈려서 질문에 올린 사람들이 많은 것 같다.
어려운 문제가 아니므로 바로 전체 코드로 넘어가겠다.
def solution(prices):
answer = []
for i in range(len(prices)):
cnt=0
for j in range(i+1,len(prices)):
if prices[i]<=prices[j]:
cnt+=1
else:
cnt+=1
break
answer.append(cnt)
return answer
3번째 줄은 prices의 전체 범위를 탐색하겠다는 것을 뜻하고 5번째 줄은 현재 가격보다 떨어지는 시간이 나올 때까지 남은 시간을 반복하여 세는 반복문이다.
만약 현재 가격보다 낮은 시간이 있다면 그 뒤에 가격은 고려할 필요가 없기에 break를 통해 바로 반복문을 탈출하면 된다.
그렇게 카운트한 값을 answer에 추가하면 된다.
결과 화면
다만 의문인 점은 prices의 길이는 100,000(10만) 이하이고 완전 탐색은 O(n^2)의 시간 복잡도가 걸리므로 1초당 5천만~1억 정도 연산이 가능한 Python을 기준으로 최악의 테스트 케이스가 나온다면 시간 초과가 걸릴 수밖에 없다.
하지만 Input이 작은 정확성까진 이해가 됐으나 상당히 큰 Input이 들어오는 효율성까지 통과된 거로 봐서는 최악의 경우까진 Input이 들어오지 않게 설정한 것 같다.
대문자 하나에 대응하는 소문자 문자열이 정해져 있으므로 Python의 딕셔너리를 사용하면 쉽게 해결할 수 있다.
대응하는 문자들을 딕셔너리에 저장하고 압축된 문자열이 들어왔을 때 차례대로 소문자 문자열로 치환하면 쉽게 풀 수 있는 문제다.
바로 전체 코드로 넘어가겠다.
n=int(input())
word={}
res=""
for i in range(n):
temp=list(input().split())
word[temp[1]]=temp[0]
question=input()
for i in question:
res+=word[i]
num=list(map(int,input().split()))
print(res[num[0]-1:num[1]])
2번째 word는 딕셔너리를 선언했고 for문을 돌면서 입력받은 값을 저장하면 된다.
이때 주의해야 할 점은 압축된 문자열을 풀어야 하므로 입력받은 대문자를 딕셔너리의 키, 소문자 문자열 패턴을 딕셔너리의 값으로 저장해야 한다는 것이다.
res에 치환한 문자열을 저장하고 입력받은 인덱스를 기준으로 출력하면 쉽게 풀 수 있다.
인덱스로 범위 출력 시 왼쪽 인덱스는 포함, 오른쪽 인덱스는 미만까지 출력하는 점을 주의해야 한다.
대기목록에서 꺼낸 문서보다 중요도가 높은 문서가 대기목록에 남아있다면 꺼낸 문서를 다시 대기 목록에 넣는다.
대기 목록에는 최대 100개의 문서가 있다.
중요도는 숫자가 클수록 중요하다.
대기 목록인 priorities의 첫 원소를 차례대로 빼면서 나머지 원소 중 최대 중요도를 비교하여 뺀 문서보다 중요도 높은 문서가 있다면 뒤에 추가하는 형식으로 풀면 될 것이다.
이때 최대 100개의 문서밖에 없으므로 O(n)의 시간 복잡도를 가지는 max 함수로 최대 중요도를 비교하면 된다.
동시에 location에 해당하는 문서가 몇 번째에 출력되는지 묻는 문제이므로 원소를 pop 할 때마다 location을 감소시키고 음수가 되면 대기 목록의 마지막에 추가되었다고 생각하면 된다.
간단한 문제이므로 바로 전체 코드로 넘어가겠다.
def solution(priorities, location):
answer = 0
while len(priorities)>0: #대기 목록에 문서가 있는 동안 반복
temp=priorities.pop(0) #첫 번째 문서 꺼내기
if len(priorities)==0: #껴낸 문서가 마지막 일때 종료
answer+=1
else:
if temp>=max(priorities): #꺼낸 문서의 중요도가 제일 높을 때
if location==0: #찾고자 하는 문서일 때 종료
answer+=1
break
else:
location-=1
answer+=1
#꺼낸 문서보다 중요도가 높은 문서가 대기 목록에 존재할 때
else:
priorities.append(temp)
location-=1
if location<0:
location=len(priorities)-1
return answer
3번째 줄은 대기 목록에 문서가 있는 동안 반복하기 위해 while문을 선언하였고 4번째 줄은 pop(0)을 통해 0번째 인덱스의 원소를 제거하며 반환한다.
또한 5번째 줄은 꺼낸 문서가 마지막 문서일 때 (더 이상 대기 목록에 문서가 없을 때) 고려할 조건이 없으므로 answer을 증가시킨 후 바로 종료한다.
8번째 줄의 if문은 max로 대기 목록의 중요도를 비교하여 더 높은 중요도가 없으면 출력하는 문서로 판단하고 location을 감소시킨다.
이때 location이 0이라면 꺼낸 문서가 찾는 문서이므로 answer을 증가시킨 뒤 break를 통해 반복문을 빠져나온다.
17번째 else는 대기 목록에 더 높은 중요도가 있을 때 뒤에 추가하는 구문으로 만약 location이 음수가 되면 대기 목록의 마지막에 추가했다는 의미이므로 현재 priorities 길이의 -1로 변경하면 된다.
결과 화면
이 문제는 Input Size가 상당히 작아서 굳이 시간 복잡도를 계산할 필요까진 없었던 것 같다.
조건만 잘 확인하고 구현한다면 충분히 쉽게 통과할 수 있을 것이다.
이 프린터 문제는 우선순위 큐란 알고리즘이다.
다만 우선순위 큐는 힙(Heap)이란 자료 구조를 사용하고 내부 구조에서 최댓값, 최솟값을 갱신하는데 O(logn)의 효율적인 시간 복잡도를 가진다.
파이썬은 Heapq란 모듈을 통해 쉽게 우선순위 큐를 구현 가능하며 해당 문제에서는 큐를 연습하기 위해 일부러 Input을 적게 주고 우선순위 큐의 결과를 나타낼 수 있도록 유도한 것 같다.
코테에서도 은근히 우선순위 큐를 사용하는 문제가 나오므로 우선순위 큐를 구현하는 힙에 대해서 포스팅하겠다.
문제를 보자마자 떠올린 생각은 day를 하루씩 증가시키면서 progresses 리스트에 speeds 리스트의 원소를 계속 더하고 progresses의 길이가 0이 될 때까지 같은 날에 0번째 인덱스의 원소가 100 이상이면 pop 하면서 카운트하여 answer에 추가하는 방식이었다.
애초에 작업의 개수가 100개 이하고 작업 진도가 1, 작업 속도가 1일 때 최대 99일이므로 Input이 작아 가능성은 있어 보였다.
하지만 Python의 pop함수에서 0번째 인덱스를 제거하는 pop(0)은 O(n)의 시간 복잡도를 가지므로 원소를 제거하는 과정에서 추가적으로 불필요한 연산이 생기기에 상당히 비효율적인 방식이라 다른 방법을 생각해봤다.
그 결과 굳이 매번 원소들을 더하는 게 아니라 day를 증가시키면서 같은 day일 경우를 카운트하여 answer에 추가하고 기존의 리스트에 대한 변경 없이 현재 어떤 인덱스를 가리키는지 알려주는curr_index를 선언한다면 매번 원소를 제거할 때 드는 시간 복잡도도 없어질 것이라 판단하였다.
전체 코드를 통해 설명하면 이해가 더 빠를 것이다.
def solution(progresses, speeds):
answer = []
day=0 #개발 일수
curr_index=0 #현재 작업 Index
#작업 Index를 0번 부터 끝까지 반복
while curr_index<len(progresses):
#현재 작업이 100% 넘을 때까지 day 증가
while progresses[curr_index]+speeds[curr_index]*day<100:
day+=1
#완료된 작업 개수 카운트
cnt=0
#완료된 작업 카운트
while curr_index<len(progresses) and progresses[curr_index]+speeds[curr_index]*day>=100:
cnt+=1
curr_index+=1
answer.append(cnt)
return answer
7번째 줄을 통해 progresses 리스트를 전체 반복하고 10번째 줄을 통해 현재 작업이 100%가 될 때까지 day를 증가시킨다.
day를 찾으면 같은 날일 때 몇 개의 작업을 배포할 수 있는지 세기 위해 14번째 줄에 cnt를 선언하여 0으로 초기화한다.
초기화된 cnt를 기반으로 17번째 줄에서 배포 가능한 작업들을 세며 curr_index를 증가시킨다.
이때 while문에서 curr_index<len(progresses)를 먼저 선언한 이유는 curr_index가 증가할 때 progresses의 리스트 범위를 벗어나 Index Error를 일으킬 수 있기 때문이다.
프로그래밍 언어에서 조건을 판단할 때앞에 있는 조건이 False라면 뒤에 있는 조건을 확인하지 않기 때문에이처럼 Index Error를 방지하는 조건이나 시간 복잡도를 최대한 줄일 수 있는 조건은되도록이면 앞에 쓰는 습관을 들이자.
마지막으로 카운트한 작업 수를 answer에 추가하면 끝이다.
결과 화면
이렇게 구현한 방식은 리스트의 원소를 제거하는 등 불필요한 연산을 줄였기 때문에 day를 증가시키는 연산(최대 99번), progresses 리스트를 탐색하는 연산(최대 100번)을 하면 최대 약 10,000번의 연산을 한다.
엄밀히 말하자면 큐로 푼 게 아니라 리스트의 인덱스 접근을 통해 풀었고 처음에는 상당히 비효율적인 방식을 생각했었다.
항상 문제의 조건을 정확히 파악하여 자신이 생각한 방식의 시간 복잡도를 계산해보고 보다 더 효율적인 방식이 있는지 끊임없이 고민하는 습관이 상당히 중요한 것 같다.
