알파벳 소문자로 이루어진 문자열 Str과, 영어 알파벳 각각의 너비를 저장한 배열 widths[]가 주어집니다. 이 문제의 목표는 폭이 10인 페이지에 해당 문자열을 출력할 때 필요한 줄(line)의 개수를 구하고, 마지막 줄에 남는 너비도 함께 출력하는 것입니다.
해결 방법은 간단합니다. 문자열을 처음부터 끝까지 순회하면서 현재 문자의 너비를 누적하고, 누적된 값이 10에 도달하면 줄 수를 하나 증가시키면 됩니다.
예제를 통해 자세히 살펴보겠습니다.
입력
Str = "ababababab"
widths[] = {2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1};출력
Count of lines: 2 Remaining width: 6
설명
line 1 : ababab (2+1+2+1+2+1 = 9) line 2 : abab (2+1+2+1)
입력
Str = "bbbbbbbbbbdd"
widths[] = {2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1};출력
Count of lines: 2 Remaining width: 2
설명
line 1 : bbbbbbbbbb (1+1+1+1+1+1+1+1+1+1 = 10) line 2 : dd (1+1)
접근 방법
위 프로그램에서 사용한 접근 방식은 다음과 같습니다.
- 문자열 Str과 각 알파벳의 너비를 담은 배열 widths[]가 주어집니다.
- numberOfLines(string str, int len, int w[]) 함수는 필요한 줄의 개수와 마지막 줄의 남은 너비를 화면에 출력합니다.
- 줄 수를 나타내는 변수 numoflines를 0으로 초기화합니다.
- 마지막 줄의 너비를 나타내는 변수 remain을 0으로 초기화합니다.
- for 반복문을 사용해 문자열 str을 순회합니다.
- 현재 문자 c를 str[i]로 가져옵니다.
- c의 너비를 num = w[c - 'a']로 구합니다.
- 구한 num 값을 remain에 더합니다.
- remain이 10 이상이 되면 줄 수를 1 증가시키고, remain을 현재 문자의 너비 num으로 갱신합니다.
- 반복문이 종료되면 최종 결과를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 필요한 줄의 개수를 구하는 함수
void numberOfLines(string str, int len, int w[]){
int numoflines = 0;
int remain = 0;
// 문자열 순회
for (int i = 0; i < len; i++){
char c = str[i]; // 현재 문자
int num = w[c - 'a']; // 현재 문자의 너비
remain += num;
if (remain >= 10){
numoflines += 1;
remain = num;
}
}
cout << "Count of lines: " << numoflines;
cout << endl << "Remaining width: " << remain;
}
int main(){
string Str = "abcdefghijklmnop";
int length = Str.length();
int widths[] = {2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1};
numberOfLines(Str, length, widths);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of lines: 3 Remaining width: 1
복잡도 분석
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 줄 수와 남은 너비를 저장하는 상수 크기의 변수만 사용하므로 공간 복잡도는 O(1)입니다.