🥇 Problem Solving/Two-pointer

[Python] BOJ / 17609번 / 회문

17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 📝 풀이 문자열이 주어졌을 때 회문인지, 유사 회문인지, 일반 문자열인지 구분하여 출력하는 프로그램 문자열의 처음(left = 0)과 끝(right = len(word) - 1)에 포인터를 두고 대치되는 위치의 두 문자를 비교해 감 1. 대치되는 두 문자가 동일한 경우 왼쪽 포인터(left)는 +1을, 오른쪽 포인터(right)는 -1을 하여 다음 문자 비교 2. 대치되는 두 문자가 동일하지 않은 경우 왼쪽 문자 혹은 오른쪽 문자를 제거했을 때 회문이 되는지 확인 이 과정에서 회문이 된다면 유..

[Python] BOJ / 2230번 / 수 고르기

2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 📝 풀이 투 포인터 알고리즘 사용 입력받은 배열 오름차순 정렬 포인터 left = 0, right = 1로 초기화 두 수를 골랐을 때 같은 수일 수 있음 while left < n and right < n 알고리즘 수행 만약 두 포인터가 가리키는 인덱스의 값의 차가 m일 경우 그대로 출력 후 종료(차이가 m 이상이면서 가장 작은 차이는 m이므로) 두 값의 차가 m보다 클 경우 현재까지 구한 최소 차이와 비교하여 더 작을 경우 갱신 더 작은 차..

[Python] BOJ / 2473번 / 세 용액

2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서..

[Python] BOJ / 7453번 / 합이 0인 네 정수

7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력 합이 0이 되는 쌍의 개수를 출력한다. 풀이 ..