(로그인 해야볼수있듬!)
해결방법 )
하나의 개구리는 한번의 울음소리 뿐만아니라 여러번 운다는 것이 문제의 힌트같다.
내가 선택한 방법은 전체울음소리와 check할 "croak"을 순차적으로 검사를 하고 원래 녹음된 울음소리에서 기본울음소리 패턴을 제거해 주는 방식을 하면서 답을 구했다. 한번 루프를 돌때마다 cnt를 증가해서 개구리 수를 구했다. (일단 연속되게 운 개구리 한마리를 먼저 걸러내주기 위해서!)
ex)
1)
기본울음소리위치 값과 녹음된 울음소리의 위치 값이 똑같다면 녹음된 울음소리에서 그 값을 빼준다.
그리고 pos 위치를 다음 검사 위치로 이동함!
2)
여기서 눈여겨 봐야할 곳은 녹음된 울음소리의 위치이다.
녹음된 울음소리는 Vector에 저장시키기 때문에 erase(a+i) 를 써서 i번째위치를 삭제시키고 그래서 자동으로 앞으로 당겨지게되어 size가 하나 줄어든다.
그리고 pos 현재위치값과 녹음된 울음소리 위치값이 다르기 때문에 반복인덱스를 하나 증가시킨다.
3)
기본울음소리위치 값과 녹음된 울음소리의 위치값이 똑같기 때문에 제거해주고 뒤에도 남은 위치값이 같으므로 전부 빼지게 된다.
이렇게 되면 녹음된 울음소리에는 “C”만 남게된다.
검사위치가 4까지가서 전부 탐색이 된것이고 5가되면 0으로 다시 만들어줘서 CROAK을 전부 제거했다라는 의미를 부여함
-> pos 위취가 0이면 재탐색 가능!
4)
C는 Pos 처음 값과 같기 때문에 빼준다.
최종적으로 녹음된 울음소리는 없기 때문에 전부 검사를 하게 된 것! 이고, 밑에 기본울음소리에서 검사위치가 0이 아니기때문에 완전한 CROAK을 못만들었다는 의미라서 -1을 출력한다. 만약 0이면 CROAK을 전부 제거했다라는 의미라서 다음 루프타는 것이 가능함
[예외의 경우]
처음부터 검사위치 값과 맞지 않아서, 예외의 경우가 발생하는데
(우리는 한루프를 돌고나서 POS위치가 0이면 CROAK을 전부제거됬다고 정의했기때문) 이는 flag 변수를 설정해서 한번이라도 같은 것이 없는것도 -1이 되게 설정해준다.
코드)
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 | #include<iostream> #include<vector> #include<string> using namespace std; char check[6] = "croak"; vector <char> v; int main() { int test_case; cin >> test_case; for(int t= 1; t<=test_case; t++) { bool flag = false; bool visit = false; int cnt = 0; int vsize = 0; int k = 0; int pos = 0; string str; cin >> str; int len = str.length(); for (int i = 0; i < len; i++) { v.push_back(str[i]); } while (!v.empty()) { vsize = v.size(); k = 0; // 만약 check와 같은 문자가 있으면 k 값으로 사이즈를 줄여주기위해서 필요함 pos = 0; flag = false; visit = false; for (int i = 0; i < vsize - k; i++) { if (v[i] == check[pos]) { v.erase(v.begin() + i); k++; //size 하나 줄임 i--; // i제자리 만들기위해 하나 빼줌 pos++; // pos는 다음 뺄것을 준비하기위해 그위치로 이동 if (pos == 5) { pos = 0;// 다뺏으면 0으로 돌린후 다음 울음소리를 빼기위해 쎗팅! } visit = true; // 이 문자는 있다. } } //한루프가 끝나면 pos 위치 확인 if (pos != 0 || visit == false) { flag = true; break; } cnt++; } if (flag) { printf("#%d -1\n", t); v.clear(); } else printf("#%d %d\n", t, cnt); } } | cs |
'PS > SWEA' 카테고리의 다른 글
| 2007번 패턴 마디의 길이 (0) | 2018.10.16 |
|---|---|
| 1859번 백만 장자 프로젝트 (0) | 2018.10.13 |
| 1926번 간단한 369게임 (0) | 2018.10.05 |
| 1868번 파핑파핑 지뢰찾기 (0) | 2018.09.30 |
| SWEA - 혜리의 숫자 나누기 (0) | 2018.09.23 |