첫 줄에 n과 S가, 둘째 줄에 작은 것부터 차례로(같은 값이 있어도 됨) 정렬된 정수 n개 a₁ … aₙ이 주어진다.
aᵢ + aⱼ = S이고 i < j인 두 자리 i, j를 찾아 "i j"로 출력하라(자리는 1부터 센다).
같은 자리를 두 번 쓸 수는 없다.
답이 여럿이면 i가 가장 작은 것을, 그중에서도 j가 가장 큰 것을 출력한다.
그런 두 자리가 없으면 -1을 출력한다.
6 4 1 1 2 3 3 3
1 6
3 10 1 5 8
-1
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
모든 짝을 해 보면 n = 10,000일 때 약 5천만 번이라 느려요.
정렬돼 있으니 두 포인터로 양 끝에서 시작해 합이 작으면 왼쪽을, 크면 오른쪽을 한 칸 옮기면 n번 안에 끝나요.
이 방법은 저절로 i가 가장 작고 그다음 j가 가장 큰 답을 먼저 찾아요.
답이 두 개(i, j)라 함수에서 값 둘을 돌려주는 법이 언어마다 달라요: Python 튜플 return i, j, JavaScript 배열 return [i, j]와 const [i, j] = …, TypeScript는 튜플 타입 [number, number], C# 튜플 (int, int)와 var (i, j) = …, C++ std::pair와 auto [i, j] = …, Java는 튜플이 없어 int[](또는 record), C는 포인터 매개변수 int *pi, 크레이콘은 목록 돌려주기 [i, j];.
함정 둘: lo <= hi로 돌리면 한 원소를 두 번 써서 1 5 9에서 5 + 5 = 10을 찾아 버려요.
또 값이 20억까지라 두 값의 합은 int(약 21억)를 넘을 수 있어요 — C·C++·Java·C#은 long long/long으로 받아야 해요(Java·C#은 넘치면 음수로 돌아가고, C·C++에서는 정의되지 않은 동작이라 맞을 때도 틀릴 때도 있어요).
Python·JavaScript·TypeScript·크레이콘은 그대로 맞아요.
def find_pair(a, s): """a[i] + a[j] == s 인 (i, j)를 1부터 센 자리로 돌려준다. 없으면 (-1, -1).""" lo, hi = 0, len(a) - 1 while lo < hi: total = a[lo] + a[hi] if total == s: return lo + 1, hi + 1 if total < s: lo += 1 else: hi -= 1 return -1, -1 n, s = map(int, input().split())a = list(map(int, input().split()))i, j = find_pair(a, s)print(-1 if i == -1 else f"{i} {j}")// a[i] + a[j] === s 인 [i, j]를 1부터 센 자리로 돌려준다. 없으면 [-1, -1].function findPair(a, s) { let lo = 0; let hi = a.length - 1; while (lo < hi) { const total = a[lo] + a[hi]; if (total === s) return [lo + 1, hi + 1]; if (total < s) lo++; else hi--; } return [-1, -1];} const [n, s, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [i, j] = findPair(a, s);console.log(i === -1 ? "-1" : `${i} ${j}`);import { readFileSync } from "node:fs"; // a[i] + a[j] === s 인 [i, j]를 1부터 센 자리로 돌려준다. 없으면 [-1, -1].function findPair(a: number[], s: number): [number, number] { let lo = 0; let hi = a.length - 1; while (lo < hi) { const total = a[lo] + a[hi]; if (total === s) return [lo + 1, hi + 1]; if (total < s) lo++; else hi--; } return [-1, -1];} const [n, s, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [i, j] = findPair(a, s);console.log(i === -1 ? "-1" : `${i} ${j}`);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { // a[i] + a[j] == s 인 {i, j}를 1부터 센 자리로 돌려준다. 없으면 {-1, -1}. static int[] findPair(long[] a, long s) { int lo = 0, hi = a.length - 1; while (lo < hi) { long total = a[lo] + a[hi]; if (total == s) return new int[] {lo + 1, hi + 1}; if (total < s) lo++; else hi--; } return new int[] {-1, -1}; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); long s = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); long[] a = new long[n]; for (int k = 0; k < n; k++) a[k] = Long.parseLong(st.nextToken()); int[] p = findPair(a, s); System.out.println(p[0] == -1 ? "-1" : p[0] + " " + p[1]); }}using System;using System.Linq; class Program{ // a[i] + a[j] == s 인 (i, j)를 1부터 센 자리로 돌려준다. 없으면 (-1, -1). static (int, int) FindPair(long[] a, long s) { int lo = 0, hi = a.Length - 1; while (lo < hi) { long total = a[lo] + a[hi]; if (total == s) return (lo + 1, hi + 1); if (total < s) lo++; else hi--; } return (-1, -1); } static void Main() { long s = long.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); long[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); var (i, j) = FindPair(a, s); Console.WriteLine(i == -1 ? "-1" : $"{i} {j}"); }}#include <iostream>#include <utility>#include <vector> // a[i] + a[j] == s 인 {i, j}를 1부터 센 자리로 돌려준다. 없으면 {-1, -1}.std::pair<int, int> findPair(const std::vector<long long>& a, long long s) { int lo = 0, hi = static_cast<int>(a.size()) - 1; while (lo < hi) { long long total = a[lo] + a[hi]; if (total == s) return {lo + 1, hi + 1}; if (total < s) lo++; else hi--; } return {-1, -1};} int main() { int n; long long s; std::cin >> n >> s; std::vector<long long> a(n); for (auto& x : a) std::cin >> x; auto [i, j] = findPair(a, s); if (i == -1) std::cout << "-1\n"; else std::cout << i << " " << j << "\n";}#include <stdio.h> /* 값 두 개는 포인터로 돌려준다. 찾으면 1, 없으면 0. */static int find_pair(const long long *a, int n, long long s, int *pi, int *pj) { int lo = 0, hi = n - 1; while (lo < hi) { long long total = a[lo] + a[hi]; if (total == s) { *pi = lo + 1; *pj = hi + 1; return 1; } if (total < s) lo++; else hi--; } return 0;} int main(void) { static long long a[10000]; int n, i, j; long long s; scanf("%d %lld", &n, &s); for (int k = 0; k < n; k++) scanf("%lld", &a[k]); if (find_pair(a, n, s, &i, &j)) printf("%d %d\n", i, j); else puts("-1"); return 0;}// a[i] + a[j] == s 인 [i, j]를 1부터 센 자리로 돌려준다. 없으면 [-1, -1].짝찾기(a, s){ lo = 0; hi = a.개수 - 1; 동안 (lo < hi) { total = a[lo] + a[hi]; 만약 (total == s) { 돌려주기 [lo + 1, hi + 1]; } 만약 (total < s) { lo += 1; } 아니면 { hi -= 1; } } 돌려주기 [-1, -1];} 첫줄 = 콘솔.수들읽기();s = 첫줄[1];a = 콘솔.수들읽기();답 = 짝찾기(a, s);만약 (답[0] == -1){ 콘솔.쓰기(-1);}아니면{ 콘솔.쓰기(답[0] + " " + 답[1]);}