[BaekJoon] #10810 - 공 넣기 [Java][C++]

문제 링크

---

1. 아이디어

주어진 바구니들에 대해 주어진 구간에 특정 번호의 공을 넣는 과정을 반복할 때, 최종적으로 바구니에 들어있는 공의 번호를 출력하는 문제다. 바구니들을 배열로 간주하고 주어진 구간에 공의 번호를 덮어씌우는 과정을 반복하면 해결할 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times M)$	$O(N)$

($N$ = 입력값 n, $M$ = 입력값 m)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            Arrays.fill(arr, s - 1, e, x);
        }

        for (int x : arr) {
            sb.append(x).append(" ");
        }

        System.out.println(sb);
    }
}

Arrays.fill 메서드로 주어진 구간을 공의 번호로 채우는 방식으로 구현했다. 이때 첫 인덱스가 0인 것과 Arrays.fill 메서드는 시작 위치는 포함하고 끝 위치는 포함하지 않는 것에 주의해야 한다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> v(n);
    while (m--) {
        int s, e, x;
        cin >> s >> e >> x;
        fill(v.begin() + s - 1, v.begin() + e, x);
    }

    for (int x : v) {
        cout << x << ' ';
    }
}

std::fill 함수를 활용해 벡터에서 해당 구간에 공의 번호를 넣었다. 이때 첫 인덱스가 0인 것과 std::fill 함수는 시작 위치는 포함하고 끝 위치는 포함하지 않는 것에 주의해야 한다.

---