[알고리즘] 입출력

Spring Framework를 배우면서, 프레임워크의 틀에 맞게 코딩을 하다보니 혼자서 로직을 짜는 것을 많이 잊어버린것 같은 느낌을 받았다. 그래서 알고리즘 문제를 풀면서 감을 다시 익혀보려고 한다.
알고리즘 문제는 특정 값을 입력받은 뒤 원하는 답을 출력하는 형식이므로,
제일 먼저 입력/출력에 대해 다시 공부하고자 한다.

입력

필자는 자바를 공부할 때 Scanner를 이용한 입력받기를 주로 사용했다.
Scanner 클래스는 공란과 줄바꿈 모두 입력값의 경계로 인식하기 때문에 데이터를 입력받기에 용이하고, 입력받은 즉시 자료형이 확정되어 문제를 풀 때 좋다.

입력을 받을 때 사용할 수 있는 클래스로는 BufferedReader도 있다.
BufferedReader는 일반적으로 라인 단위로 입력을 받고, 라인 바이 라인으로 입력값의 경계를 인식하기 때문에 한 줄에 공란을 구분자로 여러 값이 입력된 경우라면 파싱이 필수적이다. 또한 입력받은 값은 모두 String이므로 하나하나 타입 변환을 해주어야 한다는 불편함이 있다.
그리고, Scanner처럼 자체적으로 Exception에 대한 처리가 되어있지 않아서
throws Exception 또는 try ~ catch를 이용해서 Exception을 따로 처리해주어야 한다.

왜 굳이 BufferedReader를 사용할까? 🤫

바로 속도 때문이다.

알고리즘의 목표는 같은 결과값이라도 더 빠르고 효율적인 연산을 통해 결과를 도출하는 것이라고 할 수 있다. 그래서 시간 제한을 두고, 효율적인 연산인지 아닌지를 평가하게 되어있는 것이다.

적은 숫자의 입력값이 주어진 경우라면 Scanner도 크게 상관없다.
하지만 입력값이 많을 수록 BufferedReader의 사용은 필수적이다.

---

BufferedReader가 뭐지? 😐

버퍼(Buffer) : 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 임시 메모리 영역
( 입출력 속도 향상을 위해 사용한다 !! )
그리고 이러한 버퍼를 이용해 입력하는게 BufferedReader

한번 거쳐가니까 느릴 것 같은데 왜 속도가 빠르지? 😦

키보드나 모니터와 같은 외부 장치와의 데이터 입출력은 생각보다 시간이 걸리는 작업이다. 버퍼링 없이 키보드가 눌릴 때마다 눌린 문자의 정보를 목적지로 바로 이동시키는 것 보다, 중간에 메모리 버퍼를 둬서 데이터를 한데 묶어서 이동시키는 것이 보다 효율적이고 빠르다 !

---

Scanner 클래스와 BufferedReader 클래스의 구현 소스를 비교해보자.

[Scanner 클래스]

package study.test;

import java.util.Scanner;

public class ScannerExample {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int intValue = sc.nextInt();
		
		double doubleValue = sc.nextDouble();
		
		String strValue = sc.next();
		
		boolean boolValue = sc.nextBoolean();
		
		System.out.println(intValue + ", " + doubleValue + ", " + strValue + ", " + boolValue);
	}
}

입력 : 3 5.689 안녕하세요 false
출력 : 3, 5.689, 안녕하세요, false

• 딱 보기에도 쓰기 간단함. 입력받는 즉시 바로 type이 결정됨.
• Scanner의 next()는 개행문자(엔터)제외하고 String 값만 읽어온다.
• Scanner의 nextLine()는 개행문자(엔터)와 String값 같이 읽어온다.

[BufferedReader 클래스]
백준 알고리즘 5596번 문제를 Java로 푼 것을 예시로 가져왔다.

package study.test;

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

