개발 블로그

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

문제

암호학에서 치환 암호(substitution cipher)란, 평문에 들어있는 각각의 문자를 주어진 치환 방법으로 암호화하는 방법 중 하나다.

가장 단순한 방법은 평문의 알파벳을 암호문의 알파벳으로 대치시켜 치환시키는 것이다.

예를 들어, 아래와 같은 알파벳 대치표가 주어졌다고 하자.

• 평문 알파벳 대치표 : abcdefghijklmnopqrstuvwxyz
• 암호문 알파벳 대치표 : wghuvijxpqrstacdebfklmnoyz

위에 주어진 치환 방법을 통해 암호화하면 평문 "hello there"은 "xvssc kxvbv"가 된다.

한 가지 흥미로운 점은 영어 문법 특성상, 알파벳 'e'가 다른 영문 알파벳에 비해 자주 쓰인다는 것이다.

즉, 암호문 알파벳 대치표 없이 암호문을 복호화하려 할 때, 암호문 알파벳 빈도수를 체크하면 암호문 알파벳 빈도수 중 가장 빈번하게 나타나는 알파벳이 'e'라는 사실을 유추해볼 수 있다.

위 방법으로 암호문 알파벳의 빈도수를 체크하고, 가장 빈번하게 나타나는 문자를 출력하는 프로그램을 작성하면 된다.

만약 주어진 암호문에서 가장 빈번하게 나타나는 문자가 여러 개일 경우, 그 빈번한 문자 중 어느 것이 평문 알파벳 'e'를 가리키는지 확실하게 알 수 없기 때문에 "모르겠음"을 의미하는 '?'를 출력하면 된다.

입력

입력의 T(1 ≤ T ≤ 20)는 테스트 케이스로, 입력 제일 상단에 주어진다. 각각의 테스트 케이스는 한 줄마다 소문자와 공백으로 이루어진 영어 문장이 주어진다. 이 문장의 길이는 적어도 1이상이며 255이하다.

출력

각각의 테스트 케이스에 대해, 가장 빈번하게 나타나는 문자를 출력하거나 빈번하게 나타나는 문자가 여러 개일 경우 '?'를 출력한다.

접근 방법

주의할 점 : getline(cin, str)으로 공백 포함한 한 줄을 받기 전에, cin>>T 이후의 입력 버퍼를 비우도록 하자!! 입력 버퍼 비우지 않으면 입력한 값을 T에 저장하고 남은 '\n'가 밀려서 그 다음의 getline(cin, str)의 str로 들어가게 돼서 입력값이 하나씩 밀리는 문제가 발생한다. 자세한 내용은 아래의 링크를 참고하자.

https://namwhis.tistory.com/entry/cin%EA%B3%BC-getline%EC%9D%84-%EA%B0%99%EC%9D%B4-%EC%82%AC%EC%9A%A9%ED%95%A0%EB%95%8C-cinignore%EC%9D%B4-%ED%95%84%EC%9A%94%ED%95%9C-%EC%9D%B4%EC%9C%A0-%EA%B8%B0%EB%A1%9D

1) T를 입력받은 후, cin.ingnore()을 이용하여 입력 버퍼를 비워준다. (다음에 공백을 포함한 문자열을 받아야 하기 때문에)

2) 각 테스트케이스는 소문자와 공백이므로, 각 소문자를 배열의 인덱스로 삼아서 ('a'가 아스키코드로 97이므로 97을 뺀 수를 인덱스로 삼는다) 해당 소문자가 몇번 나왔는지 수를 배열에 저장한다.

3) 가장 빈번하게 나타나는 문자가 여러개인지를 판단하기 위해 벡터에 pair를 넣는다. pair의 first는 문자가 출력된 수, pair의 second는 그 문자를 저장한다.

4) 벡터를 내림차순 정렬한다.

5) 가장 빈번하게 나타나는 문자가 여러개이면 vec[0].first 와 vec[1].first가 같을 것이기 때문에 이 경우에는 ?를 출력한다.

6) 이외에는 가장 빈번한 문자인 vec[i].second를 출력한다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

