Red Salmon

출처 : https://www.acmicpc.net/problem/9935

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/9935.cpp

이 문제는 참 좋은 문제였다. 얼핏보면 매우 간단한 문제로 보였다. 그러나 자꾸 시간초과가 났고, 결국 문자열길이가 최대 백만이라는 점이 문제가 되고 있음 을 깨달았다.

초기 알고리즘은 폭발문자열을 찾고 그부분을 지우고 다시 찾고 지우고 이런식으로 진행했다. 생각해보니 찾는다는것 자체가 백만이라는 가정하에 너무도 늦게 찾을것 같았다.

그래서 생각한것이 스택처럼 다루는 것이다. 문자열을 하나씩 추가하고 끝문자를 기준으로하여 만약 폭발문자의 끝문자와 현재 스택으로쓰는 스트링의 끝문자가 같다면 폭발문자열과 같은지 그때만 비교를 하는것이다. 같다면 인덱스값을 조절하여 다시 저장하게 하는 방식으로 진행하였는데, 이렇게하니 상당히 빠른 속도를 보이며 정답을 맞았다.

이 키워드를 얻은 계기는 폭발문자열이 최대 40문자가 안된다는 점이었다. 그렇다면 폭발문자열만 자주 사용해주어도 되겠다고 생각하여 진행하였다.

참 괜찮은 문제라고 생각한다.

출처 : https://www.acmicpc.net/problem/1620

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1620.cpp

문자열 + 이진탐색 문제이다. 어려울건 없었다. 그냥 따로 분리를 하여 숫자용 하나 문자용 하나 두고 검색하여 정답을 출력하면 된다. 딱히 고민했던 에러사항도 없다.

다만 입력이 10만번에 출력도 그만큼이다. 즉 cin은 안되는데 대충보고 그냥 했다가 시간초과가 났다.

이 부분만 고쳐주면 된다. 

그리고 string형식은 그냥 <, > 으로 비교가 가능하지만  char * 형식은 저런 비교가 되지 않으니 반드시 strcmp를 써야 한다. 물론 string형식도 compare함수가 존재하지만 <, >로도 원하는 결과를 얻을수 있다.

마찬가지로 string은 =로 값을 대입할수있으나 char * 는 불가하므로  strcpy를 사용해야 한다.

참으로 C++은 편리한 것이다.  또한 이런정도 함수들은 알고 있어야 문제풀기 수월할 것이다.

출처 : https://www.acmicpc.net/problem/9933

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/9933.cpp

나는 문제 선정할때 제출 횟수와 정답률을 보고 난이도를 짐작한다. 그래서 문제를 선정하고 푸는데.. 이건 뭐지...

무척이나 쉽다. 그런데 제출에 비해 정답률이 엄청 낮다... 이유를 모르겠다.. 뭐 난해한것도 없고, 혼동되는 부분도 전혀 없다. 

문제는 단어가 입력으로 주어지는데 항상 홀수로 입력이 들어오고(중요하지 않다.) 그 중 하나의 단어는 역으로 돌리면 중복이 발생하는데 그 단어를 찾으라는 것이다. 즉 어떤 단어는 las가 오면 입력에 sal도 있고 이건 같은 단어로 보고 그 단어의 길이와 가운데 글자를 출력하라는 것이다.

해결책도 간단하다. 맵에다가 입력들어오는 모든 단어를 추가하는데 역으로 변환해서 한번 더 추가해준다. 그러면 결국 언젠가는 어떤 중복되는 단어가 발생할테고 그 값이 2라면 중복을 찾은것으로 간주하고 출력하면 된다.

내가 한번 틀린건 가운데 글자만 출력하게 프로그래밍을 해서 틀렸다. 틀릴 이유도 없는건데.. 모두들 나와 같은 실수를 한건가보다..

출처 : https://www.acmicpc.net/problem/6527

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/6527.cpp

그냥 오랜만에 영어문제와 문자열 놀이 문제를 풀어보고 싶었다. 

문제는 그리 어렵지 않다. 그냥 단어들을 추려내서 불쉿이라고 하기전에 몇개의 단어가 쓰이는지 확인하고 카운팅시켜주고, 중복은 피한다. 그리고 불쉿이되면 게임이 종료된걸로 간주한다. 그러면 단어를 처음부터 다시 입력받고 위 과정을 계속 반복한다.

그리고 문제에 맞춰서 풀면 된다. 간단한 문제이다.