문제 2141번: 우체국 첫째 줄에 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 X[1] A[1], X[2] A[2], …, X[N] A[N]이 주어진다. 범위는 |X[i]|≤1,000,000,000, 0≤A[i]≤1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 문제 풀이 처음 문제를 접하였을 때는 나라에서 각 사람들까지의 거리의 합이 최소가 되는 위치의 의미를 이해하지 못했다. 코드를 작성하는 시간보다 문제에서 의미하는 바를 생각하는 데까지 걸리는 시간이 더 소요된 것 같다. 즉 문제를 풀기 위해서는 중간 값을 계산하고, 각 마을의 번호 순서대로 정렬한다. 정렬된 마을을 기준으로 하나씩 인구수를 계산하여 중간값과 가장 근접한 마을을 찾아 출력하면 된다. ..
백준: 11000 강의실 배정
문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 풀이 위의 그림과 같이 예제 입력 1의 경우, 최소로 필요한 강의실 개수가 2개임을 알 수 있다. 이를 계산하는 방법은 어렵게 생각할 필요 없이, 강의 시작 시간에 필요한 강의실 수를 증가시키고, 강의가 끝나면 필요한 강의실 수를 감소시킨다. 이때, 강의실 수의 최대 값을 구하면 필요한 최소 강의실 수를 구할 수 있다. 문제를 풀기 위해서 주의할 점이라면, 입력되는 강의 시작 끝 시간에 시작인 경우는 +1, 끝인 경우는 -1과 같이 짝을 지어 따로 구성한다. 그 후, 정렬을 할 때 2가지 기준으로 정..
문제 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 문제 풀이 문제를 풀기 위해서는, 괄호가 제거 가능한 경우 모두를 체크하여야 함을 알 수 있다. 따라서, 올바른 괄호를 이루는 경우를 판단하고 이에 따라 `DFS`를 통해 가지를 뻗어나가야 한다. `DFS`에서 어떤 경우가 올바른 괄호인지 알 수 없으므로, 미리 체크를 한다. 이는 `stack`을 사용하며, 올바른 괄호를 판단하는 로직에서, 어떤 경우 인지 기록하는 경우만 추가하면 된다. `DFS`를 통해 다음과 같은 경우를..
문제 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 문제 풀이 올바른 괄호인지 판단하면서, `()`인 경우에는 2로 치환하고 `[]`인 경우에는 3으로 치환하여 계산하는 과정이 필요하다. 또한 치환된 값이 `()` 또는 `[]` 사이에 있다면 2나 3이 곱해지게 된다. 처음에는 해당 과정을 하나로 처리하려고 했는데, 코드 읽기가 힘들어 따로 판단하는 것이 좋다고 생각했다. 입력으로 주어진 괄호들이 올바른 괄호인지 판단한다. 올바른 괄호는 프로그래머스: 올바른 괄호와 같이 작성하면 판단할 수 있다. 각 괄호..
문제 2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net 문제 풀이 각 풍선에 다음 순번 풍선으로 가기 위한 값들이 적혀있다. 해당 값을 기준으로 음수이면 좌측, 양수이면 우측으로 다음에 터트릴 풍선을 선택한다. 터트린 순서대로 풍선의 번호(Index)를 기록한 후, 정답으로 반환하는 문제이다. 문제를 풀기 위해 아래와 같이 접근하였다. 모듈러 연산을 통해, 터트리고자 하는 풍선을 바로 찾을 수 있을 것이다. 하지만, 입력된 풍선들 전체를 left, right shift 하는 방식을 통해 답을 찾고자 했다. Python의 경우, list는 s..
문제 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 풀이 좌측에 있는 탑이, 우측의 탑 보다 높이가 높은 경우에 신호를 수신할 수 있다. 이를 구현하기 위해 처음에는 입력을 리스트로 받고 뒤집어서 생각해야 할까 고민했다. 하지만, 각 탑의 인덱스, 높이를 `stack`으로 처리하면 위 문제를 간단히 해결할 수 있다. `stack`에 탑을 순서대로 삽입한다. pop을 하게 되면, 현재 탑을 기준으로 바로 좌측의 탑부터 비교를 시작 할 수 있다. 현재 타워와 비교하여 `stack`안의 타워들(좌측의 타워..
문제 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 풀이 프린터를 하기 위한 문서 대기열에 문서들이 있다. 이때, 각 문서들은 `우선순위`를 가진다. 큐(문서 대기열)에서 문서를 인쇄하고자 할 때 큐에 있는 문서들 중 우선수위가 하나라도 높은 것이 있다면, 프린트하지 않고 큐의 맨 뒤로 보낸다. 이는 앞서 다룬 프로그래머스: 프린터와 유사한 문제이다. 문제를 풀기 위해서 다음과 같이 접근하였다. 최초의 문서가 위치한 인덱스를 알기 위해 `enumerate`를 활용한다. `deque`를 활용하여, 인쇄 가능..