int alphaCntArr[26] = {0,};
//a = 97
int main(){

   int T; cin >> T; cin.ignore();
   for(int t=1; t<=T; t++){
       memset(alphaCntArr, 0, sizeof(alphaCntArr));
       string str;
       getline(cin, str);

       for(int i = 0; i<str.length(); i++){
           if(str[i] == ' ') continue;

           alphaCntArr[str[i]-97]++;
       }

        vector<pair<int,char>> vec;
       for(int i = 0; i<26; i++){
           vec.push_back(make_pair(alphaCntArr[i], i+97));
       }

        sort(vec.begin(), vec.end(), greater<>());

        if(vec[0].first==vec[1].first){
            cout << "?\n";
        }
        else {
                cout << vec[0].second << "\n";
        }
   }

    return 0;
}

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

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

접근 방법

substr()함수를 이용해서 풀 수 있는 간단한 문자열 비교 문제였다. 그런데 생각보다 정답률이 낮아서 의아했는데 문제를 풀어보니 주의할 점을 고려해주지 않으면 오답처리되기 쉽다는 것을 알 수 있었다. 문제 조건을 꼼꼼히 확인하는것이 중요하다는 것을 새삼 깨달을 수 있게 해주는 문제였다. 주의할 점은 다음과 같이 두 개 정도 있다.

주의할 점 1)

문서의 길이가 단어 길이보다 작은 경우에는 예외 처리를 따로 해줘야 한다. 이 부분을 고려해주지 않아서 런타임 에러가 났다.

주의할 점 2)

일치하는 문자열을 찾은 뒤, 중복되지 않도록 단어의 길이만큼 문서를 스킵하기 위해 인덱스를 임의로 조정해주는데, 

이때 i+=wordLen이 아닌 i+=(wordLen -1)만큼만 증가시켜줘야한다.

왜냐하면 어짜피 for문 안에서 i++라는 증감식에 의해 인덱스가 1 증가하기 때문이다.

//
//  문자열_BOJ1543_문서검색.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
using namespace std;

int main(){

    string documents, word;
    getline(cin,documents);
    getline(cin, word);
    
    int ans = 0;
    
    int wordLen = (int)word.length();
    
    if(documents.length() < wordLen) cout << 0;	//1. 예외처리 해주지 않으면 런타임에러
    else{
        for(int i = 0; i<=documents.length()-wordLen; i++){
            
            if(documents[i] == word[0]){
                string sub = documents.substr(i, wordLen);
                if(sub==word){
                    ans++;
                    i += (wordLen -1);		//2. for문에서 어짜피 i증가되니까 여기서는 1 감소
                }
            }
        }
        
        cout << ans;
    }

    return 0;
}

문제 링크 : www.acmicpc.net/problem/4659

문제

좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtpzyo 같은 비밀번호를 무작위로 부여해 주기도 하지만, 사용자들은 이를 외우는데 어려움을 느끼고 심지어는 포스트잇에 적어 컴퓨터에 붙여놓는다. 가장 이상적인 해결법은 '발음이 가능한' 패스워드를 만드는 것으로 적당히 외우기 쉬우면서도 안전하게 계정을 지킬 수 있다. 

회사 FnordCom은 그런 패스워드 생성기를 만들려고 계획중이다. 당신은 그 회사 품질 관리 부서의 직원으로 생성기를 테스트해보고 생성되는 패스워드의 품질을 평가하여야 한다. 높은 품질을 가진 비밀번호의 조건은 다음과 같다.

1. 모음(a,e,i,o,u) 하나를 반드시 포함하여야 한다.
2. 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다.
3. 같은 글자가 연속적으로 두번 오면 안되나, ee 와 oo는 허용한다.

이 규칙은 완벽하지 않다;우리에게 친숙하거나 발음이 쉬운 단어 중에서도 품질이 낮게 평가되는 경우가 많이 있다.

입력

입력은 여러개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 테스트할 패스워드가 주어진다.

마지막 테스트 케이스는 end이며, 패스워드는 한글자 이상 20글자 이하의 문자열이다. 또한 패스워드는 대문자를 포함하지 않는다.

접근 방법

각 조건에 맞는 함수를 작성했다.

