https://www.acmicpc.net/problem/2470
2470번: 두 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00
www.acmicpc.net
문제를 파악하면서 투 포인터라는 것을 알고 분석을 해봤다.
2 <= N <=100,000 이니깐 최악의 경우 O(N^N)이겠구나? 이러면 비효율적이니깐 투포인터로 가자.
0과 가까운 두 용액의 수를 찾는 거니깐 두 값의 합에 절대값을 기준으로 풀면되겠다.
(여기서부터 산으로...)
그럼 i=0, j=1로 두고 합의 절대값이 기존 최소값보다 작으면 j++을 하고 크면 i++을 하자~
어?! 근데 i,j가 같은 자리에 있으면 또 안되니깐 i != j - 1 라는 조건도 추가되나...?
라는 식으로 엄~~~청 산으로 가면서 풀다가...결국 해답을 살짝보면서 풀어보긴했다ㅠㅠ
핵심
1) 음수, 양수가 섞인 배열을 우선 오름차순 정렬한다. ( O(n)으로 풀기 위해서 )
그렇게 되면 맨 왼쪽은 가장 낮은 음수, 맨 오른쪽은 가장 큰 양수가 자리하게 되고, 가운데로 갈수록 점점 절댓값은 작아질 것이다.
2) 그래서 양 끝부터 시작해서 탐색을 진행한다.
왼쪽 index를 i , 오른쪽 index를 j 라고 할 때
i -> <- j
로 진행하며 i가 j보다 커지기 전까지 while문을 만족하는 반복문을 짠다.
가운데로 갈수록 절대값이 점점 작아지는 것을 다시 한번 생각해보면 다음과 같다.
문제의 예시를 정렬하면
-99 -2 -1 4 98이런식으로 나온다. 이때 i = 0, j = 4에 위치하고 그때의 합은 -1이다. 여기서 생각을 한번 더 하게 되는데 -1일 때 i, j 중 뭘 이동 시키지? 라는 질문이다.
이때는 두 값의 합이 음수가 되었고 가운데로 갈 수록 절대값이 작아진다는 보장이 있으므로 양수인 쪽을 감소시키면 절대값이 더 작아지겠다~?라는 생각을 할 수가 있다.
반대로 합이 양수가 나오면 양수를 더 작게 만들어야 하므로 음수인 i 쪽을 증가시키는 것이다.
3) 그래서 i의 원소와 j의 원소의 합(어떻게 말하면 두 원소 사이의 길이)의 절댓값을 저장하며
이전에 계산했던 절댓값보다 큰지 작은지 비교한다.
만약 이전 절댓값보다 작은 경우 정답에 가까워지기 때문에 이 두 원소를 별도 저장해두고, 위 절댓값을 이번에 계산해서 나온 절댓값으로 갱신한다.
이를 위 while문 조건을 벗어날 때 까지 반복한다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 용액 개수
st = new StringTokenizer(br.readLine());
int[] solution = new int[N];
for (int i = 0; i < N; i++) {
solution[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(solution);
int start = 0;
int end = N - 1;
int min = Integer.MAX_VALUE;
int a1 = 0;
int a2 = 0;
while (start < end) {
int sum = solution[start] + solution[end];
int abs = Math.abs(sum);
if (abs < min) {
min = abs;
a1 = solution[start];
a2 = solution[end];
}
if (sum < 0) {
start++;
} else {
end--;
}
}
System.out.println(a1 + " " + a2);
bw.flush();
br.close();
bw.close();
}
}
|
cs |
피드백
N이 최대 100,000 인데 시간제한 1초인데다가 언어별 추가시간이 없기 때문에 O(n)으로 풀어야 한다.
비효율적으로 푸는 방법은 N개중에서 2개를 뽑는 콤비네이션을 완전탐색으로 돌려서 푸는 방법이 있긴 하다.
O(N)에 푸는 방법은 우선 배열을 정렬한다.
100,000까지는 정렬을 사용해도 되는거 같다.