책꽂이에 책 n권이 책 번호가 작은 것부터 꽂혀 있다.
책 번호는 모두 다르고, 자리는 왼쪽부터 1번, 2번, …, n번이다.
사서는 책 번호 x를 찾을 때 다음처럼 한다.
처음에는 찾아볼 자리의 처음이 1번, 끝이 n번이다.
처음 자리 번호와 끝 자리 번호를 더해 2로 나눈 몫(나머지는 버린다)이 가리키는 자리의 책을 꺼내 본다.
그 책의 번호가 x이면 찾기를 끝낸다.
그 책의 번호가 x보다 작으면 처음을 그 자리의 바로 다음으로 옮기고, x보다 크면 끝을 그 자리의 바로 앞으로 옮긴다.
옮기고 나서 처음이 끝보다 커졌으면 그 책은 없는 것이므로 찾기를 끝낸다.
그렇지 않으면 바뀐 처음과 끝으로 같은 방법을 되풀이해 다음 책을 꺼내 본다.
첫 줄에 n과 q가, 둘째 줄에 책 번호 n개가, 셋째 줄에 찾을 번호 q개가 빈칸 하나로 띄워 주어진다.
찾을 번호마다 한 줄에, 사서가 꺼내 본 책의 번호를 꺼내 본 차례대로 쓰고 끝에 찾은 자리 번호를 써서 빈칸 하나로 띄워 출력하라.
찾지 못했으면 자리 번호 대신 0을 쓴다.
예시의 책꽂이에서 x = 15이면 처음 꺼내 본 책이 바로 15이므로 "15 3"을 출력한다.
입력
1 ≤ n ≤ 100, 1 ≤ q ≤ 100, 1 ≤ 책 번호 ≤ 1,000, 1 ≤ x ≤ 1,000(모두 정수, 책 번호는 오름차순이고 서로 다르다)
출력
찾을 번호마다 한 줄에 꺼내 본 책 번호들과 찾은 자리 번호(없으면 0)
예시 1 · stdin
6 5
3 8 15 20 42 77
42 8 9 77 3
stdout
15 42 5
15 3 8 2
15 3 8 0
15 42 77 6
15 3 1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
가운데 자리를 구할 때 몫만 남기는 방법이 언어마다 달라요. Python (lo + hi) // 2, C·C++·Java·C#은 int끼리 (lo + hi) / 2, JS·TS Math.floor((lo + hi) / 2), 크레이콘 수학.몫(lo + hi, 2). 찾아 주는 도구도 있어요. Python bisect.bisect_left, C++ std::lower_bound, Java Arrays.binarySearch, C# Array.BinarySearch는 예시의 42에 0부터 센 자리 4 하나만 알려 줘요. 어느 책을 꺼내 봤는지는 알려 주지 않으니 이 문제는 직접 써야 해요. 함정 하나: 되풀이 조건은 lo <= hi예요. lo < hi로 쓰면 남은 자리가 하나일 때 그 책을 꺼내 보지 않아서 예시의 넷째 줄이 15 42 0이 돼요. 함정 둘: JS에서 Math.floor 없이 /로 나누면 가운데가 3.5가 되고 그 자리의 책은 undefined라서 예시의 모든 줄이 빈칸 둘 뒤에 0만 나와요. 크레이콘에서 /를 쓰면 [ ] 안에는 정수 번호를 써 주세요라는 오류로 멈춰요. 함정 셋: Python에서 책 번호를 int로 바꾸지 않으면 문자열로 견주어서 "15" < "8"이 참이 돼요. 예시의 둘째 줄이 15 42 77 0이 돼요. 함정 넷: 가운데를 (lo + hi + 1) / 2로 올려 잡으면 다른 책을 꺼내요. 예시의 첫 줄이 20 77 42 5가 돼요. 함정 다섯: 자리를 0부터 세면서 그 번호를 그대로 출력하면 자리가 하나씩 작게 나와요. 예시의 첫 줄이 15 42 4가 되고, 마지막 줄은 15 3 0이라 찾고도 못 찾은 것처럼 보여요.
Pythonmain.py · 19 줄
n, q = map(int, input().split())books = list(map(int, input().split()))queries = list(map(int, input().split()))for x in queries: lo, hi = 1, n # 아직 찾아볼 자리의 처음과 끝 seen = [] # 펼쳐 본 책 번호 answer = 0 while lo <= hi: mid = (lo + hi) // 2 # 몫만 남긴다 book = books[mid - 1] # mid번째 자리는 목록의 mid - 1번 칸 seen.append(book) if book == x: answer = mid break if book < x: lo = mid + 1 else: hi = mid - 1 print(*seen, answer)
JavaScriptmain.js · 25 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const books = lines[1].trim().split(/\s+/).map(Number);const queries = lines[2].trim().split(/\s+/).map(Number);const out = [];for (let k = 0; k < q; k++) { const x = queries[k]; let lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 const seen = []; // 펼쳐 본 책 번호 let answer = 0; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); // 몫만 남긴다 const book = books[mid - 1]; // mid번째 자리는 배열의 mid - 1번 칸 seen.push(book); if (book === x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } seen.push(answer); out.push(seen.join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 26 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q]: number[] = lines[0].trim().split(/\s+/).map(Number);const books: number[] = lines[1].trim().split(/\s+/).map(Number);const queries: number[] = lines[2].trim().split(/\s+/).map(Number);const out: string[] = [];for (let k = 0; k < q; k++) { const x: number = queries[k]; let lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 const seen: number[] = []; // 펼쳐 본 책 번호 let answer = 0; while (lo <= hi) { const mid: number = Math.floor((lo + hi) / 2); // 몫만 남긴다 const book: number = books[mid - 1]; // mid번째 자리는 배열의 mid - 1번 칸 seen.push(book); if (book === x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } seen.push(answer); out.push(seen.join(" "));}console.log(out.join("\n"));
JavaMain.java · 29 줄
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), q = sc.nextInt(); int[] books = new int[n]; for (int i = 0; i < n; i++) books[i] = sc.nextInt(); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { int x = sc.nextInt(); int lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 int answer = 0; while (lo <= hi) { int mid = (lo + hi) / 2; // int끼리 나누면 몫만 남는다 int book = books[mid - 1]; // mid번째 자리는 배열의 mid - 1번 칸 out.append(book).append(' '); if (book == x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } out.append(answer).append('\n'); } System.out.print(out); }}
C#Main.cs · 37 줄
using System;using System.Text;class Program{ static void Main() { string[] head = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(head[0]), q = int.Parse(head[1]); string[] bookParts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); string[] queryParts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int[] books = new int[n]; for (int i = 0; i < n; i++) books[i] = int.Parse(bookParts[i]); var sb = new StringBuilder(); for (int k = 0; k < q; k++) { int x = int.Parse(queryParts[k]); int lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 int answer = 0; while (lo <= hi) { int mid = (lo + hi) / 2; // int끼리 나누면 몫만 남는다 int book = books[mid - 1]; // mid번째 자리는 배열의 mid - 1번 칸 sb.Append(book).Append(' '); if (book == x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } sb.Append(answer).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 27 줄
#include <iostream>#include <vector>int main() { int n, q; std::cin >> n >> q; std::vector<int> books(n); for (int i = 0; i < n; i++) std::cin >> books[i]; for (int k = 0; k < q; k++) { int x; std::cin >> x; int lo = 1, hi = n; // 아직 찾아볼 자리의 처음과 끝 int answer = 0; while (lo <= hi) { int mid = (lo + hi) / 2; // int끼리 나누면 몫만 남는다 int book = books[mid - 1]; // mid번째 자리는 vector의 mid - 1번 칸 std::cout << book << " "; if (book == x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } std::cout << answer << "\n"; }}
Cmain.c · 29 줄
#include <stdio.h>int main(void) { int n, q; int books[100]; if (scanf("%d %d", &n, &q) != 2) return 0; for (int i = 0; i < n; i++) { if (scanf("%d", &books[i]) != 1) return 0; } for (int k = 0; k < q; k++) { int x; if (scanf("%d", &x) != 1) return 0; int lo = 1, hi = n; /* 아직 찾아볼 자리의 처음과 끝 */ int answer = 0; while (lo <= hi) { int mid = (lo + hi) / 2; /* int끼리 나누면 몫만 남는다 */ int book = books[mid - 1]; /* mid번째 자리는 배열의 mid - 1번 칸 */ printf("%d ", book); if (book == x) { answer = mid; break; } if (book < x) lo = mid + 1; else hi = mid - 1; } printf("%d\n", answer); } return 0;}
Craykonmain.cray · 32 줄
head = 콘솔.수들읽기();n = head[0];books = 콘솔.수들읽기();queries = 콘솔.수들읽기();각각 (x 에서 queries){ lo = 1; // 아직 찾아볼 자리의 처음과 끝 hi = n; seen = []; // 펼쳐 본 책 번호 answer = 0; 동안 (lo <= hi) { mid = 수학.몫(lo + hi, 2); // 몫만 남긴다 book = books[mid - 1]; // mid번째 자리는 목록의 mid - 1번 칸 seen.넣기(book); 만약 (book == x) { answer = mid; 그만; } 만약 (book < x) { lo = mid + 1; } 아니면 { hi = mid - 1; } } seen.넣기(answer); 콘솔.쓰기(seen); // 목록은 빈칸으로 이어서 쓴다}