모음 또는 자음이 세번 연속 나오는 조건을 따지는 함수에서, 자음 나오다 모음 나온 경우 또는 모음 나오다 자음 나온 경우에 초기화를 해주는 것을 주의해야 한다.

#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;

bool onemoreComp(string str) {
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') {
			return true;
		}
	}
	return false;
}
bool threeConti(string str) {
	int consonant = 0;	//자음
	int collection = 0;	//모음
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') {
			if (consonant != 0) { //자음 나오다가 모음 나온 경우 -> 자음 초기화
				consonant = 0;
			}
			collection += 1;
		}
		else {	//자음
			if (collection != 0) {	//모음 나오다가 자음 나온 경우 -> 모음 초기화
				collection = 0;
			}
			consonant += 1;
		}

		if (consonant >= 3 || collection >= 3) return false;
	}
	return true;
}
bool twoConti(string str) {
	for (int i = 0; i < str.length()-1; i++) {
		if (str[i] == str[i + 1]) {
			if (str[i] == 'e' || str[i] == 'o') continue;
			else return false;
		}
	}
	return true;
}


int main() {

	vector<pair<string, bool>> vec;

	while (1) {

		string str;
		cin >> str;
		if (str == "end") break;

		if (onemoreComp(str) == false || threeConti(str) == false || twoConti(str) == false) {
			vec.push_back(make_pair(str, false));
		}
		else vec.push_back(make_pair(str, true));

	}
	for (int i = 0; i < vec.size(); i++) {
		cout << "<" << vec[i].first << "> is ";
		if (vec[i].second == true) cout << "acceptable.\n";
		else cout << "not acceptable.\n";
	}


	return 0;
}

문제 링크 : www.acmicpc.net/problem/1316

문제

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

출력

첫째 줄에 그룹 단어의 개수를 출력한다.

접근 방법

문자열을 입력받고 한 character 씩 검사한다. chkArr[26] 배열은 알파벳이 이미 나왔는지 검사하는 배열이다. 아스키코드를 고려해서 소문자 'a'가 97이므로 인덱스에서 97을 빼주는 것을 잊지 말자. 

'happy' 를 예로 들어보자.

h 는 나온 적이 없으므로 chkArr[7] = 1로 바꾼다. (h는 8번째 알파벳)

a 는 나온 적이 없으므로 chkArr[0] = 1로 바꾼다. (a는 1번째 알파벳)

p 는 나온 적이 없으므로 chkArr[15] = 1로 바꾼다. (p는 16번째 알파벳)

p 는 나온 알파벳인데 바로 전 글자와 같으므로 그룹 단어 조건에 어긋나지 않으므로 계속 검사를 진행한다.

y 는 나온 적이 없으므로 chkArr[24] = 1로 바꾼다. (y는 25번째 알파벳)

모든 글자가 다 통과했으므로 ans를 하나 증가시킨다.

'abac'를 예로 들어보자.

a 는 나온 적이 없으므로 chkArr[0] = 1로 바꾼다. (a는 1번째 알파벳)

b 는 나온 적이 없으므로 chkArr[1] = 1로 바꾼다. (b는 2번째 알파벳)

a 는 이미 나온 알파벳인데 전 글자와 다르므로 그룹 단어 조건에 어긋난다. 그러므로 chk=0로 설정하고 즉시 검사를 중단한다. 

chk!=1 이므로 ans를 증가시키지 않는다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	//a = 97

	int N;
	scanf("%d", &N);

	int ans = 0;
	int chkArr[26];

	for (int i = 0; i < N; i++) {

		memset(chkArr, 0, sizeof(chkArr));
		char str[101];
		scanf("%s", str);
		int idx = 0;
		int chk = 1;
		while (1) {
			
			if (str[idx] == '\0') { break; }

			char c = str[idx];
			if (chkArr[c - 97] == 1) {			//이미 나온 경우
				if (str[idx - 1] != str[idx]) {		//바로 전 글자와 같으므로 그룹임
					chk = 0;
					break;
				}
			}
			else {
				chkArr[c - 97] = 1;			//나온 적 없는 경우 1로 바꿈
			}

			idx++;
		}
		
		if (chk == 1) ans += 1;


	}
	printf("%d", ans);


	return 0;
}