<Do it! 알고리즘 코딩테스트 - 자바 편>문제 3 - 백준 11660번
11660번: 구간 합 구하기 5 (acmicpc.net)
문제풀기
💡 베스트 답
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
// https://www.acmicpc.net/problem/11660
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()); // 표의 크기 n
int m = Integer.parseInt(st.nextToken()); // 합을 구해야 하는 횟수 m
// 인덱스 1부터 쓰기 위해
int[][] nums = new int[n + 1][n + 1];
int[][] sum = new int[n + 1][n + 1];
// 입력한 숫자 배열 만들기 + 구간 합 배열 만들기
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine()," ");
for (int j = 1; j <= n; j++) {
nums[i][j] = Integer.parseInt(st.nextToken());
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + nums[i][j];
}
}
// 입력된 구간 합 구하기
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine()," ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int result = sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1];
sb.append(result + "\n");
}
System.out.println(sb);
}
}오답노트
- 책풀이를 봤는데…
‘구간 합’을 이차원 배열로 옮겨서 생각해봐라…
그 구간 합의 이차원 배열을 만들고, 어떻게 하면 일부 구간의 합을 구할 수 있을지 규칙을 파악하라.
그리고 그 규칙을 공식으로 만들어라…
대충 이런 내용이었는데…
빡대갈쓰인 나는 도통 무슨 소리인지 이해가 안되서 직접 표를 그리면서 규칙을 이해하고 공식을 짰다.
그래 머리가 안 되면 몸이 고생해야지…
- 4x4 크기의 표일 때, (1,1)을 기준으로 합 배열 sum[ ][ ] 만들기
(+ 참고로 입력 받은 숫자 배열은 nums[ ][ ] 로 명명)
| (1,1) | (1,1)+(1,2) | (1,1)+(1,2)+(1,3) | (1,1)+(1,2)+(1,3)+(1,4) |
|---|---|---|---|
| (1,1)+(2,1) | 2{(1,1)}+(1,2)+(2,1)+(2,2) | ||
| (1,1)+(2,1)+(3,1) | |||
| (1,1)+(2,1)+(3,1)+(4,1) |
책 풀이에 따르면, 우선 1행과 1열은 저런 식으로 초기화 시켜놓고
sum[1][2]와 sum[2][1]를 합치고 (2,2)값을 sum[2][2]에 넣는다.
그러면 ↖이 방향 대각선에 있는 sum값이 중복되니 sum[1][1]을 빼준다.
그리고 nums[2][2]값을 더해준다.
| (1,1) | (1,1)+(1,2) | (1,1)+(1,2)+(1,3) | (1,1)+(1,2)+(1,3)+(1,4) |
|---|---|---|---|
| (1,1)+(2,1) | (1,1)+(1,2)+(2,1)+(2,2) | 2((1,1)+(1,2))+(1,3)+(2,1)+(2,2)+(2,3) | |
| (1,1)+(2,1)+(3,1) | |||
| (1,1)+(2,1)+(3,1)+(4,1) |
확인 차 다른 곳도 한번 더 그려보았다.
sum[2][3]의 경우 → sum[1][3] + sum[2][2] - sum[1][2] + nums[2][3] 요렇게 계산해서 넣어주면 됐다.
- (1,1) 기준 - (i, j) 까지의 합 배열
| (1,1) | (1,1)+(1,2) | (1,1)+(1,2)+(1,3) | (1,1)+(1,2)+(1,3)+(1,4) |
|---|---|---|---|
| (1,1)+(2,1) | (1,1)+(1,2)+(2,1)+(2,2) | (1,1)+(1,2)+(1,3)+(2,1)+(2,2)+(2,3) | (1,1)+(1,2)+(1,3)+(1,4)+ (2,1)+(2,2)+(2,3)+(2,4) |
| (1,1)+(2,1)+(3,1) | (1,1)+(1,2)+(2,1)+(2,2)+(3,1)+(3,2) | (1,1)+(1,2)+(1,3)+(2,1)+(2,2)+(2,3)+(3,1)+(3,2)+(3,3) | (1,1)+(1,2)+(1,3)+(1,4)+(2,1)+(2,2)+(2,3)+(2,4)+(3,1)+(3,2)+(3,3)+(3,4) |
| (1,1)+(2,1)+(3,1)+(4,1) | (1,1)+(1,2)+(2,1)+(2,2)+(3,1)+(3,2)+(4,1)+(4,2) | (1,1)+(1,2)+(1,3)+(2,1)+(2,2)+(2,3)+(3,1)+(3,2)+(3,3)+(4,1)+(4,2)+(4,3) | (1,1)+(1,2)+(1,3)+(1,4)+(2,1)+(2,2)+(2,3)+(2,4)+(3,1)+(3,2)+(3,3)+(3,4)+ |
| (4,1)+(4,2)+(4,3)+(4,4) |
그러면 요렇게 합 배열이 채워지고, 일정한 규칙을 발견할 수 있다.
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + nums[i][j]
하지만 문제는, (1,1)을 기준으로 구하는 합 배열이라는 것
(1,1)이 아닌 다른 곳부터 (i,j)까지의 합을 구하려면???
-
예1 : (2,2) - (3,4)를 구하려면?
(2,2) + (2,3) + (2,4) + (3,2) + (3,3) + (3,4) 가 필요
⇒sum[3][4] = (1,1)+(1,2)+(1,3)+(1,4)+(2,1)+(2,2)+(2,3)+(2,4)+(3,1)+(3,2)+(3,3)+(3,4)
➖sum[1][4] =(1,1)+(1,2)+(1,3)+(1,4)(빼기)
➖sum[3][1] =(1,1)+(2,1)+(3,1)(빼기)
➕sum[1][1] =(1,1)(중복으로 빼준(1,1)더해주기) -
예2 : (3,3) - (3,4)구하려면?
(3,3) + (3,4) 가 필요
⇒sum[3][4] = (1,1)+(1,2)+(1,3)+(1,4)+(2,1)+(2,2)+(2,3)+(2,4)+(3,1)+(3,2)+(3,3)+(3,4)
➖ sum[2][4] = (1,1)+(1,2)+(1,3)+(1,4)+(2,1)+(2,2)+(2,3)+(2,4)(빼기)
➖ sum[3][2] = (1,1)+(1,2)+(2,1)+(2,2)+(3,1)+(3,2) (빼기)
➕ sum[2][2] = (1,1)+(1,2)+(2,1)+(2,2) (중복으로 빼준 것 더해주기)
➡️ 이걸 공식으로 만들면…
(a,b) 부터 (c,d)의 구간 합은
sum[c][d] - sum[a-1][d] - sum[c][b-1] + sum[a-1][b-1]
드디어 다 풀었다!!!!!!!!!!!!!
라고 생각했으나…
여기서 끝이 아니었다.
공부하기
- 1차 시도
메모리 : 127148 KB
시간 : 1696ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
// https://www.acmicpc.net/problem/11660
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()); // 표의 크기 n
int m = Integer.parseInt(st.nextToken()); // 합을 구해야 하는 횟수 m
// 인덱스 1부터 쓰기 위해
int[][] nums = new int[n + 1][n + 1];
int[][] sum = new int[n + 1][n + 1];
// 입력한 숫자 배열 만들기 + 구간 합 배열 만들기
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine()," ");
for (int j = 1; j <= n; j++) {
nums[i][j] = Integer.parseInt(st.nextToken());
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + nums[i][j];
}
}
// 입력된 구간 합 구하기
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine()," ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
System.out.println(sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1]);
}
}
}잘 풀었다고 생각했는데 속도가 느렸다.
왜지??????
조금 빡쳐하던 찰나….
나랑 비슷한 흐름으로 풀었는데 시간이 900ms가 나오게 푼 답안이 있었다.
그 답안과 내 답안을 비교해보니, 결정적으로 StringBuilder를 쓰고 안 쓰고의 차이가 있었다.
String 그리고 StringBuffer/StringBuilder
- String은 느리다.
String이 느린 가장 큰 원인은 Immutable 한 객체이기 때문이다.
String은 객체가 한번 만들어지면 그 값이 절대 변경되지 않는다.
만약 String으로 수정 및 조작을 해야한다면,
새로운 String 객체를 만들어서 수정한 값을 새롭게 넣는 식으로 이루어진다.
- 다음 코드를 살펴보자.
String str = "AAA"; str = str + "BBB"; // 연산과 수정 이루어질 때, 아예 새로운 객체를 만들어 AAABBB를 담는다. System.out.println(str); // 출력결과 // AAABBB
String 타입의 str에 담겨있던 AAA를, AAA와 BBB를 합친 AAABBB로 바꾸는 코드로, 간단해 보이지만 실제로 Java 메모리 내에서는 많은 작업이 이루어진다.
1) str에 담겨있던 해당 객체(AAA)의 주솟값은 버리고,
2) 새로운 객체를 만들어 ‘AAABBB’를 넣고,
3) str 변수에는 그 주솟값을 담는다.
4) 이전 str에 담겨있던 주솟값의 객체는 버려져 가비지(gabbage)가 되고,
5) 이후 가비지 컬렉터가 이를 수거한다.
- String이 느린 이유?
다음 말이 그 이유를 함축하고 있다.
" Java가 느려지는 가장 치명적인 원인은 '객체의 생성'이다. "
즉, Immutable한 객체인 String은, 문자열 연산 또는 수정이 많을 때 실행 속도가 느려질 수밖에 없다.
이에 대한 보완책으로 등장한 것이 StringBuffer와 StringBuilder라는 mutable한 클래스이다. 객체 안의 데이터를 내부적으로 변경하지만 새로운 객체는 만들지 않는다. 또한 String 클래스와 거의 유사한 메소드들을 가지고 있고, 잦은 변경 시에도 속도가 훨씬 빠르다.
실제로 String과 StringBuilder의 속도 차이를 비교했을 때 다음과 같았다.
public class String {
public static void main(String[] args) {
String str = "A";
String target = "B";
long start = System.currentTimeMillis(); // 연산 전 시각
for (int i = 0; i < 90000; i++) { // 9만 번 연산
str = str + target;
}
long end = System.currentTimeMillis(); // 연산 후 시각
System.out.println(end - start); // 9만 번 연산에 소요된 시간
}
}
// 출력 결과 : 998public class StringBuilder {
public static void main(String[] args) {
StringBuilder sb = new StringBuilder("A");
String target = "B";
long start = System.currentTimeMillis(); // 연산 전 시각
for (int i = 0; i < 90000; i++) { // 9만 번 연산
sb.append(target);
}
long end = System.currentTimeMillis(); // 연산 후 시각
System.out.println(end - start); // 9만 번 연산에 소요된 시간
}
}
// 출력 결과 : 8따라서 성능을 생각한다면, String 대신 StringBuffer나 StringBuilder를 사용하는 습관을 들이는 것이 좋다고 한다.
(+ 참고로, 개인이 사용하는 프로그램이면 String을 써도 상관없지만, 엔터프라이즈급에선 가능하다면 String을 쓰지 않는다.)
- StringBuilder가 StringBuffer보다 속도 측면에서 더 빠르다.
두 클래스의 차이점은 여러 가지가 있지만, 가장 중요한 것은 다음 두 가지다.
1) StringBuffer는 이전부터 존재하던 클래스였고, StringBuilder는 JDK 1.5 버전부터 나온 기능이며
2) '동기화 처리'를 지원하지 않기 때문에 StringBuilder가 속도 면에서 더 좋다.
- String 대신 StringBuilder를 써야 하는 경우
문자열 연산 작업이 빈번하게 이루어지는 메소드에서는 StringBuilder를 이용하는 것이 좋다.
- 루프를 돌면서 문자열의 내용이 계속해서 변경되는 경우
+혹은+=와 같은 연산이 빈번하고 자주 사용되는 메소드인 경우- if ~ else에 의한 연산으로 문자열이 완성되는 경우 (주로 SQL문이나 명령어)
- 어쨌든 중요한 것만 요약하자면...
String은 매번 연산 시에 객체를 새로 만들어 내기 때문에 객체 생성이 많아지고, 시스템 성능에 악영향을 준다. 따라서 이런 문제점을 개선하기 위한 장치가 StringBuffer와 StringBuilder이다.
그 중 StringBuilder가 동기화 처리를 지원하지 않기 때문에 속도면에서 더 빠르다.
그럼 StringBuilder에 대해서만 좀더 알아보자.
StringBuilder의 생성자
| 생성자 | 기능 |
|---|---|
| StringBuilder() | 문자를 가지지 않고, 초기 용량이 16문자인 캐릭터 라인 빌더를 구축 |
| StringBuilder(CharSequence seq) | 지정된 CharSequence 인수와 같은 문자를 포함한 캐릭터 라인 빌더를 구축 |
| StringBuilder(int capacity) | 문자를 가지지 않고 수용 인수에 따라서 지정된 초기 용량인 캐릭터 라인 빌더를 구축한다. |
| StringBuilder(String str) | 지정된 캐릭터 라인의 내용에 초기화된 캐릭터 라인 빌더를 구축한다. |
이중에서 가장 많이 쓰이는 것은 아무 것도 없이 사용하는 Stringbuilder와 문자열을 아예 생성시에 사용하는 생성자가 가장 많이 쓰인다.
StringBuilder 클래스의 주요 메소드
- append() : 모든 기본형 자료와 문자열, 객체들을 현재의 StringBuilder에 추가하는 메소드. 문자열의 ‘+’대신에 사용한다.
- reverse() : 현재의 StringBuilder 안에 있는 문자열을 역순으로 만들어서 반환해주는 기능을 가진다.
| 메소드 | 기능 |
|---|---|
| StringBuilder append(String str) | 문자열 뒤에 str을 추가. 문자열뿐 아니라 거의 모든 기본 자료형이나 객체들을 추가할 때도 마찬가지로 사용한다. |
| StringBuilder insert(int offset, String str) | 문자열의 offset 위치에 str을 추가한다. 원래 그 자리의 문자열은 뒤로 밀린다. |
| StringBuilder delete(int start, int end) | start부터 end - 1까지의 부분 문자열을 삭제한다. |
| StringBuilder deleteCharAt(int index) | index 위치에 있는 문자 하나를 삭제한다. |
- append 사용 예시
StringBuilder str = new StringBuilder();
str.append(”AAA”);
str.append(”BBB”);
// 출력결과 : AAABBB후... 정리 끝!
