이진탐색, 투 포인터로 다시 풀어보기
이진탐색 NlogN
투 포인터 N
누적합 N^2
https://www.acmicpc.net/problem/2118
환형구조에서 반대쪽으로의 거리를 구할려면 전체 거리 - 순방향 거리를 하면 된다.
투포인터 문제이지만 나는 N2 복잡도인 누적합으로 해결하였다.
환형구조의 경우 선형자료형에 저장하기 위해 모듈러(%)를 사용하여 인덱스를 관리해 주어야 한다.
상황에 따라 그냥 배열을 두배로 늘리고 모듈러를 사용하지 않는 것도 방법이다.
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] distances = new int[n];
int distance_sum = 0;
for(int i=0; i<n;i++){
distances[i]= Integer.parseInt(br.readLine());
distance_sum+=distances[i];
}
int[] acc = new int[n+1];
acc[0]=0;
for(int i=1;i<n+1;i++){
acc[i] = acc[i-1] + distances[i-1];
}
int ans=0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int dist = Math.min(distance_sum-(acc[i+1]-acc[j]),acc[i+1]-acc[j]);
ans = Math.max(dist,ans);
}
}
System.out.println(ans);
}
}
투 포인터를 이용한 코드
시계방향보다 반시계방향이 커지는 순간에서 while문 나감 -> 최대 값임 그때가
그리고 다음 반복문은 시작탑만 옮김 왜냐하면 도착탑까지는 무조건 가능하기 때문(이전반복문에서의 최대값이니 다음 반복문에서도 무조건 가능함)
import java.util.Scanner;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] distance = new int[N];
int distanceSum = 0;
for (int i = 0; i < N; i++) {
distance[i] = sc.nextInt();
distanceSum += distance[i];
}
int pairIndex = 1;
int leftDistance = distance[0];
int rightDistance = distanceSum - distance[0];
int maxDistance = Math.min(leftDistance, rightDistance);
for (int i = 0; i < N; i++) {
while (leftDistance < rightDistance) {
leftDistance += distance[pairIndex];
rightDistance -= distance[pairIndex];
pairIndex = (pairIndex + 1) % N;
}
maxDistance = Math.max(maxDistance, Math.min(leftDistance, rightDistance));
leftDistance -= distance[i];
rightDistance += distance[i];
}
System.out.println(maxDistance);
}
}
'Problem Solving > 투포인터' 카테고리의 다른 글
BOJ17609 회문 (0) | 2024.03.04 |
---|---|
BOJ11728 배열합치기 (0) | 2024.03.04 |
BOJ 12891 DNA 비밀번호 (0) | 2024.03.03 |
BOJ2230 수 고르기 (0) | 2024.03.03 |
BOJ 1806 부분합 (0) | 2024.03.03 |