공연장에 입구가 A와 B 두 곳 있다.
입구마다 들어온 관람객의 입장 시각(초)이 들어온 차례대로 적혀 있다. 그래서 두 기록은 각각 작은 시각부터 차례로 놓여 있다(같은 시각이 여럿일 수 있다).
두 기록을 합쳐 입장 시각 순서로 명단 하나를 만든다.
시각이 같으면 A 입구 관람객이 B 입구 관람객보다 앞에 온다. 같은 입구 관람객끼리는 원래 기록의 차례를 지킨다.
명단의 맨 앞이 1번이다.
첫째 줄에 A 입구 관람객들의 명단 번호를 A 기록의 차례대로 빈칸 하나씩 띄워 출력하라.
둘째 줄에 B 입구 관람객들의 명단 번호를 B 기록의 차례대로 같은 방식으로 출력하라.
입력의 첫 줄에 A 기록의 수 n과 B 기록의 수 m이, 둘째 줄에 A의 시각 n개가, 셋째 줄에 B의 시각 m개가 주어진다.
입력
1 ≤ n, m ≤ 10,000, 0 ≤ 시각 ≤ 1,000,000,000(정수). 각 줄의 시각은 작아지지 않는 차례로 주어진다
출력
두 줄: A 관람객들의 명단 번호, B 관람객들의 명단 번호
예시 1 · stdin
4 3
5 9 9 120
3 9 40
stdout
2 3 4 7
1 5 6
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
두 기록이 이미 정렬돼 있으니, 두 기록에 손가락(자리 i, j)을 하나씩 두고 더 이른 쪽을 명단에 넣으며 그쪽 손가락만 한 칸 옮기면 n + m번에 끝나요. 같은 시각이면 A가 먼저라서 A를 고르는 조건은 a[i] <= b[j]예요. <로 쓰면 같은 시각에 B가 먼저 들어가요. 한쪽 기록이 먼저 끝나면 남은 쪽을 모두 뒤에 붙여야 해요. while (i < n && j < m)만 돌고 멈추면 꼬리가 빠지니, 조건을 j == m || (i < n && a[i] <= b[j])로 써서 한 반복에서 끝까지 처리해요. 이때 i < n을 먼저 물어야 다 쓴 기록의 범위 밖을 읽지 않아요(&&는 앞이 거짓이면 뒤를 보지 않아요. 순서를 바꿔 a[i] <= b[j] && i < n으로 쓰면 Python·Java·C#·크레이콘은 범위 밖 오류로 멈춰요). 모아서 정렬해도 되지만 JS·TS의 sort()는 비교 함수가 없으면 문자열로 바꿔 사전 순으로 놓아서 100이 9보다 앞에 와요. Java에서 List<Integer>의 두 값을 ==로 비교하면 같은 객체인지를 봐서, -128~127 밖의 같은 시각이 다르다고 나와요. int[]에 담거나 equals, intValue()를 써요. 줄 하나에 수를 빈칸으로 이어 쓸 때 Python print(*pos), JS·TS·C# join(" "), 크레이콘 콘솔.쓰기(목록)은 사이에만 빈칸을 넣고, C·C++·Java는 첫 수 앞에 빈칸이 생기지 않게 직접 챙겨요.
Pythonmain.py · 18 줄
n, m = map(int, input().split())a = list(map(int, input().split()))b = list(map(int, input().split()))pos_a, pos_b = [], []i = j = 0place = 1while i < n or j < m: # A를 고르는 때: B가 다 끝났거나, A의 시각이 B보다 이르거나 같을 때(같으면 A가 먼저) if j == m or (i < n and a[i] <= b[j]): pos_a.append(place) i += 1 else: pos_b.append(place) j += 1 place += 1print(*pos_a)print(*pos_b)
JavaScriptmain.js · 17 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, m] = lines[0].trim().split(/\s+/).map(Number);const a = lines[1].trim().split(/\s+/).map(Number);const b = lines[2].trim().split(/\s+/).map(Number);const posA = [], posB = [];let i = 0, j = 0;for (let place = 1; place <= n + m; place++) { // B가 끝났거나 A가 이르거나 같으면 A가 먼저 if (j === m || (i < n && a[i] <= b[j])) { posA.push(place); i++; } else { posB.push(place); j++; }}console.log(posA.join(" ") + "\n" + posB.join(" "));
TypeScriptmain.ts · 17 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, m] = lines[0].trim().split(/\s+/).map(Number);const a: number[] = lines[1].trim().split(/\s+/).map(Number);const b: number[] = lines[2].trim().split(/\s+/).map(Number);const posA: number[] = [], posB: number[] = [];let i = 0, j = 0;for (let place = 1; place <= n + m; place++) { if (j === m || (i < n && a[i] <= b[j])) { posA.push(place); i++; } else { posB.push(place); j++; }}console.log(posA.join(" ") + "\n" + posB.join(" "));
JavaMain.java · 33 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int[] readInts(BufferedReader br, int k) throws Exception { StringTokenizer st = new StringTokenizer(br.readLine()); int[] r = new int[k]; for (int t = 0; t < k; t++) r[t] = Integer.parseInt(st.nextToken()); return r; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()); int[] a = readInts(br, n), b = readInts(br, m); // int[]라 ==가 값을 비교한다 StringBuilder outA = new StringBuilder(), outB = new StringBuilder(); int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { if (j == m || (i < n && a[i] <= b[j])) { if (outA.length() > 0) outA.append(' '); outA.append(place); i++; } else { if (outB.length() > 0) outB.append(' '); outB.append(place); j++; } } System.out.print(outA + "\n" + outB + "\n"); }}
C#Main.cs · 31 줄
using System;using System.Collections.Generic;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]), m = int.Parse(first[1]); int[] a = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse); int[] b = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse); var posA = new List<int>(n); var posB = new List<int>(m); int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { if (j == m || (i < n && a[i] <= b[j])) { posA.Add(place); i++; } else { posB.Add(place); j++; } } Console.WriteLine(string.Join(" ", posA)); Console.WriteLine(string.Join(" ", posB)); }}
C++main.cpp · 30 줄
#include <iostream>#include <vector>void printLine(const std::vector<int>& p) { for (size_t t = 0; t < p.size(); t++) std::cout << (t ? " " : "") << p[t]; std::cout << "\n";}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> a(n), b(m); for (int& x : a) std::cin >> x; for (int& x : b) std::cin >> x; std::vector<int> posA, posB; int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { if (j == m || (i < n && a[i] <= b[j])) { posA.push_back(place); i++; } else { posB.push_back(place); j++; } } printLine(posA); printLine(posB);}
Cmain.c · 28 줄
#include <stdio.h>static int a[10000], b[10000];static int pos_a[10000], pos_b[10000];static void print_line(const int *p, int k) { for (int t = 0; t < k; t++) printf(t ? " %d" : "%d", p[t]); printf("\n");}int main(void) { int n, m; scanf("%d %d", &n, &m); for (int t = 0; t < n; t++) scanf("%d", &a[t]); for (int t = 0; t < m; t++) scanf("%d", &b[t]); int i = 0, j = 0; for (int place = 1; place <= n + m; place++) { /* B가 끝났거나 A가 이르거나 같으면 A가 먼저 */ if (j == m || (i < n && a[i] <= b[j])) { pos_a[i++] = place; } else { pos_b[j++] = place; } } print_line(pos_a, n); print_line(pos_b, m); return 0;}
Craykonmain.cray · 27 줄
first = 콘솔.수들읽기();n = first[0];m = first[1];a = 콘솔.수들읽기();b = 콘솔.수들읽기();posA = [];posB = [];i = 0;j = 0;반복 (place = 1; place <= n + m; place++){ // B가 끝났거나, A가 남아 있고 A의 시각이 이르거나 같으면 A가 먼저 // &&는 앞이 거짓이면 뒤를 보지 않으니 i < n을 먼저 묻는다 takeA = j == m || i < n && a[i] <= b[j]; 만약 (takeA) { posA.넣기(place); i++; } 아니면 { posB.넣기(place); j++; }}콘솔.쓰기(posA);콘솔.쓰기(posB);