개발하는 개구리

🐸 문제 정보 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 🤖 알고리즘 투포인터 ⏱️ 풀이 시간 14.41m 📝 풀이 처음에 괜한 도전정신으로 힙으로 풀어보려다가 숫자 개수 보고 정신차리고 제대로 풀었다. 간단한 투포인터 문제이고, 두 리스트에 맨 처음부터 움직이는 인덱스를 두어 값을 비교하면서 하나씩 채워나가면 된다. 어차피 둘 다 정렬된 배열이기 때문에, 한 리스트에서 인덱스가 끝에 도착하면 나머지 리스트의 나머지 값은 그냥 더해주면 된다. 🧑‍💻 나의 답 # pypy..

🐸 문제 정보 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 🤖 알고리즘 누적합, 투포인터 ⏱️ 풀이 시간 12.12m 📝 풀이 누적합으로 풀면 간단하지만, 구할 수 없는 경우 0 출력 처리 때문에 약간의 시간 낭비를 했다. 주어진 입력 리스트를 누적합으로 만들고, 투포인터를 돌면서 아래 조건에 따라 처리하면 된다. start와 end 사이의 합이 s보다 크거나 같다면, 길이에 대해 최소값 처리를하고 start를 뒤로 한 칸 이동 start와 end 사이의 합이 s보다 작다면, end를 뒤로 ..

🐸 문제 정보 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 🤖 알고리즘 투포인터 ⏱️ 풀이 시간 60m+ 📝 풀이 생각보다 어려운 문제였다ㅠㅠ 처음에는 투포인터를 이용해서 앞부터 순회하며, start가 1커진다면 이전 start에서 구한 수열 - 1 개로 초기화되는 방식(dp + 투포인터)으로 구현하였으나 start와 end가 같아지는 시점에서 예외처리가 너무 많아 포기하게 됐다. 검색을 통해 end에서 start를 빼주면서 개수를 더해주는 아이디어를 얻었는데, 풀고나서 보니 대부분의 사람들이 dictionary를..

🐸 문제 정보 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 🤖 알고리즘 투포인터 ⏱️ 풀이 시간 25.15m 📝 풀이 오름차순으로 정렬했음에도 0번 인덱스부터, 그리고 해당 인덱스를 제외하고 투포인터를 진행해야한다는 것을 놓쳤다. 아마 정답률이 낮은 것도 나같은 사람이 많아서지 않을까 싶다. 입력 숫자 리스트 오름차순 정렬 0번 인덱스부터 끝까지 순회 특정 인덱스에 해당하는 숫자를 제외하고, 투포인터를 이용해서 해당 숫자를 만들어 낼 수 있는지 검사 start는 0부터, end는 해당 숫자를 제외한 리스트의 마지막 인덱스부터 만약 s..

🐸 문제 정보 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 🤖 알고리즘 투포인터 ⏱️ 풀이 시간 15.53m 📝 풀이 비교적 간단한 투포인터 문제였다. 마지막까지 전부 통과한 경우에 길이를 출력하는 것을 잊어 약간의 시간이 더 걸렸다. start와 end 모두 0부터 시작 end를 하나씩 뒤로 이동하며 딕셔너리에 담기 end 인덱스에 해당하는 숫자의 개수가 k보다 많다면, 우선 end - start를 res와 비교하여 더 큰 값 넣기 start를 뒤로 하나씩 이동하며 딕셔너리에서 해당 인덱스의 숫자를 ..