백준 19948. 음유시인 영재
백준 19948. 음유시인 영재
1. 문제 분석
- 시는 대문자, 소문자 알파벳과 빈칸으로 이루어져 있다.
- 시에 나오는 단어들의 첫 글자를 대문자로 바꾼 뒤 순서대로 이어서 제목으로 만든다
- 만약 시의 내용이 ‘There is no cow level’ 이라면 시의 제목은 ‘TINCL’이 된다.
- 앞으로 스페이스 바와 영자판을 누를 수 있는 횟수가 정해져 있어 이를 초과하면 키보드가 수명이 다 하여 어떠한 작업도 하지 못하게 된다.
- 키보드를 쓸 때 같은 문자가 연속으로 나오거나 빈칸이 연속으로 나오는 경우, 영재는 자판을 꾹 눌러 한 번만 사용해서 키보드를 좀 더 효율적으로 쓸 수 있다.
- 시의 내용과 시의 제목은 Enter 키로 구분된다. Shift 키와 Enter 키는 항상 수명이 무한한 상황
- 이번에 지은 시의 내용과 스페이스 바와 영자판을 누를 수 있는 횟수가 주어졌을 때,
- 시의 내용과 제목을 모두 기록할 수 있다면 시의 제목을 출력하고, 만약 키보드의 수명이 다 하여 기록을 완벽하게 못 하게 된다면 -1을 출력하여라.
입력
- 첫 줄에 시의 내용이 주어진다
- 둘째 줄에는 스페이스 바의 남은 사용 가능 횟수 주어진다.
- 셋째 줄에는 대소문자를 구별하지 않고, 26개의 알파벳에 대한 영자판의 남은 사용 가능 횟수가 알파벳순으로 주어진다
출력
- 시의 내용과 제목을 모두 기록할 수 있다면 시의 제목을 출력하여라
- 만약 키보드의 수명이 다 하여 기록을 완벽하게 못 하게 된다면 작업을 하지 못한다면 -1을 출력하여라
주의사항
a a와 같이 빈칸이 연속으로 나오는 경우도 존재함- 제목도 입력해야 하므로, 키보드 타이핑 횟수에 추가해야한다고 함
2. 예시 분석
예시 1.
1
2
3
There is no cow level
5
1 0 2 0 4 3 0 1 2 0 0 3 0 2 2 0 4 1 1 2 0 1 1 0 0 0
단어는 5개, 스페이스바는 4개가 사용되었다.
스페이스바는 문제 없고, 사용된 단어의 개수를 살펴보면 다음과 같다
1
2
a b c d e f g h i j k l m n o p q r s t u v w x y z
0 0 1 0 4 0 0 1 1 0 0 2 0 1 2 0 0 1 1 1 0 1 1 0 0 0
내용을 모두 입력하고 나면 남은 키보드 횟수는 다음과 같다
1
2
a b c d e f g h i j k l m n o p q r s t u v w x y z
1 0 1 0 0 3 0 0 1 0 0 1 0 1 0 0 4 0 0 1 0 0 0 0 0 0
여기서 제목 TINCL 입력해야하므로 이를 입력하면
1
2
a b c d e f g h i j k l m n o p q r s t u v w x y z
1 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0
이 되므로, 키보드 횟수 내에서 입력할 수 있어 제목이 출력된다
예시 2.
1
2
3
Show me the money
2
0 1 0 4 3 0 0 2 0 0 0 0 4 1 2 0 0 0 1 2 0 0 1 0 1 2
스페이스바 3번 입력해야하는데 두번밖에 주어지지 않아 -1 출력 후 종료
예시 3.
1
2
3
show me the money
4
1 0 3 2 1 0 0 2 0 0 0 0 4 1 2 0 0 0 1 2 0 0 1 0 1 0
1
2
a b c d e f g h i j k l m n o p q r s t u v w x y z
0 0 0 0 3 0 0 2 0 0 0 0 2 1 2 0 0 0 1 1 0 0 1 0 1 0
사용된 알파벳 수보다 키보드 횟수가 적게 주어져서 타이핑 불가
예시 4.
1
2
3
aaa bac cab
3
4 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
스페이스바 개수 문제 없음
aaa는 연속된 입력이므로, 한번의 타이핑으로 처리 가능하다
내용을 입력하는데 a : 3, b : 2, c: 2가 필요하므로 입력 가능하다
이후 제목을 입력하는데 ABC도 각각 한번씩 남아있으므로 처리 가능
예시 5.
1
2
3
a b
1
4 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
스페이스바도 빈칸이 연속으로 나오는 경우로 명시되어있다. 주의
출력 : AB
3. 알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
13
1. 문장 입력받기
2. 스페이스바와 알파벳 개수를 체크한다
2-1. 스페이스바를 체크
- 빈칸이 연속입력되었는지 확인. 아니라면 개수 차감
- 스페이스바 횟수가 음수라면 -1 출력 후 종료
2-2. 알파벳 개수 체크
- 대문자라면 일단 소문자로 변환
- 이전 입력과 비교하여 같은지 확인, 아니라면 개수 차감
- 현재 알파벳 개수가 음수라면 -1 출력 후 종료
3. 키보드의 개수가 남아있다면, 제목을 타이핑해봄
3-1. 스페이스바 다음의 문자가 알파벳이라면, 단어의 시작이므로, 이를 대문자로 변환 후 가져온다
3-2. 키보드 개수를 차감해보면서 출력 가능한지 체크, 아니라면 -1 출력 후 종료
4. 제목 출력 후 종료
제목의 입력도 키보드에서 차감해야한다는 걸 디버깅하면서 발견해서
알고리즘을 조금 수정하는게 깔끔할 것 같다
1
2
3
4
5
6
7
8
9
10
11
12
1. 전처리
- 시의 내용 입력받기
- 입력 받은 시의 내용으로 다음 두가지를 미리 계산하여 저장
(A) : 본문 입력에 필요한 키보드 사용 횟수. 연속된 문자 처리에 주의
(B) : 제목 문자열 생성
2. 제목 입력에 필요한 키보드 사용 횟수 계산
- 생성된 (B) 문자열 기준으로, 연속 문자열 규칙을 적용하여, 제목 입력에 필요한 각 알파벳 사용 횟수 계산
3. 검증 및 결과 출력
- 주어진 키보드 사용 가능 횟수에서 (A)본문과 (B)제목에 필요한 총 사용 횟수를 모두 차감
- 차감 과정에서 어느 하나라도 횟수가 부족하다면 -1을 출력 후 종료
- 모든 키보드 사용 횟수가 충분하다면, (B) 제목 문자열을 출력
4. 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <string>
using namespace std;
string str;
int space_cnt, alpha[26];
char last_input = '.';
void Input() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
getline(std::cin, str);
cin >> space_cnt;
for (int i = 0; i < 26; i++) {
cin >> alpha[i];
}
}
int main() {
// 1. 입력받기
Input();
// 2. 개수 체크
for (int i = 0; i < str.size(); i++){
// 스페이스 체크. 빈칸이 연속으로 나오는 경우 한번으로 입력 가능
if (str[i] == ' ') {
if (last_input != ' ' && str[i] == ' ') {
space_cnt--;
last_input = ' ';
}
if (space_cnt < 0) {
cout << "-1";
return 0;
}
}
// 알파벳 체크
else {
char now = str[i];
// 소문자로 일단 변환
if (isupper(str[i])) {
now = tolower(str[i]);
}
int cur_idx = (int)(now - 97);
// 이전 알파벳이랑 같으면 차감하지 않음
if (last_input != now) {
alpha[cur_idx]--;
last_input = now;
}
if (alpha[cur_idx] < 0) {
cout << "-1";
return 0;
}
}
}
// 3. 키보드가 멀쩡하다면 제목을 출력
string result;
result += toupper(str[0]);
// 스페이스바 다음의 문자를 가져와 제목으로 만든다
for (int i = 1; i < str.size(); i++) {
if (str[i-1] == ' ' && str[i] != ' ') {
result += toupper(str[i]);
}
}
// 제목도 입력한다
for (int i = 0; i < result.size(); i++) {
int cur_idx = (int)(result[i] - 65);
alpha[cur_idx]--;
if (alpha[cur_idx] < 0) {
cout << -1;
return 0;
}
}
cout << result
return 0;
}
개선버전
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <string>
#include <vector>
#include <cctype> // isalpha, tolower, toupper 등의 함수를 위해 포함
// 시 내용으로 제목 문자열을 생성하는 함수
std::string generate_title(const std::string& poem) {
std::string title;
if (poem.empty()) {
return title;
}
// 첫 글자가 알파벳이면 제목에 추가
if (isalpha(poem[0])) {
title += toupper(poem[0]);
}
// 공백 다음의 알파벳을 찾아 제목에 추가
for (size_t i = 1; i < poem.length(); ++i) {
if (poem[i - 1] == ' ' && isalpha(poem[i])) {
title += toupper(poem[i]);
}
}
return title;
}
int main() {
// C++ 입출력 속도 향상
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// --- 1. 전처리 (Preprocessing) ---
std::string poem;
getline(std::cin, poem);
int space_limit;
std::cin >> space_limit;
std::vector<int> alpha_limit(26);
for (int i = 0; i < 26; ++i) {
std::cin >> alpha_limit[i];
}
// 제목 문자열 미리 생성
std::string title = generate_title(poem);
// --- 2. 본문/제목 타이핑 시뮬레이션 및 검증 ---
// 본문 타이핑
char last_char = '\0'; // 이전에 누른 키 (초기값은 NULL)
for (char c : poem) {
if (c == ' ') {
if (last_char != ' ') {
space_limit--;
}
last_char = ' ';
} else if (isalpha(c)) {
char lower_c = tolower(c);
if (last_char != lower_c) {
alpha_limit[lower_c - 'a']--;
}
last_char = lower_c;
}
// 키 사용 직후 바로 검사
if (space_limit < 0 || (isalpha(c) && alpha_limit[tolower(c) - 'a'] < 0)) {
std::cout << "-1";
return 0;
}
}
// 제목 타이핑 (Enter를 누른 후이므로 last_char는 초기화됨)
last_char = '\0';
for (char c : title) {
char lower_c = tolower(c);
if (last_char != lower_c) {
alpha_limit[lower_c - 'a']--;
}
// 키 사용 직후 바로 검사
if (alpha_limit[lower_c - 'a'] < 0) {
std::cout << "-1";
return 0;
}
last_char = lower_c;
}
// --- 3. 결과 출력 ---
std::cout << title;
return 0;
}
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.