투 포인터 알고리즘11 [프로그래머스] 67258번 - 보석 쇼핑 [Java] https://school.programmers.co.kr/learn/courses/30/lessons/67258 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매 예를 들어 아래 진열대는 4종류의 보석(RUBY,.. 2025. 3. 10. [백준] 20922번 - 겹치는 건 싫어 [Java] https://www.acmicpc.net/problem/20922 1. 아이디어 카운팅 배열과 투 포인터 알고리즘을 활용하면 해결할 수 있다.2. 문제풀이 수열의 앞쪽에 left, right 포인터를 설정한 후 right 포인터에 위치한 수가 카운팅 배열에서 K개 미만이면 포함할 수 있고, K개면 포함할 수 없다. 포함할 수 있으면 포함하고 right 포인터를 오른쪽으로 이동, 포함할 수 없으면 left 포인터의 수를 카운팅 배열에서 빼주고 left 포인터를 오른쪽으로 이동하는 과정을 반복하면 됐다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final int MAX = 100_000; public.. 2025. 2. 19. [백준] 2003번 - 수들의 합 2 [Java] https://www.acmicpc.net/problem/2003 1. 아이디어 누적합과 브루트포스 알고리즘을 통한 방법과 투 포인터 알고리즘을 활용한 방법으로 해결할 수 있었다.2. 문제풀이 - 누적합 + 브루트포스 알고리즘주어진 문제가 수열에서 특정 구간의 합이 M이 되는 경우의 수를 구하는 문제이므로 누적합 배열을 미리 만든 후 2중 for문을 활용해 누적합 배열에서 두 원소의 차를 계산하는 방식으로 특정 구간의 합을 간단하게 구할 수 있다. - 투 포인터 알고리즘주어진 수열이 자연수로만 이루어진 수열이어서 두 개의 포인터를 앞쪽에서 출발시켜 두 포인터의 위치를 합을 구할 구간이라 생각하면 합을 줄이기 위해서는 왼쪽 포인터를, 합을 늘리기 위해서는 오른쪽 포인터를 오른쪽으로 이동시키는 것으로 볼 .. 2025. 1. 17. [백준] 2473번 - 세 용액 [Java] https://www.acmicpc.net/problem/2473 1. 아이디어 기존 두 용액 문제에서 용액의 수가 하나 더 늘어난 문제로 반복문 내에서 투 포인터 알고리즘을 돌리는 방식으로 세 용액을 다룰 수 있다.([코딩테스트 준비/백준] - [백준] 2470번 - 두 용액 [Java])2. 문제풀이 용액 하나를 고정시키고 투 포인터 알고리즘을 돌리면 세 용액을 다룰 수 있다. 이때 고정시킨 용액을 반복문으로 처리하면 되며 세 용액의 합을 구하는 과정에서 int형 오버플로우가 발생하는 것에 대비해 그냥 long 타입 배열로 관리했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(Stri.. 2025. 1. 13. [백준] 2470번 - 두 용액 [Java] https://www.acmicpc.net/problem/2470 1. 아이디어 기존 용액 문제에서 입력 값이 정렬되지 않은 채로 주어지는 문제로 정렬 후 투 포인터 알고리즘으로 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 2467번 - 용액 [Java])2. 문제풀이 기존 방식에서 정렬만 추가하면 해결할 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2025. 1. 13. [백준] 2467번 - 용액 [Java] https://www.acmicpc.net/problem/2467 1. 아이디어 투 포인터 알고리즘으로 간단하게 해결할 수 있다.2. 문제풀이 용액을 배열로 입력 받은 후 맨 왼쪽에 포인터 하나, 맨 오른쪽에 포인터 하나를 뒀다.이후 두 포인터가 위치한 용액의 특성값의 합을 구해서 절댓값을 씌웠을 때 현재까지 구한 특성값보다 작으면 정답 용액을 갱신하고 작지 않으면 특성값의 합이 양수면 오른쪽 포인터를 왼쪽으로, 음수면 왼쪽 포인터를 오른쪽으로 이동시켜줬다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffer.. 2025. 1. 12. [백준] 11728번 - 배열 합치기 [Java] https://www.acmicpc.net/problem/11728 1. 아이디어 정렬된 배열 두 개를 합치는 경우 각 배열의 앞 원소들을 비교하며 추가하면 합쳐진 배열을 따로 정렬하지 않아도 정렬을 유지함을 이용했다.2. 문제풀이 각 배열의 앞 원소를 비교해서 작은 원소를 새로운 배열에 넣고 작았던 원소의 다음 위치을 비교할 원소로 바꿔주는 과정을 두 배열의 모든 원소를 확인할 때까지 반복하면 된다. 구체적 구현으로는 Queue와 투 포인터 알고리즘을 활용했고 Queue는 peek 값이 배열의 앞 원소가 되면서 Queue에서 원소를 제거하면 자동으로 다음 원소를 바라보게 되어 적합하다고 생각했고, 투 포인터 알고리즘은 배열을 그대로 둔 채 포인터의 이동으로 확인을 한다는 점에서 역시 적합하다고 판단했.. 2025. 1. 8. [백준] 1644번 - 소수의 연속합 [Java] https://www.acmicpc.net/problem/1644 1. 아이디어 에라토스테네스의 체를 이용해서 소수를 구하고 투 포인터 알고리즘으로 연속합을 구하는 방식을 활용하면 해결할 수 있다.2. 문제풀이 에라토스테네스의 체를 이용해서 소수 리스트를 먼저 구했다.이후 투 포인터 알고리즘을 활용해서 소수의 연속합을 구하는데 포인터는 둘다 앞쪽에 위치시킨채 소수의 연속합이 N보다 작으면 오른쪽 포인터를 한칸 오른쪽으로, N보다 크면 왼쪽 포인터를 한칸 오른쪽으로 이동시키는 방식으로 구현했다.N이 1일 경우 예외처리를 해줘야 했는데 그냥 main 메서드에서 바로 종료하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { .. 2025. 1. 7. [백준] 7795번 - 먹을 것인가 먹힐 것인가 [Java] https://www.acmicpc.net/problem/7795 1. 아이디어 투 포인터 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 두 종류의 생명체를 각각 배열에 저장한 후 정렬을 수행한다.이후 각 배열의 가장 큰 원소 위치에 각각 포인터를 설정하고 해당 포인터를 기준으로 매칭되는 쌍의 개수를 세어줬다.A 포인터 위치의 생명체가 B 포인터 위치의 생명체보다 크다면 B 포인터의 위치로 더 작은 생명체들의 수를 바로 알 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader.. 2025. 1. 5. [백준] 3273번 - 두 수의 합 [Java] https://www.acmicpc.net/problem/3273 1. 아이디어 투 포인터 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 두 수의 합이 X가 되는 조합의 수를 구해야 한다.이를 투 포인터 알고리즘을 적용하면 입력 값을 배열로 저장한 뒤 정렬을 해준다.이후 배열 양 끝에서 포인터를 출발해서 두 수의 합이 X보다 작으면 왼쪽 포인터를 오른쪽으로 한 칸 이동시켜 두 수의 합이 더 커지게 만들고 두 수의 합이 X보다 크면 오른쪽 포인터를 왼쪽으로 한 칸 이동시켜 두 수의 합이 더 작아지게 만들어준다. 두 수의 합이 X가 되면 조합의 수를 하나 세고 두 포인터를 모두 한 칸씩 이동시키면 된다.3. 코드 import java.io.*;import java.util.*;public cl.. 2025. 1. 4. [백준] 25381번 - ABBC [Java] https://www.acmicpc.net/problem/25381 1. 아이디어 시행할 수 있는 최대 횟수는 B와 C를 먼저 지우고 A와 B를 지울 때 최대가 되는 것을 이용했다.2. 문제풀이 B와 C, A와 B를 지울 때 앞의 문자를 기준으로 가장 가까운 뒷쪽에 위치한 문자와 삭제할 때 가장 많이 지울 수 있다. B와 C를 지울 때는 B를 발견하면 그 뒤로 가장 가까운 C와 매핑시켜 지우는 과정을 반복하고, A와 B를 지울 때는 A를 발견하면 그 뒤로 가장 가까운 B와 매핑시켜 지우는 과정을 반복하면 된다. 이 과정에서 처음엔 여러 개의 Deque를 만들어서 풀이를 했는데 52점을 받았다. 예외 케이스를 찾다가 A 15만개 뒤에 B 15 만개가 붙은 문자열에서 시간이 매우 많이 소요되는 것을 발견해.. 2024. 12. 6. 이전 1 다음
