two pointer
[LeetCode/릿코드] 948. Bag of Tokens - Python
[Medium] https://leetcode.com/problems/bag-of-tokens/ 풀이 tokens 배열을 오름차순 정렬해준 후, Two Pointer 기법을 이용해 풀어주면 쉽게 풀이할 수 있다. curl, curr 이라는 두 개의 커서를 각각 0, len(tokens) 로 초기화한 뒤, 차례로 진행해주면 된다. 현재 power가 왼쪽 커서(curl)의 토큰값보다 크다면 power를 낮추고 score를 올린 뒤(Face-up), 커서를 오른쪽으로 한 칸 이동. 현재 power가 왼쪽 커서(curl)의 토큰값보다 작다면, score가 1 이상이며, 왼쪽 커서와 오른쪽 커서가 같은 곳을 가리키지 않을 때, score를 낮추고 power를 올린다. (Face-down) 왼쪽 커서와 오른쪽 커서..
[백준] 1644. 소수의 연속합 - 파이썬
[Gold III] https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 1 보자마자, Prefix Sum 문제라고 생각했다. 먼저 에라토스테네스의 체를 이용해 입력값인 N까지의 수 중 소수를 구하고, 그 소수들의 리스트를 이용해 prefix sum 리스트를 만든 후, Two Pointer 기법을 이용해 부분합의 값이 N과 동일한 지 확인하는 방법. 시간은 충분했으나, MLE. (Memory Limit Exceed.) N = int(input()) nums = {i: 0 for i in range(2, N+1)} # 에라토스테네스의 체 for i in nums: ..
[백준] 2473. 세 용액 - 파이썬
[Gold III] https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 [백준] 2467. 용액 - 파이썬 의 업그레이드(?) 버전. 2467번 용액 문제는 N
[백준] 2467. 용액 - 파이썬
[Gold V] https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 1과 풀이 2 모두 AC(통과)가 가능한 코드입니다. 풀이 1 일단, 모든 경우의 수를 다 따져본다면(Brute-Force), NC2 이기 때문에, (N * (N-1)) / 2 => O(N^2) 정도의 Time Complexity로 풀 수 있게 됨. 당연히 이 방법은 아닐 테고, 일단 문제를 보자마자 직감적으로 생각난 것은 Two Pointer였다. 그런데 일반적인 tw..
[백준] 1806. 부분합 - 파이썬
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 1 문제 이름과 같이, Prefix Sum (부분합)을 이용하여 풀이하면 되는 문제. 설명은 다른 곳에 더 잘 설명되어 있을 테니 생략. line 13 ~ 16에서 Time Complexity가 O(N^2)이라 TLE. 1부터 N까지의 공차가 1인 등차수열의 합은 n(n+1)/2 이므로.. O(N^2) import sys input = sys.stdin.readline N, S..
[프로그래머스] 67258. 보석 쇼핑
2020 카카오 인턴십 - 67258. 보석 쇼핑 Python 풀이 풀이 1 Two Pointer(투 포인터) 알고리즘을 이용해 풀이. 외국에선.. Two Pointer Technique(투 포인터 테크닉) 이라고 부르는 듯. start, end Pointer를 정하고, 처음엔 조건을 만족할 때까지 end += 1 그 이후, 조건을 만족하는 한 start += 1 그렇게 조건을 만족하는 [start, end]를 구함. 그 이후, 뒤쪽에 더 짧은 답이 존재할 수 있으니 end에 +1을 해주며, end < len(gems) 이하에서 반복. 그렇게 Two Pointer를 이용해 풀이하였으나, 시간 초과. Code def solution(gems): gemList = len(set(gems)) start = 0..