문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 투 포인터 문제입니다. 3개의 용액의 합의 절대값이 0과 가장 가까운 3개의 용액을 찾는 문제입니다. 3개의 용액을 구하기 위해, 기준이 되는 용액을 하나를 고정하고, 두 용액을 투포인터를 통해 포인터를 이동하며, 최적의 합을 찾는 것이 핵심입니다. for문을 통해 모든 용액을 기준으로 합니다. 이 때 for문의 범위를 전범위로 하는 것이 아니라, 두가지 용액이 더..
[문제] https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [풀이] 투 포인터를 이용하면 쉽게 풀 수 있는 문제이다. 문제를 푸는 방법은 아래와 같다. 1. 조건 N의 범위가 (1 ≤ N ≤ 4,000,000) 이므로, (1 ≤ N ≤ 4,000,000) 사이의 소수를 미리 모두 구한다. 2. 연속된 소수의 합이므로, 연속된 소수의 합을 미리 구하여 배열에 저장을 해둔다. 3. 투 포인터를 이용하여, 풀어준다. 1번 과정은 에라토스테네스의 체를 이용하여 해결한다. prime = MutableList(MAX){true} prime[1] = false prime[0] ..
[문제] https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net [해설] 들어가기 앞서 이 문제는 삽질을 강제로하게 만들었다. 입력은 여러 개의 테스트 케이스로 이루어져 있다.
[문제] https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net [풀이] 투 포인터를 통해 풀었다. 입력되는 용액의 순서가 오름차순으로 정렬이 되어져 있는 상태이다. 그렇기 때문에 왼쪽에서 오른쪽 방향, 오른쪽에서 왼쪽으로 값을 찾아나가며, 0에 가까운 용액을 찾는다. 왼쪽을 가리키는 포인터 left, 오른쪽을 가리키는 포인터를 right라고 가정했을 경우에 용액 배열의 left위치와 right위치를 더한 값이 0보다 작다면, left를 1만큼 ..
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [풀이] stack을 이용하여 풀면 편하다. 왼쪽 방향으로 이동하면서 인접한 탑끼리 비교를 한다. 2가지 경우로 나눌 수 있다. 1. i번째 탑이 i-1번째 탑의 높이보다 큰 경우 이러한 경우에는 i 번째에서 레이저 신호를 보내도 i-1에서 받을수가 없다. 따라서 Pair를 이용하여, i번째의 인덱스값과 높이를 stack에 저장을 한다. 2. i번째 탑이 i-1번째 탑의 높이보다 작거나 같은 경..
https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net [풀이] 투 포인터로 풀었다. 풀이 과정은 다음과 같다. 입력 받은 문자열의 각 자리별 인덱스 위치를 저장해두는 배열을 만든다. 예를 들어 abbc라는 문자열을 받는다면, [[0],[1,2],[3]]과 같이 인덱스를 저장하는 배열을 만든다. 문자열을 W라고 표현하고 저장하는 배열을 abcIndex라고 한다면 아래와 같다. var W = br.readLine().toString() var abc..
