문제 링크 https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/ 개요 2차원 배열에 대해 각각의 리스트의 합을 기준으로 정렬을 하고 그 순서를 반환하는 문제이다. 파이썬에서는 내장함수 sort()를 사용하면 쉽게 풀 수 있다. 문제 해설 입력으로 2차원 배열 mat과 출력값의 개수를 의미하는 정수 k가 주어진다. mat에 있는 각각의 리스트는 0과 1의 조합으로 이루어져 있으며 1의 개수가 많은 리스트가 강한 리스트이다. 문제에서 요구하는 것은 1. 리스트를 약한 순으로 정렬하고 2. 정렬하기 전의 인덱스 번호를 정렬된 순서대로 반환하는 것이다. 이를 위해 리스트의 인덱스 번호와 리스트의 합을 따로 저장할 필요가 있으므로 for문을 통해 mat을 순회한다....
문제 링크 https://www.acmicpc.net/problem/2805 개요 이분 탐색으로 해결할 수 있는 문제이다. Python3을 사용하면 시간초과가 발생하므로 PyPy3를 사용한다. 문제 조건 일정 높이에 대해 모든 나무를 잘랐을 때, 조건을 만족하는 절단기의 최대 높이(H)를 구하는 문제이다. 잘린 나무의 길이의 합은 상근이가 필요로 하는 나무의 길이(M)보다 크거나 같아야 한다. 문제 해설 나무의 수(N)의 최댓값이 1,000,000이므로 모든 범위에 대해 반복하는 순차 탐색을 이용할 경우 시간초과가 발생한다. 시간 복잡도가 O(log n)인 이분 탐색을 이용하면 시간 복잡도가 O(n)인 순차 탐색을 쓰는 것보다 훨씬 빠르다....
문제 링크 https://www.acmicpc.net/problem/11650 개요 배열 형태의 자료들을 정렬하는 간단한 문제이다. 파이썬에서는 내장 함수 sort()를 사용하면 쉽게 풀 수 있다. 문제 해설 문제에서 요구하는 것은 x좌표 값과 y좌표 값으로 구성된 배열들의 리스트를 x 값, y 값 순으로 정렬하는 것이다. 배열의 자료구조는 인덱싱으로 접근이 가능한 것이면 아무거나 상관없기에 좌표 표현에 직관적인 튜플을 사용한다. 정렬의 기준이 반대였으면 람다 식을 써야겠지만 좌표의 위치가 곧 정렬 순서이기 때문에 Key값은 사용하지 않는다. 해설 코드 1 2 3 4 5 6 7 8 9 10 import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/4949 개요 스택을 이용하여 풀 수 있는 문제이다. 문자열 처리에 관한 능력이 추가로 요구된다. 최대 입력 크기가 정해지지 않았기에 시간 복잡도는 무시한다. 문제 해설 해당 문제에서 고려해야할 문자는 종료 조건인 점(’.’)을 제외하면 소괄호와 대괄호 뿐이다. 균형잡힌 문장의 구분 여부는 1. 닫힌 괄호가 열린 괄호보다 앞에 나온 경우 2. 열린 괄호가 안 닫힌 경우로 판단했다. 문자 하나하나마다 확인하며 괄호를 골라낼 수도 있지만 이번엔 정규식을 사용해본다. 우선 정규식 라이브러리인 re에 속한 sub 메서드를 사용해 괄호를 제외한 모든 문자를 제거한다....
문제 링크 https://www.acmicpc.net/problem/2164 개요 큐를 이용하여 풀 수 있는 간단한 문제이다. 양쪽에서 데이터를 빼고 집어넣는 작업이 요구되기 때문에 deque의 사용을 권장한다. 1번 카드의 위치를 앞으로 하냐 뒤로 하냐는 크게 상관없기 때문에 앞에서부터 정의하겠다. 문제 해설 문제에서 제시된 행동은 1. 제일 위의 카드를 버린다 2. 제일 위에 남은 카드를 제일 아래로 옮긴다 이다. 해당 행동을 카드가 한 장이 남을 때까지 무한히 반복하면 된다. 1번 행동을 하기 위해선 1번 카드를 큐의 맨 앞으로 정했기에 큐의 왼쪽에서 값을 빼내면 된다....