투 포인터
-
Programmers Lv3) [2020 카카오 인턴십] 보석쇼핑Algorithm/Programmers 2021. 4. 21. 17:31
출처: programmers.co.kr/learn/courses/30/lessons/67258 분류: Lv3, 카카오 인턴십, 투 포인터 접근방식 투 포인터 방식으로 해결했습니다. 먼저 전체 보석 종류의 개수를 구해놓고 포인터를 움직이면서 모든 보석이 들어있는 경우를 체크해주는 방식입니다. 저는 처음에 조금 비효율적으로 접근했는데요, 보석의 개수를 체크해주면서 현재 시작 포인터의 보석이 여러 개라면 현재 보석을 더 들고 있을 필요가 없으니 포인터를 옮겨주는 방식을 사용했습니다. 전체 과정을 좀 더 설명드리면, 저는 시작 포인터가 끝에 도달할 때까지 반복문을 돌려주면서 먼저 보석이 모두 들어있는지 체크해서 최선이라면 결과를 바꿔주고 끝 포인터를 움직이면서 보석에 담아줍니다. 그리고 현재 시작 포인터의 보석..
-
백준 2143 두 배열의 합Algorithm/BOJ 2021. 3. 5. 13:44
출처: www.acmicpc.net/problem/2143 분류: 이분 탐색, 투 포인터 접근방식 합이 0인 네 정수 문제와 비슷했던 문제였습니다. 주어진 각 배열에서 나올 수 있는 부분합을 모두 구해준 뒤 정렬해서 투 포인터로 해결했습니다. 마찬가지로 T인 케이스를 찾았을 때 중복인 수의 개수를 세서 쌍을 찾아줘야 합니다 :) 해결방법 let t = Int(readLine()!)! let n = Int(readLine()!)! let a = readLine()!.split(separator: " ").map { Int(String($0))! } let m = Int(readLine()!)! let b = readLine()!.split(separator: " ").map { Int(String($0))..
-
백준 7453 합이 0인 네 정수Algorithm/BOJ 2021. 3. 4. 14:53
출처: www.acmicpc.net/problem/7453 분류: 투 포인터, 이분 탐색 접근방식 4개의 배열이 주어지고 각 원소의 합이 0이되는 쌍이 몇 개인지 찾는 문제입니다. 이 문제의 첫 번째 아이디어는 4개의 배열을 각각 생각하려고 하면 힘드니 2개씩 묶어서 합쳐주는 것입니다. a b 의 합이 될 수 있는 모든 경우를 담은 배열 ab, c d 의 합이 될 수 있는 모든 경우를 담은 배열 cd 를 만들고 둘 모두 오름차순으로 정렬해줍니다. 다음으로 ab는 작은 수부터, cd는 큰 수부터 포인터를 움직여 0이 되는 경우를 찾는 것입니다. ab, cd 원소의 합이 0보다 작으면 low를 증가시키고 0보다 크면 high를 줄여줍니다. sum이 0일 때 주의해야할 건 중복을 찾아서 쌍을 계산해줘야 합니다..
-
백준 2003 수들의 합2카테고리 없음 2021. 1. 22. 10:53
출처: https://www.acmicpc.net/problem/2003 분류: 두 포인터 접근방식 수열의 특정 구간의 합이 특정한 수가 되는 경우의 수를 구하는, 대표적인 투 포인터 문제입니다. 2개의 포인터를 둬서 하나는 합이 원하는 수보다 크거나 같으면, 다른 하나는 합이 원하는 수보다 작으면 움직여주면서 합을 계산해주면 됩니다:) 해결방법 protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()! } func readSingleVa..