{ }codelper
두 포인터P0260

두 입구의 입장 기록 합치기

공연장에 입구가 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
입력(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);