https://www.acmicpc.net/problem/11723
11723번: 집합
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
www.acmicpc.net
백준 집합 문제를 풀다가 간단해보이길래 Scanner, System.our.println() 을 이용하여 문제를 풀었다.
하지만 시간초과가 나서 공부를 하던 중 데이터 입출력 부분에서 시간초과가 났다는 것을 알게 되었다.
알고리즘 문제를 풀 때 대량의 데이터를 처리할 때 쓰기 좋은 방법을 배워서 정리하겠다.
1. BufferedReader
Scanner 대신에 BufferedReader를 사용하면 입력된 데이터가 바로 전달되지 않고 버퍼를 거쳐 전달되므로 많은 양의 데이터를 전달할 때 유리하다. 하지만 입력데이터가 String으로 고정되어 사용법이 Scanner보다는 복잡하다는 단점이 있다. 데이터를 가공하는 방법 중 내가 공부했던 방법을 밑에 적을 예정이다(+점점 추가 될 수도 있고)
2. BufferedWriter
BufferedWriter는 System.our.println()보다 데이터 출력속도가 마찬가지로 더 빠르다고 한다.
아래는 버퍼를 사용하면 한번 더 거쳐가서 속도가 느리지 않나? 라는 질문에 답을 해준 좋은 블로거의 예시이다.
기가막힌 비유인 것 같다.
하지만 집합 문제를 풀 때 BufferedWriter를 써도 시간초과라는 똑같은 결과가 나왔다. 무엇이 문제인가?
공부를 더 해보니 check를 할 때 마다 "1" or "0"의 데이터를 계속해서 출력해주었기 때문이였다. 출력을 해줘야 답이 나오지 그럼 어떻게 출력을 하냐? 에 대해서 더 공부를 해 본 결과 문자열을 한번에 저장해서 마지막에 한번에 출력하는 방법인 StringBuilder가 있었다.
3. StringBuilder
그럼 StringBuilder란 무엇인가? String형태의 문자를 저장하여 마지막에 한번에 출력하게 만들어주는 클래스이다. StringBuilder는 String과 문자열을 더할 때 새로운 객체를 만드는 것이 아니라 기존의 데이터에 sb.append()를 하여 더하는 방식을 사용하기 때문에 속도가 더 빠른 것이다. 이를 이용해서 집합 문제를 풀었다.
하지만 나는 1204ms라는 생각보다 느린 처리속도의 결과가 나왔다.
어떻게 하면 더 빠른 속도를 낼 수 있을까? 이정도면 한 문제에 열심히 노력한 것 같은데. 나보다 속도 빠른 분들의 답을 보고 공부를 더 하기로 했다. 270ms의 미친속도를 내신 분도 있었는데 그 분의 코드는 아직 내가 해석해서 공부하기에는 살짝 시간이 걸릴 것 같아 800ms대의 분의 코드를 분석해서 공부를 해보았다.
그럼 이제 위에 말했던 BufferdReader를 이용하여 받은 문자열을 가공하는 방법을 알려주겠다.
1. StringTokenizer
BufferdReader의 readLine() 을 이용하면 개행문자 단위로 데이터를 읽어온다. 그럼 그 안에서 필요한 데이터를 나눠서 가공해야 하는데 그 중 StringTokenizer를 이용하면 원하는 문자 단위로 문장에서 데이터를 끊어준다. 나는 이를 이용하여 입력데이터인 (add 1) 을 .nextToken()을 이용하여 add와 1을 따로 읽어왔고, 1은 int형으로 바꿔줘야 하기 때문에 .Integer.ParseInt()를 이용하여 변경해주었다. 즉 (add 1)의 입력 데이터에서 1을 읽어오기 위해서는
String text = st.nextToken();
int N = Integer.parseInt(st.nextToken());
을 해줘야 하는 것이다. 정말이지 데이터를 읽어오는데 길고 복잡하지만 쓰면 익숙해진다. 단축키 기능이 있어서 st를 누르면 알아서 정리해주는 기능이 있으면 좋겠다 ㅎ
나는 위의 방식을 이용하여 데이터를 가공하였고, 정답을 도출해 냈을 때 1204ms의 속도가 나왔다.
그럼 800ms대의 속도를 낸 코더분의 방법을 가르쳐주겠다.(물론 내가 공부해서 정리하는 것)
2. StartsWith, subString
나는 StringTokenizer를 이용하여 데이터를 읽어와 또 " "-> 공백단위로 데이터를 잘라서 String과 int 변수에 저장을 하여 데이터를 이용하였다. 하지만 StartsWith, subString을 이용하면 String str = br.readLine()을 이용하여 (add 1)의 한 문장을 String 데이터에 가져오고
if (text.startsWith("add"))
{
S = S | (1 << Integer.parseInt(text.substring(4)));
}str.startsWith("add") 즉 문자열이 "add"로 시작하면 비트연산자를 이용하여
Integer.parseInt(test.subString(4)); 을 해주어 str의 4번째 인덱스 값인 1을 읽어와 정수형으로 변환하여 비트연산자를 수행하였다. 복잡하지만 StringTokenizer를 이용하여 데이터를 다시 변수에 저장하고, 이용하는 것 보다 속도가 더 빨라졌다.
subString에 대한 설명은 또 좋은 블로거 분의 비유와 설명이 있기에 가져와봤다.
자세한 설명은 아래 링크를 통해서 공부해보길 바란다.
이를 이용하여 나도 860ms의 속도로 문제를 해결 할 수 있었다.
역시 다른 분들의 코드를 보고 공부하는 것도 큰 도움이 되는 것 같다. 더 효율적이고 좋은 코드를 짜기위해 기초인 데이터 입/출력에 대해 알아보았다. 단순히 내가 공부한 것을 정리하는 블로그 이므로 틀릴 수도 있으니 너그럽게 봐주길 바란다ㅎㅡㅎ
아래에 2가지 방식의 내 코드를 보여드리고 마무리 하겠다.
1. BufferedReader, StringTokenizer를 사용한 방식
package bruteforce;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_실버5_11723_손은성 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int S = 0;
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String text = st.nextToken();
if (text.equals("all")) {
for (int j = 1; j <=20; j++) {
S = S | (1 << j);
}
continue;
} else if (text.equals("empty")) {
S = 0;
continue;
}
int num = Integer.parseInt(st.nextToken());
switch (text) {
case "add":
S = S | (1 << num);
break;
case "check":
if ((S & (1 << num)) != 0) {
sb.append("1\n");
break;
} else {
sb.append("0\n");
break;
}
case "remove":
S = S & ~(1 << num);
break;
case "toggle":
S = S ^ (1 << num);
break;
}
}
System.out.println(sb);
}
}2. BufferedReader, startsWith, subString을 사용한 방식
package bruteforce;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main_실버5_11723_손은성2 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int S = 0;
for (int i = 0; i < N; i++) {
String text = br.readLine();
if (text.startsWith("add")) {
S = S | (1 << Integer.parseInt(text.substring(4)));
} else if (text.startsWith("remove")) {
S = S & ~(1 << Integer.parseInt(text.substring(7)));
} else if (text.startsWith("check")) {
if ((S & (1 << Integer.parseInt(text.substring(6)))) != 0) {
sb.append("1\n");
} else
sb.append("0\n");
} else if (text.startsWith("toggle")) {
S = S ^ (1 << Integer.parseInt(text.substring(7)));
} else if (text.startsWith("all")) {
int cnt = 0;
while (++cnt != 21) {
S = S | (1 << cnt);
}
} else if (text.startsWith("empty")) {
S = 0;
}
}
System.out.println(sb);
}
}
+ 2021.08.16 / 15:38 추가
StringBuilder를 초기화 하기 위해서는 new StringBuilder를 이용하는 방법과, delete를 하여 지우는 방법이 있지만
각각은 객체를 새로 생성하고, 수행해야하는 연산이 많아져 속도가 느릴 수 있기 때문에
sb.setLength(0)을 이용하면 StrinbBuilder의 길이를 0으로 만들어 초기화 할 수 있다.
댓글