문제 링크 : https://codeforces.com/contest/1281 A. Suffix Three 문제 요약 문장의 접미사를 체크하여 어느 나라 언어인지 출력하는 문제이다. 접근 방법 string을 reverse한 후 맨 앞에서부터 차례대로 체크하면 해결될 것 같았다. 시간복잡도 계산하기 복잡하지만, std::reverse 가 O(n)이라고 가정하고(O(1)이라는 이야기도 있지만 어떻게 구현되었는지 몰라 O(n)이라고 두자..) std::string::find도 아래의 코드 상에선 O(n)보다는 작을 것이라 생각하면(무조건 접미사가 일치할 것이라고 문제에서 주어졌으므로) O(n) 정도 될 것 같다. #include #include #include using namespace std; void s..
문제 링크 : https://codeforces.com/contest/1265 A. Beautiful String 문제 요약 '?'을 'a', 'b', 'c' 중 하나로 치환하여 인접한 두 문자가 같지 않도록 만들 수 있는지 확인하고, 가능하면 그 값을 출력하는 문제이다. 접근 방법 문자열이 A[1]부터 A[N]까지 있다고 하면(N은 입력받은 문자열의 길이), A[0]과 A[N+1]에는 더미 문자를 미리 삽입하면 A[1]과 A[N]에서도 양 옆의 문자열을 확인하면 되므로 따로 처리를 할 필요가 없어진다고 생각하였다. 시간복잡도 이미 입력 받은 값이 불가능한 값인지 체크하는 부분이 O(n)이고, 값을 생성하는 부분이 O(n)이므로 총 O(n)이 걸린다고 생각한다. #include #include using..
문제 링크 : https://codeforces.com/contest/1255 A. Changing Volume 문제 요약 임의의 음량 크기에서 자신이 원하는 음량 크기로 맞추는 데 필요한 최소 버튼 클릭 횟수를 구하는 문제이다. 접근 방법 무조건 큰 단위의 버튼을 누르는 게 유리하므로 -5 크기의 버튼을 음량의 차가 5 미만이 될 때까지 누르고, 5 미만이 되면 차에 따라 값을 구하면 될 것 같았다. 시간복잡도 O(1) #include #include using namespace std; int solution(int A, int B) { if(A == B) return 0; if(A < B) swap(A, B); //A가 B보다 크도록 int ret = (A - B) / 5; //무조건 -5를 누르는..