좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtpzyo 같은 비밀번호를 무작위로 부여해 주기도 하지만, 사용자들은 이를 외우는데 어려움을 느끼고 심지어는 포스트잇에 적어 컴퓨터에 붙여놓는다. 가장 이상적인 해결법은 '발음이 가능한' 패스워드를 만드는 것으로 적당히 외우기 쉬우면서도 안전하게 계정을 지킬 수 있다.
회사 FnordCom은 그런 패스워드 생성기를 만들려고 계획중이다. 당신은 그 회사 품질 관리 부서의 직원으로 생성기를 테스트해보고 생성되는 패스워드의 품질을 평가하여야 한다. 높은 품질을 가진 비밀번호의 조건은 다음과 같다.
모음(a,e,i,o,u) 하나를 반드시 포함하여야 한다.
모음이 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;
}
그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, 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;
}
청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.
N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.
각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.
모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.
<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.
<그림 2>
<그림 3>
<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.
<그림 4>
<그림 5>
<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.
이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.
입력
첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)
그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.
그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.
그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.
맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.
출력
1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.
접근 방법
1단계 : 4방향 검사
현재 상어를 방향을 기준으로 우선위에 따라 돌아가면서 다음 칸을 검사한다.
돌면서 내 냄새와 같은 칸이 나오면 그 값을 저장한다. 그리고 계속 검사한다. 왜냐하면 빈칸이고 냄새가 없는 칸이 나올수도 있기 때문이다. 후자의 경우가 더 우선순위가 높으므로 검사를 멈추면 안된다. (4방향 중 또 내 냄새와 같은 칸이 나오면 그 값은 그냥 건너 뛴다. 이미 우선순위에 의해 이동할 위치가 정해졌으므로)
돌면서 빈칸이고 냄새가 없는 칸이 나오면 현재 칸은 상어가 없는것으로 표시하고 이 경우가 가장 우선순위가 높으므로 다른 방향을 조사할 필요 없이 검사를 중단한다.
2단계
CASE 1
위에서 상어가 없고, 냄새도 없는 칸을 찾은 경우에는 해당 상어의 위치 정보를 바꿔주고(이차 배열은 아직 안바꿈), 임시 벡터를 만들어서 해당 칸에 상어 번호를 넣는다. (나중에 가장 작은 상어만 남겨놓고 다 내보내기 위함)
CASE 2
CASE1 에 해당하지 못할 경우에는 내냄새와 같은 칸으로 이동해야 한다. 1단계에서 값을 저장해놓았으므로 상어 객체 정보를 갱신한다.
CASE 3
이외 상황은 문제에서 조건으로 주어지지 않았으므로 고려하지 않아도 된다.
3단계
M개의 상어에 대해 어디 위치로 이동해야할지 조사가 다 끝났으니 정보를 갱신해야한다.
아까 위의 2단계-CASE1 에서 가장 번호가 작은 상어만 남겨놓고 나머지는 내보내는 것을 안 했으니 3단계에서 수행해준다. 임시 3차원 벡터 tmp를 돌면서 그 칸의 후보가 1이면 그냥 넣어주고, 2이상이면 상어 번호들을 비교해서 가장 최소 번호 상어만 남기고 다 지운다. (goOut()에서 수행한다.)
또한 내보낸 상어들 수를 카운트해서 처음 상어에서 빼준다.
4단계
이제 냄새를 1씩 감소해준다. 이때 주의할 점은 상어가 있는 칸을 제외하고 1을 감소시켜줘야 한다.
위 단계들을 반복하면서 남은 상어가 1마리인데 그 상어 번호가 1일 때까지 반복하며, 1000번 넘게 반복하면 스탑한다.
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
class Shark {
public:
int r, c, d;
int dirArr[5][5];
bool live;
Shark() {}
Shark(int _r, int _c, int _d, int _dirArr[5][5], bool _live) {
r = _r;
c = _c;
d = _d;
for (int i = 1; i <=4; i++) {
for (int j = 1; j<=4; j++) {
dirArr[i][j] = _dirArr[i][j];
}
}
live = _live;
}
};
pair<int, pair<int, int>> sharkMap[21][21]; //현재 상어 번호
Shark sharkArr[400];
int N, M, k;
//x, 위 아 왼 오
int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,-1,1 };
//1초 지나서 k감소
void decreaseK() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (sharkMap[i][j].first==-1 && sharkMap[i][j].second.second > 0) { //상어가 떠난 자리에 냄새가 남아있는 칸이면
sharkMap[i][j].second.second -= 1;
}
}
}
}
void goOut(vector<int> vec, int left, int nr, int nc) { //vec 중에서 left 빼고 다 내보내기
//sharkArr 처리
for (int i = 0; i < vec.size(); i++) {
if (vec[i] != left) { //나머지들 내보내기
sharkArr[vec[i]].live = false;
}
}
//sharkMap 처리
sharkMap[nr][nc] = make_pair(left, make_pair(left, k));
}
int main() {
cin >> N >> M >> k;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int sharkNum; cin >> sharkNum;
if (sharkNum != 0) {
sharkMap[i][j] = make_pair(sharkNum, make_pair(sharkNum, k));
sharkArr[sharkNum].r = i;
sharkArr[sharkNum].c = j;
sharkArr[sharkNum].live = true;
}
else {
sharkMap[i][j] = make_pair(-1, make_pair(-1, 0));
}
}
}
//상어 m 마리의 방향
for (int i = 1; i <= M; i++) {
int dir; cin >> dir;
sharkArr[i].d = dir;
}
//상어 m 마리의 우선순위
for (int m = 1; m <= M; m++) {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
cin >> sharkArr[m].dirArr[i][j];
}
}
}
int leftSharkCnt = M; //격자 안에 남아있는 상어 수
int sec = 0;
while (sec <= 1000) {
if (leftSharkCnt == 1 && sharkArr[1].live == true) break;
vector<int> tmp[21][21]; //움직이고나서의 상어 번호 저장
//상어 1번부터 M번까지 동시에 이동
for (int s = 1; s <= M; s++) {
if (sharkArr[s].live == false) continue; //이미 나간 상어
pair<int, int> sameSmellLoc = make_pair(-1, -1);
int toSameSmellmoveDir = 0;
int curR = sharkArr[s].r;
int curC = sharkArr[s].c;
int curD = sharkArr[s].d;
//아무것도 없는 빈 칸(k<=0) -> 자신의 냄새 있는 칸
bool isEmpty = false;
int nr, nc, nd;
//1단계
for (int i = 1; i <= 4; i++) {
nd = sharkArr[s].dirArr[curD][i];
nr = curR + dr[nd];
nc = curC + dc[nd];
if (nr <= 0 || nr > N || nc <= 0 || nc > N) continue;
if (sharkMap[nr][nc].first == -1 && sharkMap[nr][nc].second.second<=0) { //빈칸이고 냄새 없음
isEmpty = true;
sharkMap[curR][curC].first = -1; //현재칸 상어 없애기
break;
}
else if (sharkMap[nr][nc].second.second >= 0 && sharkMap[nr][nc].second.first == s) {
if (sameSmellLoc.first == -1) { //내냄새와 같은 첫 위치만 저장
sameSmellLoc.first = nr;
sameSmellLoc.second = nc;
toSameSmellmoveDir = nd;
}
}
}
//2단계
if (isEmpty == false) {
//위에서 저장한 내 냄새가 있는 칸으로 이동
sharkMap[sameSmellLoc.first][sameSmellLoc.second] = make_pair(s, make_pair(s, k));
sharkArr[s].r = sameSmellLoc.first;
sharkArr[s].c = sameSmellLoc.second;
sharkArr[s].d = toSameSmellmoveDir;
sharkMap[curR][curC].first = -1; //이동 후 현재 위치 있던거 삭제
}
else {
sharkArr[s].r = nr; sharkArr[s].c = nc; sharkArr[s].d = nd;
tmp[nr][nc].push_back(s); //일단 후보들 킵
}
}
//3단계
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (tmp[i][j].size() == 0) continue;
else if (tmp[i][j].size() == 1) {
int shark_num = tmp[i][j][0];
sharkMap[i][j] = make_pair(shark_num, make_pair(shark_num, k));
}
else { //2개 이상
int mini = 1000;
for (int k = 0; k < tmp[i][j].size(); k++) {
if (mini > tmp[i][j][k]) mini = tmp[i][j][k];
}
goOut(tmp[i][j], mini, i, j); //(i,j)에 mini번 상어만 남기기
leftSharkCnt = leftSharkCnt - tmp[i][j].size() + 1; //한개만 빼고 다 내보냄
}
}
}
//4단계
//상어 이동 완료 후
decreaseK();
//모든 상어 동시에 이동 후 sec 증가
sec++;
}
if (sec > 1000) cout << -1;
else cout << sec;
return 0;
}