public class BufferedReaderExample {
	public static void main(String[] args) throws IOException {
		int sum1=0;
		int sum2=0;
		int result;
		
		// BufferedReader 객체 생성하기 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// readLine() 이용해서 String 형태로 개행문자까지 포함해서 한줄을 통째로 입력받음. and 그걸 StringTokenizer 이용해서 " " 기준으로 쪼갠다.
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
		
		
		// 쪼갠 값이 존재할 때 까지 반복한다.
		while(st.hasMoreTokens()) {
			// nextToken()을 이용해서 남은 토큰을 String -> int 로 형변환 하여 누적해서 더한당.
			sum1 += Integer.parseInt(st.nextToken());
		}
		while(st2.hasMoreTokens()) {
			// nextToken()을 이용해서 남은 토큰을 String -> int 로 형변환 하여 누적해서 더한당.
			sum2 += Integer.parseInt(st2.nextToken());
            	      
                      //sum2 += Integer.valueOf(st2.nextToken()); 도 가능하다.
                      // valueOf()메소드 : 입력받은 인자값을 지정된 Number객체 형으로 변환하여 반환한다.
		}
		if (sum1 > sum2) {
			result = sum1;
		}
		else if (sum1 < sum2) {
			result = sum2;
		}
		else {
			result = sum1;
		}
		System.out.println(result);
	}
}

• 기본적으로 BufferedReader는 한 줄을 통째로 입력받는 방법으로 주로 쓰인다.
• StringTokenizer : 하나의 문자열을 여러개의 문자열로 분리하기 위해 사용한다. 구분하는 기준 문자를 구분문자, 구분 문자로 분리된 문자열을 토큰이라고 한다.
• split()메소드를 사용해서 원하는 구분자로 문자열을 분리하는 것도 가능하다.
  다만 split()은 인자로 regex(정규표현식)을 사용하기 때문에, 속도 측면에서는 StringTokenizer가 더 빠르다고 할 수 있다.
  

System.in은 뭐고, InputStreamReader는 뭐야? 😵

• Stream : 한 곳에서 다른 곳으로의 데이터 흐름.
  출발지와 도착지를 이어주는 빨대라고 생각하면 쉽다. 아래의 그림을 참고하자.
  
  스트림은 단방향이기 때문에 입력과 출력이 동시에 발생할 수 없다. 그래서 용도에 따라 입력스트림 / 출력스트림 으로 나뉜다.
  그리고 자바에서 가장 기본이 되는 입력 스트림이 InputStream 이다.
  그리고 System.in 이 InputStream 타입의 필드 이다.
  하지만 InputStream은 입력을 받을 때 1Byte만 인식하니 한글은 입력해봤자 읽지 못하고 엉뚱한 문자만 나온다. 문자를 온전히 읽어들이기 위해서 필요한 것이 InputStreamReader 이다
• InputStreamReader의 특징
  : Byte 단위 데이터를 문자 단위 데이터로 처리할 수 있도록 변환해준다.

---

출력

System.out.print는 잘 알고 있을 것이라 생각해서, 그것 대신 StringBuilder에 대해 설명하고자 한다.

출력해야 하는 것이 많은 경우, 매번 출력하는 것 보다 StringBuilder를 이용해서 문자열을 만들고 한번에 출력하는 것이 속도 면에서 좋다.

왜 System.out.println이 StringBuilder보다 속도가 느릴까?

System.out.println을 내부적으로 살펴보면, synchronized block 으로 씌여져 있는 것을 확인할 수 있다.
synchronized는 해석 그대로 동기화다.
하나의 프로세스에는 하나 이상의 스레드가 존재하고, 스레드를 통해 같은 프로세스에서 데이터 공유가 가능하다. 때로 공유 데이터를 작업중인 스레드가 작업을 마칠 때 까지 다른 스레드에서 접근하지 못하도록 막기위한 것이 바로 동기화이다.
동기화의 단점은 작업중인 스레드가 마칠 때 까지 다른 스레드들의 대기시간이 발생한다는 것이다.
즉, System.out.println 또한 동기화가 적용되어 있는 것이고, 그렇기에 작더라도 오버헤드가 발생하게 되는 것이다

오버헤드(overhead)는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말한다.
예를 들어 A라는 처리를 단순하게 실행한다면 10초 걸리는데, 안전성을 고려하고 부가적인 B라는 처리를 추가한 결과 처리시간이 15초 걸렸다면, 오버헤드는 5초가 된다. 또한 이 처리 B를 개선해 B'라는 처리를 한 결과, 처리시간이 12초가 되었다면, 이 경우 오버헤드가 3초 단축되었다고 말한다.

---

• 만약 1억번의 출력이 필요해서 System.out.println을 1억번 호출한다면 어떻게 될까?
  -> 오버헤드가 쌓여서 성능 저하를 초래하게 된다.
• 이러한 이유로 프로젝트에서는 System.out.println으로 로그를 남기지 말라는 이야기가 있는 것이다.

따라서 알고리즘 문제를 풀 때에는 출력할 데이터들을 모아두고, 한번의 System.out.println을 이용해 출력하는 방법을 사용한다.

