✨ 백준 16396번
✨ 문제 해석
1️⃣ 준섭이가 그린 선의 개수 N이 주어지고 두 번째 줄부터 N+1번째 줄까지는 X_i와 Y_i가 공백을 기준으로 주어진다.
✔️ BufferedReader 클래스를 이용하여 입력을 받는다. BufferedReader 클래스는 버퍼를 이용하는 I/O(Input/Output) 클래스이다. 즉 버퍼에 저장해두었다가 전달하는 방법으로, 입력된 데이터를 바로바로 전달하지 않는다. 따라서 공백을 인식하지 않고 Enter만을 인식하는 특징을 가진다. 하지만 선의 개수(N)가 입력된 후, 시작 좌표와 끝 좌표가 같은 줄에 공백을 기준으로 입력된다.
👉🏻 따라서 이때 StringTokenizer 객체가 필요하다.
StringTokenizer
public StringTokenizer(String str);
- 매개변수로 전달된 문자열 str을 default delim으로 분리한다. 여기서 default delim은 공백 문자들인 '\t\n\r\t'이다.
public StringTokenizer(String str, String delim);
- 바로 위에서처럼 delim(구분자)도 함께 전달하면 해당 구분자를 기준으로 문자열 str를 분리한다.
👉🏻 여기서는 StringTokenizer()에서 delim으로 " "를 작성하여 공백을 기준으로 문자열을 분리한다. 이후 매 줄 마다 nextToken() 메서드를 사용해 토큰을 읽어온다.
이 문제에서는 BufferedReader, StringTokenizer을 사용해 입력되면 1, 3이 토큰으로 읽어지는 것이다.
2️⃣ 투사된 선들의 길이 합을 구해야 하는데, 여기서 중요한 점은 그린 선끼리 겹칠 수 있다는 것이다.
✔️ 따라서, 겹치는 것을 고려해야 한다. 이때 for 반복문을 이용한다.
👉🏻 10001 길이를 가진 int형 배열 n을 선언한다. 이후, for 반복문 조건식에서 i를 입력된 X_i으로 초기식을 작성하고, 1씩 증가하며 Y_i 바로 직전까지 n[i]에 1을 대입한다.
✔️ for 반복문을 사용하는 이유를 알고 싶다면 아래 Questions & Answer을 보자!
3️⃣ 이제 n[i]는 0과 1로 구성되어 있으며, 1인 요소들의 개수 총합을 구하면 투사했을 때의 선들의 길이 합이 된다.
✔️ Arrays.stream().sum()을 이용한다.
✔️ 자바는 스트림 스퀀스의 합을 얻기 위해 스트림 API에 sum() 메서드를 제공하기 때문이다.
👉🏻 따라서, Arrays.stream(n)을 사용해 배열을 스트림에 전달하고, 여기에 sum() 메서드를 사용해 1의 총합을 얻는다. 여기서 n 배열이 투시된 선에 포함되는 좌표이면 1을, 아니면 0을 가지고 있기 때문에 배열의 총합을 구해도 되는 것이다.
✨ 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
int n[] = new int[10001];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
for(int j = x; j < y; j++) {
n[j] = 1;
}
}
System.out.println(Arrays.stream(n).sum());
}
}
✨ Questions & Answer
📍 왜 배열의 길이가 10000이 아니라 10001인가요?
✔️ int형 배열인 n은 10000개가 아니라 10001 length로 선언했다.
👉🏻 이유는 선의 시작 좌표와 끝 좌표는 1~10000까지의 자연수이고, 배열의 인덱스가 1이면 좌표 1을, 2면 좌표 2를 의미한다고 생각하고 코드를 작성했기에 배열의 길이가 10001이 되었다.
📍 왜 for 반복문과 배열을 사용하는 건가요?
✔️ 문제에서 준섭이가 그린 여러 선들을 좌표에 투시한 선의 길이를 그려야 하는데, 여러 선들이 그려졌을 경우(=N > 1일 경우) 투시되는 과정에서 겹치는 부분이 존재할 수 있고 우리는 그것을 고려해야 하기 때문이다.
🔻 예시를 통해 쉽게 보는 답변
✔️ 문제에서 주어진 예제 입력 중 1 3과 2 5를 보자. 첫 번째 선은 좌표 1부터 3까지가 연결된 선이고 두 번째 선은 좌표 2부터 5까지가 연결된 선이다. 이때 두 선을 투시하면 좌표 2부터 3까지가 겹치게 된다. 즉, 두 선이 하나가 되어 결국 좌표 1부터 5까지의 선이 완성되는 것이다. 이러한 부분을 for 반복문과 배열이 아니라 하더라도 풀 수 있을 것이다! 하지만, 내가 for 반복문과 배열을 선택한 이유는 "겹치는 선이 존재할 때의 처리"를 for 반복문이 쉽게 해결할 수 있기 때문이다. 첫 번째 선의 시작 좌표가 1, 끝 좌표가 3이므로 인덱스 1, 2에 1을 대입한다. 이후 두 번째 선의 시작 좌표인 2와 끝 좌표인 5이므로 인덱스 2, 3, 4에 1를 대입한다. 이 과정에서 인덱스 2에 1이 두 번 대입된다. 하지만, 두 번 대입된다고 해서 1이 더해져 2가 되는 것이 아니라, 그대로 1이 된다. 따라서 서로 다른 선에서 겹치는 부분이 존재한다 하더라도 for 반복문을 이용해 1을 대입하면 쉽게 해결할 수 있다.
📍 for 반복문에서 i < y로, 왜 y가 아니라 y-1까지만 반복을 도는 것인가요?
✔️ 바로 위 질문에서 적기도 했지만, 이 문제는 투시된 선들의 길이를 구하는 문제이기 때문이다.
🔻 예시를 통해 쉽게 보는 답변
✔️ 예제 입력에서 선의 개수가 1(N)이고, 주어진 x y 좌표가 1 9라고 하자. i가 x부터 y까지 반복을 돌며 배열 n의 인덱스 i에 1을 대입한다고 하면, 인덱스 1~9까지 총 9개의 인덱스가 요소 1을 가지게 된다. 따라서 배열의 합을 구하면, 1 * 9 = 9가 된다. 하지만, 백준 16396번 힌트에서 볼 수 있듯이, 1~9까지의 선의 길이는 선에 포함된 점의 개수가 아니라 1~2, 2~3, 3~4, ..., 8~9 각각이 길이가 1이 되어 총 길이가 8이 된다고 생각해야 한다. 따라서 반복문을 돌 때 y-1까지 돌 수 있도록 코드를 작성했다. 물론, i = x + 1; i < y + 1; i++ 이라고 적어도 상관없다.
✨ 주의할 점
✔️ 백준에 제출할 때는 클래스명을 Main이라고 수정하고 제출해야 하는데, 자꾸 까먹고 그대로 제출해서 컴파일 에러가 발생했다... 👉🏻 꼭 제출 전에 Main으로 고치자!!
✔️ 투사된 선들의 "길이" 합을 구하는 것이다. 투사된 선들을 이루는 좌표의 개수를 세지 말자!
✨ 백준 채점 결과 및 코드 리뷰
📍 채점 결과1
✔️ 위 최종 코드를 제출한 결과는 다음과 같다.
📍 채점 결과2
✔️ 최종 코드와 StringTokenizer 클래스 부분에서 차이가 존재한다.
public class Main {
public static void main(String[] args) throws IOException {
int n[] = new int[10001];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
for(int j = x; j < y; j++) {
n[j] = 1;
}
}
System.out.println(Arrays.stream(n).sum());
}
}✔️ 코드를 제출한 결과는 다음과 같다.
👉🏻 시간은 증가했지만, 메모리는 줄었다.
📍 채점 결과3
✔️ 코드 제출 후 자바로 이 문제를 푸신 다른 분들의 코드를 봤는데, sum() 메서드를 사용한 대신, 직접 모든 원소의 값을 sum 변수에 더하여 푸신 분들이 있으셔서 나도 채점 결과2에서 제출한 코드에서 해당 부분만을 수정해서 다시 제출해봤다. (위 최종 코드에서 이 부분을 수정한 결과는 채점 결과 4에 가면 있다.)
public class Main {
public static void main(String[] args) throws IOException {
int n[] = new int[10001];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
for(int j = x; j < y; j++) {
n[j] = 1;
}
}
int sum = 0;
for(int i = 0; i < 10001; i++){
if(n[i] == 1) sum++;
}
System.out.println(sum);
}
}
✔️ 코드를 제출한 결과는 다음과 같다.
👉🏻 시간은 채점 결과1에 비해 4ms 정도 증가되었는데, 메모리는 확 줄었다. 아무래도 배열을 스트림에 넣어서 합을 구하는 것보다는 메모리를 적게 차지하지 않나 싶다. 이 차이가 왜 발생하는지도 찾아봐야겠다.
📍 채점 결과4
✔️ 최종 코드에서 sum() 메서드를 사용하지 않고 반복문을 사용해 합을 직접 더하는 방식으로 수정해서 제출해봤다.
public class Main {
public static void main(String[] args) throws IOException {
int n[] = new int[10002];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
for(int j = x; j < y; j++) {
n[j] = 1;
}
}
int sum = 0;
for(int i = 0; i < 10001; i++){
if(n[i] == 1) sum++;
}
System.out.println(sum);
}
}
✔️ 코드를 제출한 결과는 다음과 같다.
👉🏻 채점 결과 3과 시간은 같은데, 메모리는 줄었다.
✨ 느낀 점
일단 오늘 int 배열의 합을 구할 수 있는 메서드를 알게 되었다. 그리고 확실히 제출 후에 다른 분들 코드를 보며 직접 수정해보니 왜 시간과 메모리 부분에서 달라지는지 고민할 수 있게 되어 좋은 것 같다!! 또한, 이렇게 정리해보니까 입력과 관련된 BufferedReaer, StringTokenizer 클래스에 대해서도 전보다 더 잘 이해할 수 있었다. 정말 다양한 풀이가 있으니 일단 종이에 어떤 형식으로 풀건지 그 흐름을 정리하고 코드를 작성해보는 것도 좋을 것 같다. 그리고 다음부터는 시간 제한을 두고 풀어보려고 한다!
