반응형 투포인터6 BOJ 11728 - 배열 합치기 / C++ 문제 링크 : https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 풀이 주어지는 두 배열은 이미 정렬되어 있는 상태이므로 각 배열의 0번째 인덱스부터 비교하여 순서대로 출력하면 된다. 한 포인터라도 크기를 벗어나면 while문이 종료되므로 나머지 포인터도 증가시키며 값들을 출력하면 된다. 코드 #include #include using namespace std; int main() { ios_base::sync_.. 2022. 6. 14. 프로그래머스 - 보석 쇼핑 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 풀이 모든 종류의 보석을 담아야하므로 모든 종류의 보석을 알아야한다. 따라서, set을 통해 보석을 모두 담으면 중복이 제거되어 모든 보석 종류가 들어가있다. 다음은 투 포인터 알고리즘을 이용하여 start pointer부터 end pointer까지의 보석이 모든 보석 종류를 담고있는지 확인해야한다. 이를 위해 보석의 이름을 key값으로 가지고 개수를 value값으로 가지는 unordered_ma.. 2022. 4. 24. BOJ 2003 - 수들의 합 2 / C++ 문제 링크 : https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제 풀이 투 포인터 알고리즘을 사용한다. 두 포인터는 모두 인덱스 0에서 시작한다. 목표는 m을 만드는 것이므로 합이 m보다 작다면 끝 포인터(en)을 늘려나가며 sum에 더해나간다. 만약 합이 m보다 크다면 앞 포인터(st)의 수를 뺀다. 이 때, 앞 포인터가 끝 포인터보다 커진다면 그 지점에 두 포인터를 위치시키고 다시 더해나간다. 만약.. 2022. 2. 21. BOJ 2559 - 수열 / C++ 문제 링크 : https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 풀이 처음 생각한 방식은 포인터 2개를 이용해서 0 ~ k / 1 ~ k+1 / 2 ~ k+2 ..를 모두 더해서 최댓값을 구하려고 했다. 하지만 시간초과가 났고 포인터 2개를 더 효율적으로 쓸 수 있는 방식을 찾아보았다. 먼저 0 ~ k 를 더한 뒤 0번째 인덱스의 수를 빼고 k+1번째 인덱스의 수를 더하는 방식으로 풀면 시간초과가 나지 않는다. 소스 코드 시간 .. 2022. 2. 20. 이전 1 2 다음 반응형