그 방법이 바로 StringBuilder를 활용하는 것이다.
예제를 보자.

public class StringBuilderEx {
	public static void main(String[] args) {
		StringBuilder sb = new StringBuilder();
		
		for(int i=0; i<100000000; i++) {
			sb.append(i + "\n");
			
		}
        System.out.println(sb.toString());
	}
}

위의 소스처럼 출력 데이터를 append()메소드를 통해 계속 붙여나가다가, 마지막에 System.out.println을 호출해서 출력할 수 있다.

[참고] String , StringBuffer, StringBuilder
Java에서 문자열을 다루는 대표적인 클래스로는 위의 3가지가 있다.
연산이 많지 않을때는 어떤 것을 사용하더라도 이슈가 발생할 가능성은 거의 없다. 하지만 연산횟수가 많아지거나, 멀티스레드 등의 상황이 자주 발생한다면 각클래스의 특징을 이해하고 상황에 맞게 적절한 클래스를 사용해야 한다.

String vs StringBuffer/StringBuilder
가장 큰 차이점 : String은 불변(immutable)의 속성을 갖는다 !
아래의 예제를 보자.

Stirng str = "Hello";
str += " World" 
System.out.println(str); // 출력결과 : Hello World

Hello 값을 가지고 있던 String 클래스의 참조변수 str이 가리키는 곳에 저장된 Hello에 World라는 문자열을 더해 Hello World로 변경된 것으로 착각할 수 있다.
하지만, 기존에 Hello 값이 들어가있던 String클래스의 참조변수 str이 Hello World라는 값을 가지고 있는 새로운 메모리 영역을 가리키게 변경되고, 처음 선언했던 Hello값이 할당되어 있던 메모리 영역은 Garbage로 남아있다가 GC에 의해 사라지게 되는 것이다.
즉 String클래스는 불변이기 때문에 문자열을 수정하는 시점에서 새로운 String 인스턴스가 생성된 것이다 !
아래 그림을 참고하자.

위와 같이 String은 불변성을 가지기 때문에 변하지 않는 문자열을 자주 읽어들이는 경우 String을 사용하면 좋은 성능을 기대할 수 있다.
하지만, 문자열 추가/수정/삭제 등의 연산이 빈번하게 발생하는 알고리즘에 String 클래스를 사용하면 Heap영역에 많은 임시 Garbage가 생성되어 Heap메모리의 부족으로 성능에 치명적인 영향을 끼치게 된다.

---

이를 해결하기 위해 Java에서는 가변성을 가지는 StringBuffer 와 StringBuilder 클래스를 도입했다.
이들은 .append(), .delete()등을 이용해서 동일 객체 내에서 문자열을 변경하는 것이 가능하다.
따라서 문자열의 추가/수정/삭제가 빈번하게 발생할 경우라면 이들을 사용해야 한다.

---

StringBuffer vs StringBuilder

그렇다면 이 둘의 차이점은 무엇일까?
가장 큰 차이점은 동기화의 유무이다.
StringBuffer는 동기화 키워드를 지원하여 멀티스레드 환경에서 안전하다.(참고 : String 역시 불변성을 가지기 때문에 멀티스레드 환경에서의 안정성을 가지고 있다)
반대로 StringBuilder는 동기화를 지원하지 않기 때문에 멀티스레드 환경에서 사용하는 것은 적합하지 않다. 하지만 동기화를 고려하지 않는 만큼 단일스레드에서의 성능은 StringBuffer보다 뛰어나다.

[정리]

• String : 문자열 연산이 적고, 멀티스레드 환경일 경우
• StringBuffer : 문자열 연산이 많고, 멀티스레드 환경일 경우
• StringBuilder : 문자열 연산이 많고, 단일스레드 or 동기화를 고려하지 않아도 되는 경우

---

글을 마치면서

처음엔 입출력 방법에 대해서만 공부하려고 하였으나, 찾아보다 보니 잘 몰랐던 StringBuilder/StringBuffer 라던지, Scanner외에 다른 입력방법 등 여러가지를 알게 되었다. 그래서 생각했던 것 보다 글의 내용이 많이 길어진 것 같다.
Java에 대해 잘 모르면서 사용했던 부분이 생각보다 많았다는 것도 깨달아서 반성하는 계기도 되었던 것 같다.
필자의 글을 읽는 독자들도 잘 몰랐다면 다시 한 번 정리하는 계기로 삼았으면 좋겠다.