[BaekJoon] 10810번 - 공 넣기 (java)

📌 1. 문제

👉 문제 바로가기

- 조건

시간 제한	메모리 제한
1초	256MB

- 문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 들어있지 않으며, 바구니에는 공을 1개만 넣을 수 있다.
도현이는 앞으로 M번 공을 넣으려고 한다. 도현이는 한 번 공을 넣을 때, 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약, 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고, 새로 공을 넣는다. 공을 넣을 바구니는 연속되어 있어야 한다.
공을 어떻게 넣을지가 주어졌을 때, M번 공을 넣은 이후에 각 바구니에 어떤 공이 들어 있는지 구하는 프로그램을 작성하시오.

- 입력

도현이는 입력으로 주어진 순서대로 공을 넣는다. 첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.
둘째 줄부터 M개의 줄에 걸쳐서 공을 넣는 방법이 주어진다. 각 방법은 세 정수 i j k로 이루어져 있으며, i번 바구니부터 j번 바구니까지에 k번 번호가 적혀져 있는 공을 넣는다는 뜻이다. 예를 들어, 2 5 6은 2번 바구니부터 5번 바구니까지에 6번 공을 넣는다는 뜻이다. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ N)

- 출력

1번 바구니부터 N번 바구니에 들어있는 공의 번호를 공백으로 구분해 출력한다. 공이 들어있지 않은 바구니는 0을 출력한다.

- 예제

입력	출력
5 4 1 2 3 3 4 4 1 4 1 2 2 2	1 2 1 1 0

---

📌 2. 풀이

2-0. 알고리즘

1번 바구니부터 N번 바구니까지 순서대로 바구니에 들어있는 공의 번호를 출력해야 하기 때문에,
배열을 사용해 공의 번호를 저장한다.

배열은 인덱스 0부터 시작하기 때문에 1번 바구니 공은 인덱스 0에, 2번 바구니 공은 인덱스 1에,
N번 바구니 공은 인덱스 N-1에 저장하면 된다.

따라서, for 문을 사용해 인덱스 i-1 부터 j-1 까지의 값에 k를 저장한다.

int[] arr = new int[N];

for(int b=i-1;b<j;b++) {
    arr[b] = k;
}

2개의 입력방식과 3개의 출력방식을 사용해서 결과를 출력한다.

1. Scanner 클래스
2. BufferedReader 클래스

2-1. Scanner 클래스

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
 
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] arr = new int[N];
		
		for(int a=0;a<M;a++) {
			int i = sc.nextInt();
			int j = sc.nextInt();
			int k = sc.nextInt();
			
			for(int b=i-1;b<j;b++) {
				arr[b] = k;
			}
		}
		for(int num : arr) {
			System.out.print(num + " ");
		}
	}
}

위와같이 객체를 생성할 때, Scanner(System.in) 에서 System.in 은 입력한 값을 Byte 단위로 읽는 것을 뜻한다.

int형 데이터를 입력받기 위해 nextInt() 메서드를 사용한다.

확장 for 문 을 사용해 배열의 값을 모두 출력한다.

[여기서 잠깐!]

Scanner에 대해 더 자세히 알고싶다면 여기 를 클릭하세요

2-2. BufferedReader 클래스 사용

3가지 출력 방식으로 문제를 풀어보고 비교해보자.



     ① System.out.println()
     ② BufferedWriter
     ③ StringBuilder

① BufferedReader + System.out.println()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
 
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());
		
		int[] arr = new int[N];
		
		for(int a=0;a<M;a++) {
            st = new StringTokenizer(br.readLine());
            
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			
			for(int b=i-1;b<j;b++) {
				arr[b] = k;
			}
		}
		for(int num : arr) {
			System.out.print(num + " ");
		}
		br.close();
	}
 
}

StringTokenizer 클래스를 사용해 “ “ (공백)을 기준으로 값을 구분하고, nextToken()를 사용해 공백으로 구분된 입력값들을 순서대로 가져온다.

Integer.parseInt()을 사용해 String형을 int형으로 변환시켜준다.

② BufferedReader + BufferedWriter

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[N];
		
		for(int a=0;a<M;a++) {
            st = new StringTokenizer(br.readLine());
            
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			
			for(int b=i-1;b<j;b++) {
				arr[b] = k;
			}
		}
		for(int num : arr) {
			bw.write(num + " ");
		}
		br.close();
        bw.flush();
        bw.close();
    }
}

BufferedWriter 클래스의 write() 메소드는 데이터를 내부 버퍼에 저장하고, flush() 메소드 를 사용해 버퍼를 비우고 데이터를 출력한다.

BufferedWriter 클래스의 write() 메소드는 단독으로 int 형 값만 넣을 경우 아스키 코드값으로 인식되기 때문에 다른 문자가 출력된다. 때문에 반드시 문자열과 int 형을 함께 넣어줘야 int 값을 제대로 출력할 수 있다.

[여기서 잠깐!]

BufferedReader／BufferedWriter 클래스에 대해 더 알아보고 싶으면 여기를 클릭하면 된다.

③ BufferedReader + StringBuilder

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

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());
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[N];
		
		for(int a=0;a<M;a++) {
            st = new StringTokenizer(br.readLine());
            
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			
			for(int b=i-1;b<j;b++) {
				arr[b] = k;
			}
		}
		for(int num : arr) {
			sb.append(num).append(" ");
		}
        System.out.println(sb);
    }
}

StringBuilder 클래스는 문자열을 동적으로 조작하기 위한 클래스로, append() 를 사용해 문자열을 추가하여 새로운 문자열을 생성한다.

append() 를 위와 같이 나눠서 쓰면 타입 변환과 문자열 연결 연산이 추가적으로 발생하지 않고 StringBuilder에 직접 추가하기 때문에 보다 더 효율적이고 빠르다.

---

📌 3. 성능 비교

위에서 부터 순서대로

BufferedReader + StringBuilder
BufferedReader + BufferedWriter
BufferedReader + System.out.println()
Scanner

위와같이 입력 메소드와 알고리즘 구현 방법에 따라 시간이 달라질 수 있다.

입력의 경우 확실히 Scanner 보다는 BufferedReader 가 빠른 것을 볼 수 있다.

출력의 경우 StringBuilder 가 제일 빠르다.
BufferedWriter는 일반적으로 I/O 작업으로 인해 비교적 느릴 수 있다.
반면에 StringBuilder는 문자열 조작에 최적화된 클래스로, 문자열 연산은 일반적으로 메모리 상에서 수행되므로 상대적으로 빠를 수 있다.

관련 페이지

• Scanner 클래스
• BufferedReader/BufferedWriter 클래스