성능 요약
메모리:
- Java: 14664 KB, 시간: 176 ms
- C++: 2020 KB, 시간: 16 ms
분류
이분 탐색, 정렬, 두 포인터
제출 일자
2024년 12월 15일 02:41:29
문제 설명
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.
입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
출력
좋은 수의 개수를 첫 번째 줄에 출력한다.
풀이
-
느낀점: 두개를 골라야 하고 정렬이 의미가 있을때, 투포인터 고려하기
-
설계 시간: 30분 고민해보고 참고함
💡 설계 아이디어
- 입력된 수를 배열에 오름차순으로 정렬시키고, 각 수를 순회한다.
- 배열의 양끝 인덱스를 각각 left, right로 두고 투포인터 방식으로 이동한다.
- 두 포인터가 가리키는 값들의 합이 목표값보다 크면 right를 왼쪽으로 이동한다.
- 목표값보다 작으면 left를 오른쪽으로 이동한다.
- 같으면 “좋다”
- 단, 자기 자신은 더할 수 없으므로 두 인덱스가 목표값의 인덱스와 일치하면 각각 이동방향으로 한칸씩 이동한다.
코드
구현 시간: 15분 (Java)
/**
* Author: yngbao97, Yuk Yejin
* Problem: 좋다_1253
* Date: 2024.12.15
*/
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] nums = new int[n];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(nums);
int answer = 0;
for (int i = 0; i < n; i++) {
int left = 0;
int right = n-1;
while (left < right) {
if (left == i) left++;
if (right == i) right--;
if (left >= right) break;
if (nums[left] + nums[right] > nums[i]) right--;
else if (nums[left] + nums[right] < nums[i]) left++;
else {
answer++;
break;
}
}
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}구현 시간: 15분 (C++) - ver.1
/**
* Author: yngbao97, Yuk Yejin
* Problem: 좋다_1253
* Date: 2024.12.15
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int nums[n];
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
sort(nums, nums + n);
int answer = 0;
for (int i = 0; i < n; i++) {
int left = 0;
int right = n-1;
while (left < right) {
if (left == i) left++;
if (right == i) right--;
if (left >= right) break;
if (nums[left] + nums[right] > nums[i]) right--;
else if (nums[left] + nums[right] < nums[i]) left++;
else {
answer++;
break;
}
}
}
cout << answer << "\n";
}- C++은 배열 생성을 크기와 함께 한번에 한다.
ex) int nums[3]; - 일반 배열 정렬시 사용하는 sort(시작 포인터, 엔드 포인터)는 algorithm 헤더를 include 한다.
- 위 코드에서
nums는 배열의 첫번째 요소를 가리키는 포인터다. - 위 코드에서
nums + n은 배열의 마지막 요소의 다음을 가리키는 포인터다. - 배열의 길이를 특정지을 수 없을때 구하는 방법은 sizeof()를 사용할 수 있는데, 이는 배열의 길이가 아닌 실제 데이터 크기를 반환하기 때문에
sizeof(전체 배열) / sizeof(요소 하나)로 구한다.
- 위 코드에서
구현 시간: 15분 (C++) - ver.2
/**
* Author: yngbao97, Yuk Yejin
* Problem: 좋다_1253
* Date: 2024.12.15
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int& num : nums) {
cin >> num;
}
sort(nums.begin(), nums.end());
int answer = 0;
for (int i = 0; i < n; i++) {
int left = 0;
int right = n-1;
while (left < right) {
if (left == i) left++;
if (right == i) right--;
if (left >= right) break;
if (nums[left] + nums[right] > nums[i]) right--;
else if (nums[left] + nums[right] < nums[i]) left++;
else {
answer++;
break;
}
}
}
cout << answer << "\n";
return 0;
}- C++에서는 가변 크기 배열 대신
vector를 사용하는 것이 더 안전하고 효율적이다. - vector의 요소에는 벡터이름[인덱스]로 접근 가능하다.
- for문을 사용하면 전통적인 인덱스 순환방식으로도 가능하지만 향상된 for문을 사용할수도 있다.
- 이때, 참조자(&) 사용시 원본 벡터의 요소를 직접 참조하여 복사본을 만들지 않아 메모리를 절약한다. 값의 변경이 필요한 경우 사용한다.
- 참조자 미사용시 원본 벡터의 값이 변경되지 않는다.
- vector 선언 방법
vector<int> nums; // 크기 0으로 선언
vector<int> nums(n); // 크기 n으로 선언, 모든 요소 0으로 초기화
vector<int> nums(n, 5); // 크기 n으로 선언, 모든 요소 5로 초기화