[백준] 10810번 : 공 넣기 - JAVA 문제

출처: 백준의 알고리즘[백준] 10810번 : 공 넣기 - JAVA 문제

백준의 알고리즘[백준] 10810번 : 공 넣기 - JAVA 문제

---

1. 문제 개요

• 바구니 개수: N개(1번~N번)
• 초기 상태: 모든 바구니는 비어 있음(값 0)
• 작업 횟수: M번
• 한 번 작업
  1. 연속 구간 i번 바구니부터 j번 바구니까지 선택
  2. 번호 k인 공을 넣음(이미 공이 있으면 덮어쓰기)
• 최종 출력: 1번~N번 바구니에 남아 있는 공 번호를 공백으로 구분하여 한 줄에 출력

---

2. 설계 및 클래스 구조

2.1. Basket (한 개의 바구니)

• 역할: “바구니 하나”의 상태(마지막으로 넣은 공 번호)를 관리
• 필드
  • int lastValue – 현재 바구니에 들어있는 공 번호
• 메서드
  • setValue(int k) – 공 번호를 k로 덮어쓰기
  • getLast(): int – 현재 공 번호 반환

static class Basket {
    private int lastValue;

    public Basket() {
        this.lastValue = 0;    // 초기값: 빈 상태(0)
    }

    // k로 덮어쓰기
    public void setValue(int k) {
        this.lastValue = k;
    }

    // 마지막 상태 조회
    public int getLast() {
        return lastValue;
    }
}

 

2.2. BasketGroup (여러 바구니 묶음)

• 역할: N개의 Basket을 생성·관리하고, “구간 덮어쓰기” 명령을 수행
• 필드
  • List<Basket> baskets – 내부에 N개의 Basket 객체 보유
• 메서드
  • BasketGroup(int n) – N개 바구니 초기화
  • applyCommand(int start, int end, int k)
    • 1-based 구간 [start..end]의 모든 바구니에 setValue(k) 적용
  • getFinalStates(): List<Integer>
    • 각 바구니의 getLast() 결과를 모아 반환

static class BasketGroup {
    private final List<Basket> baskets;

    // N개의 바구니 생성
    public BasketGroup(int n) {
        baskets = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            baskets.add(new Basket());
        }
    }

    // 구간 덮어쓰기: [start..end]에 k 적용
    public void applyCommand(int start, int end, int k) {
        for (int idx = start - 1; idx < end; idx++) {
            baskets.get(idx).setValue(k);
        }
    }

    // 최종 각 바구니 상태 반환
    public List<Integer> getFinalStates() {
        List<Integer> result = new ArrayList<>(baskets.size());
        for (Basket b : baskets) {
            result.add(b.getLast());
        }
        return result;
    }
}

---

3. 실행 흐름 (Main 클래스)

(1) 입력 처리

• 첫 줄: N M
• 다음 M줄: 각각 i j k

(2) 바구니 그룹 초기화

• BasketGroup group = new BasketGroup(n);

(3) 명령 순차 수행

• for (int t = 0; t < m; t++) { // i, j, k 파싱 후 group.applyCommand(i, j, k); }

(4) 결과 수집 및 출력

• List<Integer> finalStates = group.getFinalStates(); // StringBuilder로 한 줄에 공백 구분 출력

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

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

        BasketGroup group = new BasketGroup(n);

        // M개의 작업 수행
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            group.applyCommand(
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken())
            );
        }

        // 최종 상태 출력
        StringBuilder sb = new StringBuilder();
        for (int val : group.getFinalStates()) {
            sb.append(val).append(' ');
        }
        System.out.println(sb.toString().trim());
        br.close();
    }
}

---

4. 시간·공간 복잡도

• 시간 복잡도
  • 각 명령 applyCommand는 구간 길이 L = end-start+1 만큼 반복 → 최악 O(N)
  • 명령 M회 수행 → O(M·N)
  • 최종 상태 수집 → O(N)
  • 총합: O(M·N + N) = O(M·N) (N, M ≤ 100 → 충분히 빠름)
• 공간 복잡도
  • BasketGroup 내부에 N개의 Basket → O(N)
  • 추가 구조체(List<Integer> 등)도 모두 O(N) 규모

---

5. 결론

• 객체 지향 설계로 각 바구니(Basket)와 그룹(BasketGroup)의 책임을 분리
• 시간·공간 효율성은 원리 그대로 유지 (O(M·N)), N, M ≤ 100의 제약하에서는 충분히 적합
• 간단한 구간 덮어쓰기 문제를 클래스 역할 분리와 명확한 메서드로 깔끔하게 구현할 수 있음