[백준] '공 넣기' - Java

<문제 제시>

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 들어있지 않으며, 바구니에는 공을 1개만 넣을 수 있다.

도현이는 앞으로 M번 공을 넣으려고 한다. 도현이는 한 번 공을 넣을 때, 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약, 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고, 새로 공을 넣는다. 공을 넣을 바구니는 연속되어 있어야 한다.

공을 어떻게 넣을지가 주어졌을 때, M번 공을 넣은 이후에 각 바구니에 어떤 공이 들어 있는지 구하는 프로그램을 작성하시오.

---

<문제 해결 과정>

N은 바구니의 개수, M은 테스트케이스의 개수이어서 현재 문제에서는 5 4 가 주어졌으므로 

5번바구니까지 있고, 4번의 테스트케이스가 주어진다는 의미이다.

테스트케이스가 1 2 3 이면 1~2번바구니까지 3번 공을 넣겠다는 의미이다.

이렇게 되면

0 0 0 0 0 이던 바구니가 3 3 0 0 0 처럼 초기화 된다.

---

<Try 1>

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[] data = new int[N];

// 값 넣기 로직 (오답의 원인?) >> 지워봐도 오답
int k = 1;
for(int i = 0; i < N; i++) {
    data[i] = k;
    k++;
}

//System.out.println(Arrays.toString(data));

Set<Integer> remove = new HashSet<>();

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

    int I = Integer.parseInt(st.nextToken()) - 1;
    int J = Integer.parseInt(st.nextToken()) - 1;
    int K = Integer.parseInt(st.nextToken()); // 3


    remove.add(K);

    for(int j = I; j <= J; j++) {
        data[j] = K;
        //System.out.println(Arrays.toString(data));
    }
}

List<Integer> list = new ArrayList<>(remove);// set->list

//		System.out.println("HashSet = " + remove);
//		System.out.println("List = " + list);

int no_ball = 0;
for(int i = 0; i < data.length; i++) {
    for(int j = 0; j < list.size(); j++) {
        if(data[i] != list.get(j)) {
            no_ball = i;
        }
    }
}

// 공이 담기지 않은 바구니
data[no_ball] = 0;

// 결과 출력문
for(int i = 0; i < data.length; i++) {
    if(i == data.length - 1) {
        System.out.print(data[i]);
        break;
    }
    System.out.print(data[i] + " ");
}

//		Testcase) [1,2,3,4,5]
//		1~2번째 공을 모두 3번으로 >> 3 3 3 4 5
//		3~4번째 공을 모두 4번으로 >> 3 3 4 4 5
//		1~4번째 공을 모두 1번으로 >> 1 1 1 1 5
//		2~2번째 공을 모두 2번으로 >> 1 2 1 1 5

문제에서 주어지기를 바구니에 공이 담겨있으면 새로운 공으로 갱신해주므로

덮어쓰기 방식으로 업데이트해 나가야한다.

이번에도 I, J, K가 주어지면 인덱스가 아닌 순서로 값이 주어지므로 I와 J 의 경우 -1을 해주어

인덱스를 의미하게 해주어야한다.

해시셋과 리스트 자료형을 통하여서도 풀어보고자했지만 오답이었다.

---

<Answer 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 value = Integer.parseInt(st.nextToken());

    for(int j = start - 1; j < end; j++) {
        data[j] = value;
    }
}

StringTokenizer()을 통해 I, J, K값을 입력받고

data배열을 K값으로 초기화해주고, M의 테스트케이스만큼 이 반복을 수행한다.

---

<전체 코드>

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

public class q_10810_putball {

	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[] data = new int[N];
		
		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 value = Integer.parseInt(st.nextToken());
			
			for(int j = start - 1; j < end; j++) {
				data[j] = value;
			}
		}
		
		for(int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
	}
}

---

불필요한 함수사용 없이 StringTokenizer() 사용으로 해결이 가능한 문제였다.

---

<문제 링크>

https://www.acmicpc.net/problem/10810