문제 https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 특정 구간에 모든 종류의 보석들이 포함되어 있는가를 묻는 문제이다. 보석들의 진열은 중복된 보석들이 존재할 수 있기 때문에 종류를 파악하기 위해 HashSet을 사용하였다. 또한 구간 내에 존재하는 각 보석의 종류와 그 갯수를 확인하기 위해 HashMap을 사용하였다. 투 포인터를 활용하는 곳은 HashMap의 size 즉 현재 구매한 보석의 종류들이 HashSet의 크기, 즉 진..

문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 접근 두 수의 합이 0에 가장 가까워야 한다. 하지만 데이터가 음수와 양수로 나뉘어져 있기 때문에, 두 수의 합의 절댓값을 가지고 판단해야 한다. 데이터 값이 중구난방으로 되어있어 바로 처리하기가 곤란하다. 정렬을 해서 음수 파트와 양수 파트를 나누고 양 끝에서 두 개의 포인터를 사용하여 투 포인터 전략을 사용해야 한다. 두 수의 합의 절댓값을 계산한 ..

문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 접근 앞서 해보았던 투 포인터 유형의 대표적인 문제인 부분합 / 구간 찾기 문제이다. 문제를 상세히 읽어보면 부분합이 S이상이 되면 되므로 $S_{cur} \geq S_{target}$ 를 만족하게 되면 left를 하나씩 올리면서 위 구간합이 만족하는지를 검사하며 구간을 줄여나가면 된다. 만약 $S_{cur} < S_{target}$ 라면 right를 움직여서 다음 요소를..

투 포인터(Two Pointers) 투 포인터는 이름 그대로 두 개의 포인터를 사용하여 배열에서 원하는 결과를 얻는 방법이다. 다중 반복문이 사용되어야 하는 경우에서 해당 방법론을 사용할 수 있다면 좀 더 효율적으로 문제를 풀 수 있다. 포인터의 배치 위치는 일반적으로 아래와 같다. 동일한 방향에서 시작하는 경우, 첫 번째 원소에 둘 다 배치 서로 다른 방향에서 시작하는 경우, 첫 번째 원소와 마지막 원소에 배치 투 포인터의 활용 투 포인터는 배열에서 여러번의 다중 반복문이 사용되어야 할 경우에 효율적이다. 예시로는 구간합 찾기 문제가 있다. 아래와 같은 배열에서 구간합이 9인 구간을 찾아주세요 1 2 5 3 7 2 4 3 2 해당 문제를 나이브하게 다중 루프를 사용할 경우 시작 구간 i와 구간합을 계산..