[백준] 10810 공 넣기 (설명/코드/정답)

 

문제 링크 : https://www.acmicpc.net/problem/10810

 

1. 요구 사항 이해

시간, 메모리 제한 : 1초 / 256 MB

 

바구니와 공: 

총 N개의 바구니가 있고, 각 바구니에는 1부터 N까지의 번호가 있습니다. 모든 바구니는 처음에는 비어 있습니다. 1부터 N까지 번호가 적힌 공을 사용할 수 있습니다.

공을 넣는 작업: 

M번의 작업이 주어지며, 각 작업은 다음과 같은 형식입니다:
i j k: i번 바구니부터 j번 바구니까지 공의 번호가 k인 공을 넣습니다.
바구니에는 한 번에 하나의 공만 넣을 수 있으며, 공이 이미 있는 바구니에 새로운 공을 넣으면 기존의 공이 사라집니다.
출력: 모든 바구니에 현재 들어있는 공의 번호를 공백으로 구분하여 출력합니다. 공이 들어있지 않은 바구니는 0을 출력합니다.

 

 

• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 100
• 1 ≤ i ≤ j ≤ N
• 1 ≤ k ≤ N

 

 

 

2. 설계/검증 

 

복잡도

시간 복잡도	최악의 경우	공간 복잡도
O(M * N)		O(N)

 

입력 처리: O(M), 바구니 업데이트: O(M * N) 결과 출력: O(N)

M개의 공 넣기 작업을 고려하면 최악의 경우 각 공을 넣는 작업이 O(N)일 수 있습니다. 

즉, 모든 공 넣기 작업을 합치면 O(M * N) 시간 복잡도는 O(M * N)

 

int[] baskets = new int[N]; 배열을 생성하여 N개의 정수를 저장합니다. 공간 복잡도는 O(N)  

 

 

 

 

3. 정상 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        // 입력을 위한 객체 생성
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt(); // 바구니의 개수
        int M = scan.nextInt(); // 공을 넣는 방법의 수

        // N, M 유효성 검사
        if (N < 1 || N > 100 || M < 1 || M > 100) {
            System.out.println("N의 범위 1 ≤ N ≤ 100, M의 범위 1 ≤ M ≤ 100");
            return;
        }

        // 바구니 상태를 저장할 배열 생성, 초기화 0인 상태
        int[] baskets = new int[N];


       for (int x = 0; x < M; x++) {
            int i = scan.nextInt(); // 시작 바구니 번호
            int j = scan.nextInt(); // 끝 바구니 번호
            int k = scan.nextInt(); // 공의 번호

           // 입력된 i, j, k의 유효성 검사
           if (i < 1 || i > N || j < 1 || j > N || i > j || k < 1 || k > N) {
               System.out.println("(1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ N)");
               return;
           }

            // i번 바구니부터 j번 바구니까지 k의 공 넣음
            for (int idx = i-1; idx < j; idx++) {
                baskets[idx] = k;
            }
        }

        // 결과 출력
        for (int basket : baskets) {
            System.out.print(basket + " ");
        }

        scan.close();
    }
}