[C#] 15552번: 빠른 A+B

 

목차

---

백준 단계별로 풀어보기

25.07.18

 

3단계: 반복문

 

15552번: 빠른 A+B

문제 링크 : https://www.acmicpc.net/problem/15552

 

※ 문제를 풀기 위해 필요한 '빠른 입출력' 방법 모음

https://docs.google.com/document/d/17OUl9nU9i7vTkhk2q_qy4Q5Vl0HHE9bTLUHwbLp56WM/edit?tab=t.0#heading=h.mwvd9fqamd6

빠른 입출력 모음

 

문제를 풀기 위해 알아야 할 개념

- Baekjoon 문제의 시간 제한은 각 파일마다 따로따로 적용된다. 즉 시간 제한이 1초면 첫 번째 파일에 1초, 두 번째 파일에 1초, ..., 마지막 파일에 1초 이내가 걸려야 한다. 메모리 제한도 마찬가지인데, 한 순간에라도 지정된 메모리를 초과하면 안 된다.

 

- " 첫 줄에 테스트케이스의 개수 T가 주어진다." 또는 "입력은 여러 개의 테스트케이스로 이루어져 있다." 같은 문제는 그 T개의 테스트케이스가 한 파일에 들어있다는 뜻이다. 그런데 시간과 메모리 제한은 각 파일마다 따로따로 적용된다고 했으므로 주어진 시간 안에 한 파일에 들어있는 모든 테스트케이스가 돌아가야 한다.

 

--> 따라서 StringBuilder를 사용할 줄 알아야 한다.

 

└ StringBuilder란?

: StringBuilder를 사용하면 문자열을 조합할 때마다 새로운 변수를 생성하지 않고 결합할 수 있다.

--> 내부에 함수가 존재해서 값들을 조합하거나 삭제할 때에도 새로운 인스턴스가 생성되지 않는다.

 

▶ StringBuilder 사용법

- StringBuilder 사용 전 선언

: StringBuilder 클래스는 'System.Text' 네임스페이스에 정의되어 있기에 선언해야 한다.

using System.Text;

 

- StringBuilder 초기화

//빈 StringBuilder 생성
StringBuilder sb1 = new StringBuilder();
//string 변수로 value 설정하며 초기화
StringBuilder sb2 = new StringBuilder("StringBuilder");
//int 값으로 capacity 값을 설정하며 초기화
StringBuilder sb3 = new StringBuilder(10);
//int 값으로 capacity와 MaxCapacity 값을 설정하며 초기화
StringBuilder sb4 = new StringBuilder(10, 100);
//value와 capacity 값을 설정하며 초기화
StringBuilder sb5 = new StringBuilder("테스트 중", 100);
//value를 시작 인덱스(3)부터 길이(6)만큼 뗀 substring으로 초기화
//capacity는 20으로 초기화
StringBuilder sb6 = new StringBuilder("Hello World!", 3, 6, 20);

//콘솔 출력
Console.WriteLine(sb6);
Console.WriteLine(sb6.ToString());
//string 변수와 + 연산
string txt = "Hel" + sb6 + "ld!";
Console.WriteLine(txt);

 

--> 출력 결과물

 

- StringBuilder 속성

• Length 값은 string과 동일한 속성으로, 현재 StringBuilder 인스턴스의 텍스트 길이를 반환한다.
• Capacity 값은 StringBuilder 인스턴스가 현재 저장할 수 있는 최대 텍스트 길이를 반환한다. 생성 시에 따로 초기화하지 않았다면 Default 값은 16에서 시작하며, 다뤄야 할 문자열의 크기가 클 것으로 예상된다면, 해당 값을 처음부터 큰 값으로 초기화하여 Capacity를 늘리는 작업이 빈번하게 생기는 것을 막는다. --> List와 마찬가지로 StringBuilder 클래스는 내부적으로 고정된 저장공간을 가지고 있으며, 텍스트 추가로 이를 넘어서는 순간 추가로 공간을 할당한 후 기존 영역에 연결하는 방식이다.
• MaxCapacity 값은 StringBuilder 인스턴스의 Capacity가 최대 얼마까지 늘어날 수 있는지를 나타낸다. 생성 시 따로 초기화하지 않았다면 Default 값은 2,147,483,647(int형의 최대값)로, 웬만해서는 넘어갈 일이 없을 정도의 크기다.

StringBuilder sb = new StringBuilder("abcd");
//현재 텍스트 길이
Console.WriteLine(sb.Length);
//인스턴스의 현재 capacity
Console.WriteLine(sb.Capacity);
//StrigBuilder의 최대 capacity
Console.WriteLine(sb.MaxCapacity);

 

 

--> 출력 결과물

 

- StringBuilder의 함수

• Append() 함수를 통해 해당 StringBuilder 인스턴스의 텍스트 뒤에 문자열을 추가할 수 있다.
• AppendLine(string) 함수를 통해 현재 StringBuilder 개체의 끝에 지정한 문자열의 복사본과 기본 줄 종결자를 차례로 추가한다.
• Insert() 함수를 통해 원하는 위치에 문자열을 삽입할 수 있다.
• Remove() 함수를 통해 원하는 인덱스로부터 원하는 길이만큼의 문자열을 제거할 수 있다.
• Replace() 함수를 통해 특정 문자(char)를 다른 문자로, 혹은 특정 문자열을 다른 문자열로 교체할 수 있다. --> 첫 번째 매개변수와 동일한 모든 값이 교체된다.
• Clear() 함수로 텍스트를 빈 문자열로 초기화할 수 있다. --> List와 마찬가지로 내용을 초기화해도 변화된 Capacity 값은 유지되므로, 큰 문자열을 저장했던 인스턴스를 초기화하고 작은 문자열을 저장하는데 사용하는 것은 부적절하다.

StringBuilder sb1 = new StringBuilder("Hello");
//텍스트 뒤에 문자열 추가
sb1.Append(" World!");
Console.WriteLine($"현재 텍스트: {sb1}");

//기존 텍스트에 문자열 삽입
sb1.Insert(0, "Hi ");
Console.WriteLine($"현재 텍스트: {sb1}");

//문자열 제거
sb1.Remove(3, 6);
Console.WriteLine($"현재 텍스트: {sb1}");

//문자열 교체
sb1.Replace("World", "Everyone");
Console.WriteLine($"현재 텍스트: {sb1}");

//인스턴스 초기화
sb1.Clear();
Console.WriteLine($"현재 텍스트: {sb1}");

 

--> 출력 결과물

 

string vs StringBuilder

>> string

: string은 값 타입이 아닌 참조 변수이다. 즉, 문자열을 붙이는 과정에서 매번 복사가 일어나게 되고 이전의 데이터는 GC(Garbage Collector)에 의해서 수집이 된다.

--> 따라서 문자열을 조합할 때마다 원본과 새로운 복사본을 생성하여 변수에 할당하는 방식이기 때문에 속도가 느릴 뿐만 아니라 Garbage도 많이 생성한다.

 

>> StringBuilder

: Append() 함수를 통해 문자열을 추가할 경우, 우리가 생각하던 원본에 추가하는 방식이기 때문에 매번 복사가 일어나지 않는다.

--> Capacity를 넘어설 때마다 늘리는 과정이 필요하지만 매번 원본을 통째로 복사하는 string에 비해서 작업 속도가 월등히 빠르다.

 

▶ 다만 StringBuilder가 무조건 string의 상위호환이란 것은 아닙니다. 우선 StringBuilder를 사용하려면 따로 System.Text 네임스페이스를 참조해야 하며, 짧은 크기의 문자열을 다루는 경우에는 string에 비해 딱히 유의미한 성능 향상을 기대할 수 없습니다. 또한 StringBuilder 클래스는 IndexOf(), LastIndexOf()와 같은 특정 문자를 찾는 기능을 지원하지 않기 때문에, 문자열 내에서 검색하는 작업에는 부적절합니다. 따라서 StringBuilder는 길이가 긴 문자열(혹은 런타임에 크기가 정해지는 문자열)을 빈번하게 수정해야 하는 경우에 사용하는 것이 바람직하다.

 

※ Garbage Collector (GC)

: 메모리의 할당, 해제를 관리하는 관리자로서, 사용자가 직접 메모리를 해제할 필요가 없도록 해준다. GC는 이름 그대로 Garbage를 수집하며, 여기서 Garbage의 정의는 '더 이상 참조할 수 없게 된 객체'이다.

--> GC 호출 시, 다른 스레드를 일시정지하고 GC가 실행되기 때문에 잦은 GC 호출은 프로그램의 성능을 하락시킬 수 있다.

 

>> Garbage Collector의 세대 구분

: GC는 효율적인 수집을 위해 객체들에 세대를 매긴다. 최근에 생성되어 가비지 컬렉팅을 아직 겪은 적이 없는 객체를 0세대, 가비지 컬렉팅을 1번 겪었지만 해제되지 않은 객체를 1세대, 2번 겪었지만 해제되지 않은 객체를 2세대라 한다.

--> 세대가 높아질수록, 즉 가비지 컬렉팅을 겪고도 생존한 객체들일수록 중요한 객체로 판단하는 방식이다. 기본적으로 가비지 컬렉팅은 0세대를 대상으로 먼저 시행되며, 그러고도 필요한 메모리를 확보할 수 없을 경우에 1세대까지 포함하여 시행, 1세대까지 포함하여도 메모리 확보가 불가할 때 2세대까지 포함하게 된다. 2세대까지 포함한 모든 가비지 컬렉팅 수행 시 아예 프로세스를 일시정지하고 우선적으로 수행하기 때문에, 순간적인 프레임 드랍 등이 일어나게 된다.

--> 또한 GC는 객체를 그 크기에 따라 85,000바이트(85kb)보다 작으면 SOH(Small Of Heap), 크거나 같으면 LOH(Large Of Heap)로 구분합니다. SOH는 위에서 언급한대로 할당 직후 0세대부터 시작하며, LOH의 경우 처음부터 2세대로 등록됩니다. 가비지 컬렉팅을 겪고 생존한 객체를 중요하다고 판단하듯이, 크기가 큰 객체는 중요한 객체라고 판단하는 방식입니다. 또한 가비지 컬렉팅 후 SOH들은 메모리 단편화를 없애기 위해 재배치되지만, LOH의 경우 옮기는 과정에 발생하는 오버헤드가 크기 때문에 가비지 컬렉팅 후 이동되지 않습니다.

출처 : https://sam0308.tistory.com/22

 

※ 참고한 블로그

https://sam0308.tistory.com/23

[C#] StringBuilder

 

정답 코드

using System.Text;

class Backjoon
{
    static void Main(string[] args)
    {
        StringBuilder answer = new StringBuilder();
        int count = int.Parse(Console.ReadLine());

        for (int i = 0; i < count; i++)
        {
            string[] input = Console.ReadLine().Split();
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            answer.AppendLine((a + b).ToString());
        }

        Console.WriteLine(answer.ToString());
    }
}