💡문제
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
출력
문제의 조건을 만족하는 쌍의 개수를 출력한다.
예제입력
9
5 12 7 10 9 1 2 3 11
13예제출력
3📖내가 작성한 Code
import sys
'''
n이 10만 O(n)으로 한번에
'''
def two_pointer(n,array,find_number):
start, end, count_combination = 0, n-1, 0
while start < end:
plus_numbers = array[start] + array[end]
if plus_numbers > find_number:
end -= 1
else:
if plus_numbers == find_number:
count_combination += 1
start += 1
return count_combination
def main():
inputs = sys.stdin.read().split()
n = int(inputs[0])
array = [int(inputs[i]) for i in range(1,n+1)]
find_number = int(inputs[-1])
array.sort()
sys.stdout.write(str(two_pointer(n, array, find_number)))
if __name__ == '__main__':
main()
✍️풀이과정
n을 이중 반목문을 사용한다면, 무조건 터지는 문제라고 생각. 그래서 바로 투 포인터로 풀었더니 바로 풀렸던 문제. 이런 문제 나오면 땡큐임!!
최적화 안했는데 이정도면 그냥 넘어가도 될지도...?
위에는 set을 활용하여 전체를 찾았는데 엣지케이스에서 터지지 않을까..?
그리고 앞으로는, Java도 같이 할까 생각 중. AI 리뷰 코드 보다는 Python 코드를 Java로 변경해보며, Java 전용 코테에 대한 대비를 할까 생각 중이다.
🧠 코드 리뷰
-
함수의 범용성 강화: 함수 내부에서 배열을 정렬하도록 수정하면, 함수 호출 시 정렬 여부를 신경 쓰지 않아도 되어 사용성이 개선됩니다.
-
정렬로 인한 시간 복잡도 고려: 현재 O(n log n)의 시간 복잡도를 가지는 정렬 과정을 포함하고 있습니다. 만약 입력 배열이 이미 정렬되어 있다면, 정렬 과정을 생략하여 성능을 향상시킬 수 있습니다. 또한, 해시맵을 활용하여 O(n) 시간 복잡도로 문제를 해결하는 방법도 고려해볼 수 있습니다.
🛠️Java 연습 코드
import java.io. *;
import java.util.*;
public class Main {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens()) {
String line = br.readLine();
if (line == null) return null;
st = new StringTokenizer(line);
}
return st.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
public static int twoPointer(int[] array, int findNumber) {
int start = 0;
int end = array.length - 1;
int countCombination = 0;
while (start < end) {
int sum = array[start] + array[end];
if (sum > findNumber) {
end--;
} else {
if (sum == findNumber) {
countCombination++;
}
start++;
}
}
return countCombination;
}
public static void main(String[] args) throws IOException {
FastReader in = new FastReader();
int n = in.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = in.nextInt();
}
int findNumber = in.nextInt();
Arrays.sort(array);
int countCombination = twoPointer(array, findNumber);
System.out.println(countCombination);
}
}
💻결과
🖱️참고 링크
