백준 - 10810번: 공넣기

문제 출처

문제 출처 : 10810번: 공넣기

문제 이해하기

• 도현이는 바구니를 총 N개 가지고 있습니다. 이 말은 1 ~ N개의 바구니를 소유하고 있다는 이야기와 동일합니다.

• 또한 1번부터 N번까지 번호가 적힌 공을 많이 가지고 있습니다.

  • ex) N = 5 --> 1번 공, 2번 공, 3번 공, 4번 공, 5번 공

• 이렇게 준비된 상태에서 M번 공을 넣을 예정입니다. 여기서 M은 공을 넣는 횟수를 의미합니다. 즉 M = 4 일 때 바구니에 공을 넣는 행동을 4번 한다는 뜻입니다.

• 그런데 공을 넣을 땐 바구니의 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣고, 만약 공이 이미 존재할 경우, 들어있는 공을 빼고, 새로 공을 넣습니다. 공을 넣을 바구니는 연속되어 있다고 나와있습니다.

저는 개인적으로 굵게 강조한 문장들을 이해하는데 30분 이상 허비했습니다.. 🥹

문제의 나와있는 입력 예시로 설명해드리겠습니다.

주요 조건 이해하기 ⭐️

• 공을 넣을 때 바구니의 범위를 정한다
  • 1번 바구니부터 2번 바구니까지 공을 넣겠다는 의미입니다.
• 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다
  • 1번 바구니부터 2번 바구니까지 3번 공을 넣는다는 의미입니다.
• 공을 넣을 바구니는 연속되어 있다
  • 자료를 연속된 형태로 저장할 수 있는 배열을 사용하라는 의미입니다.

만약 공이 이미 존재할 경우, 들어있는 공을 빼고, 새로 공을 넣는다는 문장이 적혀있지만 들어오는 공을 뺄 때 어떤 조건으로 빼는지에 대한 설명이 나와있지 않기 때문에 위에 그림과 같이 단순히 replace만 해주면 되는 부분입니다

알고리즘 선정

특별한 알고리즘이 필요하지 않고, 단순히 for문만으로 문제를 해결할 수 있습니다.

스켈레톤 코드

int N, M; // 입력받을 N, M에 대한 변수
int[] buckets; // N만큼의 크기를 가진 배열 

void insertBall(int start, int end, int ballNumber) {
	for(int i = start; i <= end; i++) {
		nums[start] = ballNumber;
	}
}

최종 소스 파일

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_10810 {

	static int N, M;
	static int[] buckets;
	static StringBuilder sb = new StringBuilder();

	static void insertBall(int start, int end, int ballNumber) {
		for (int i = start; i <= end; i++) {
			buckets[i] = ballNumber;
		}
	}

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		buckets = new int[N + 1];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int ballNumber = Integer.parseInt(st.nextToken());

			insertBall(start, end, ballNumber);
		}

		printBallNumber();

	}

	static void printBallNumber() {
		for (int i = 1; i <= N; i++) {
			sb.append(buckets[i]).append(" ");
		}

		System.out.println(sb.toString());
	}

}