공 넣기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 256 MB | 59382 | 31279 | 27897 | 53.363% |
문제
도현이는 바구니를 총 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을 출력한다.
풀이✔
1️⃣ 문제 분석하기
- 바구니 N개를 가지고 있다.
- 각 바구니 별로 1번 ~ N번까지 번호가 매겨져 있다.
- 1번부터 N번까지 번호가 적혀있는 공을 많이가지고 있음.
- 맨처음 바구니에는 공이 없고, 바구니에는 공을 1개만 넣을 수 있다.
- 앞으로 M번 공을 넣으려고 한다.
- 한번 공을 넣을 떄 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고 새로 공을 넣음.
2️⃣ 요구 조건 구현하기
- 바구니 개수 N 선언
- 몇개의 줄에 걸쳐서 넣을지 변수 M 선언
- 바구니가 0부터 시작이 아닌 1부터 시작이기 떄문에 +1을 해줘야함.
- 정수 i j k 배열 선언한 후 for문으로 채우기
- 2중 for문으로 한번더 for문에 조건을 줘야함.
- 두번째 조건에는 1부터 2까지 닌까 중간 숫자 까지 for문을 돌린다.
3️⃣ 슈도 코드
BufferedReader 선언
StringTokeinizer 선언
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] baskets = new int[N+1] //담아서 출력할 바구니 합계
for(int i=0; i<M; i++) {
st = new StringTokeinizer(bf.readLine());
변수 3개 받기
for문() {
조건주기
}
for문 통해 출력하기
}
4️⃣ 코드 작성
package 알고리즘;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class B10810 {
public static void main(String[] args) throws IOException {
BufferedReader bf =new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] baskets = new int[N+1]; //바구니 시작이 1번부터라서 +1 해줌
for (int a = 0; a <M ; a++) {
st = new StringTokenizer(bf.readLine());
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
for (int l = i; l <=j ; l++) { //시작 은 i, 마지막은j 를 해야함
baskets[l] = k;
}
}
for (int i = 1; i <=N ; i++) {
System.out.print(baskets[i] + " ");
}
}
}
🖐 Help
int[] baskets = new int[N+1]; //바구니 시작이 1번부터라서 +1 해줌
위 코드는 바구니를 시작하는 번호가 1부터 시작이라서 N+1을 해줬다
0부터 시작한다고하면 01234 로 나열이 되고
1부터 시작해야지 12345 대로 순번이 적용이 된다.
for (int l = i; l <=j ; l++) { //시작 은 i, 마지막은j 를 해야함
baskets[l] = k;
}
- 위 코드의 핵심은, i j k 번호를 입력 받고 ( i는 시작번호, j는 범위, k는 무슨 번호를 넣을건지)이기 때문에 위 조건을 꼭 기억하고 있어야 한다.
- basktes[시작번호] = 넣을 번호 를 해야지 바구니에 번호가 채워진다
- j 범위를 통해 몇번 바꾸니 까지 번호를 채울건지를 정한다.
- basktes[시작번호] = 넣을 번호 를 해야지 바구니에 번호가 채워진다
자세하게 더 설명을 하면
5 4
1 2 3
3 4 4
1 4 1
2 2 2
- 초기 바구니 상태: [0, 0, 0, 0, 0]
- 첫 번째 조건: 1번 바구니부터 2번 바구니까지에 3번 공을 넣음 → [3, 3, 0, 0, 0]
- 두 번째 조건: 3번 바구니부터 4번 바구니까지에 4번 공을 넣음 → [3, 3, 4, 4, 0]
- 세 번째 조건: 1번 바구니부터 4번 바구니까지에 1번 공을 넣음 → [1, 1, 1, 1, 0]
- 네 번째 조건: 2번 바구니에 2번 공을 넣음 → [1, 2, 1, 1, 0]
이렇게 설명을 할 수 있다.
for (int i = 1; i <=N ; i++) {
System.out.print(baskets[i] + " ");
}
배열의 출력은 기본적으로 for문을 통해서 하는 것이 편하다.
배열을 toString으로 출력을 하면은 배열의 해쉬코드가 나온다.
5️⃣ 핵심 파악하기
배열의 성질과 for문을 돌리고 조건을 어떻게 줄지를 잘 파악해야하는 문제이다.