728x90
요약: 어떤 string 하나가 주어졌을 때, 이 스트링의 모든 substring들이 distinct하도록(중복이 없도록) 만들기 위해, 원본 스트링에서 삭제해야하는 문자의 최소 갯수를 구하는 문제입니다. 원본 스트링에서 중복되는 알파벳이 하나라도 있는 경우 substring들이 중복되는 것은 자명합니다. 따라서 알파벳 26개의 frequency를 저장해서, 특정 알파벳의 frequency가 1개 초과인 경우에는 1개를 제외한 나머지를 삭제하는 방식으로 풀었습니다.
#include <bits/stdc++.h> // 모든 표준 라이브러리 헤더들을 가져오는 전처리문
using namespace std; // std라는 namespace에서 사용하려고 한다. 그냥 암기하면 됨
/*
어떤 string 하나가 주어졌을 때, 이 스트링의 모든 substring들이 distinct하도록(중복이 없도록) 만들기 위해,
원본 스트링에서 삭제해야하는 문자의 최소 갯수를 구하라
0. 아이디어
원본 스트링에서 중복되는 알파벳이 하나라도 있는 경우, substring들이 중복됨은 자명하다.
ex) 원본 스트링이 "aba"인 경우, substrings = { "a", "b", "a", "ab", "ba", "aba" }인데 여기서 substring "a"와 "a"가 중복된다.
따라서, 입력으로 주어지는 string에서, 모든 알파벳 a~z가 1개 이하여야 한다.
1. 알파벳 26개가 각각 몇 번씩 나왔는 지(frequency)를 카운팅하는 벡터 alphabet_cnt을 선언한다. 벡터의 크기는 26이고 초기값은 0
2. 입력으로 주어지는 string을 문자 하나씩 sweeping하면서(순서대로 읽으면서),
해당 문자가 'a'이면 alphabet_cnt[0]을 증가시켜주고,
해당 문자가 'b'이면 alphabet_cnt[1]을 증가시켜주고,
...
해당 문자가 'z'이면 alphabet_cnt[25]를 증가시켜준다.
3. alphabet_cnt[0]부터 alphabet_cnt[25]까지 읽으면서 (즉, 'a'의 갯수, 'b'의 갯수, ..., 'z'의 갯수를 보면서)
만약 특정 알파벳이 1개 초과(2개 이상)이면, 삭제해야하는 문자이므로
결과값 result에다가 alphabet_cnt[i] - 1을 추가한다. (왜 -1이냐면 1개는 남겨놔도 되므로)
*/
int getMinDeletions(string s) {
int n = s.size(); // 스트링 s의 크기를 저장. ex) 스트링이 "abab"이면 n은 4
vector<int> alphabet_cnt(26, 0); // 알파벳 26개의 frequency를 저장하는 벡터 alphabet_cnt를 선언하고, 초기값을 모두 0으로 지정
for (int i=0; i<n; i++) { //i는 0부터 시작해서, n 미만일동안 i를 하나씩 증가시킨다. (즉, 입력으로 주어지는 string을 문자 하나씩 sweeping하는 것)
/*
ex) s가 "abac"이면
s[0] = 'a'
s[1] = 'b'
s[2] = 'a'
s[3] = 'c'이다.
s[i]-'a'는 무엇을 의미하는가?
'a'는 아스키코드 값으로 변환하면 97이고, 'z'는 아스키코드로 123이다.
따라서 s[i]에서 'a'를 빼면, 알파벳 'a'~'z'를 0~25 사이의 숫자로 바꿀 수 있다.
참고로 s[i]-'a' 대신 s[i]-97로 대체 가능하다.
i=0인 경우, s[0]-'a'는 0 -> alphabet_cnt[0]을 +1시킨다. (alphabet_cnt[0]은 1이 됨)
i=1인 경우, s[0]-'a'는 1 -> alphabet_cnt[1]을 +1시킨다. (alphabet_cnt[1]은 1이 됨)
i=2인 경우, s[0]-'a'는 0 -> alphabet_cnt[0]을 +1시킨다. (alphabet_cnt[0]은 2가 됨)
i=3인 경우, s[0]-'a'는 2 -> alphabet_cnt[2]을 +1시킨다. (alphabet_cnt[2]은 1이 됨)
*/
++alphabet_cnt[s[i]-'a'];
}
int result = 0; //결과값을 저장할 변수 (원본 스트링에서 삭제해야하는 문자의 갯수)
for (int i=0; i<26; i++) { //alphabet_cnt[0]부터 alphabet_cnt[25]까지 읽으면서 (즉, 'a'의 갯수, 'b'의 갯수, ..., 'z'의 갯수를 보면서)
if (alphabet_cnt[i] > 1) { // 현재 알파벳의 frequency가 1보다 크면, 삭제해야하는 문자이므로
result += (alphabet_cnt[i] - 1); // 결과값 result에다가 alphabet_cnt[i] - 1을 추가한다
}
}
return result; //결과값을 리턴
}
int main()
{
string s; //스트링 s 선언
cin >> s; //스트링 입력
int answer = getMinDeletions(s); // getMinDelettion 함수 호출해서 결과값을 answer 변수에 저장
cout << answer; // 출력해서 확인
return 0; //정상 종료됨을 의미하는 return 0
}
주석 제거용
#include <bits/stdc++.h>
using namespace std;
int getMinDeletions(string s) {
int n = s.size();
vector<int> alphabet_cnt(26, 0);
for (int i=0; i<n; i++) {
++alphabet_cnt[s[i]-'a'];
}
int result = 0;
for (int i=0; i<26; i++) {
if (alphabet_cnt[i] > 1) {
result += (alphabet_cnt[i] - 1);
}
}
return result;
}
int main()
{
string s;
cin >> s;
int answer = getMinDeletions(s);
cout << answer;
return 0;
}'알고리즘' 카테고리의 다른 글
| [2021 ICT 하반기] 5번 문제 (0) | 2021.07.16 |
|---|---|
| [2021 ICT 하반기] 4번 문제 (0) | 2021.07.16 |
| [2021 ICT 하반기] 3번 문제 (0) | 2021.07.15 |
| [2021 ICT 하반기] 1번 문제 (0) | 2021.07.15 |
