Red Salmon

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

정답 : https://github.com/stemp12/acmicpc.net/blob/master/2016.01/9442.cpp

이 문제도 쉽다. 아무래도 오늘은 쉬어가는 날인가보다. 잡는 문제마다 쉽다.

문제를 간략히 설명하면 n을 입력받고 string한문장을 입력받는다. string은 알파벳인데, ABC가 아니라 저렇게 입력하는게 새로운 알파벳 순서가된다.

그다은 n개의 단어가 입력이 되는데 그 단어를 새로 입력받은 알파벳 순서대로 정렬하면 되는 문제이다.

sort함수를 쓰고 cmp 만 따로 처리해주면 간단히 해결되는 문제다.

단, 비교하는 문장이 같을 경우는 true가 아니라 false를 리턴해줘야한다. 

        idx1++; idx2++;
        if (idx2 == str2.length()) return false;
        else if (idx1 == str1.length()) return true;

그래서 나는 이렇게 표현하였는데 만약 idx2의 인덱스가 길이와 같아졌다면(아마 그럼 위 포문에서 결과가 나오지 않은 경우 즉 전부 동일한 경우이다.) 이 경우는 false를 리턴해준다고 하였다. 분명 모두 동일하다면 idx1과 idx2가 동일하겠지만, idx1를 먼저 쓰게 되면 같은경우 true를 리턴하게 되어 함수가 비정상 종료가 된다. 이 점만 주의하면 된다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/1931.cpp

이 문제는 전형적인 그리드알고리즘이다. 그리고 아주 기초 그리드 알고리즘이다. 

먼저 입력을 종료값기준으로 정렬시킨다. 그리고 임시 변수에 종료값을 담아 두어, 계속 비교를 한다. 그런데 여기서 시작시간과 종료시간이 같을수도 있다고 하였으니 <= 식으로 표현해야 한다. 

그런식으로 표현을 하게 되면 종료시간이 제일 빠른 녀석을 처음에 고르게 되고, 그 종료시간으로부터 다음 시작을 하면서 종료시간이 제일 빠른녀석을 고르게 되므로 최대의 경우의수를 구할수있다.

n이 10만이기때문에 재귀로는 접근이 불가하고 이런식으로 풀어야한다.

그런데 여기서 재채점이 과거에 있었는데 나역시 정답이었다가 오답이되었다. (물론 지금은 다시 정답이다.)

요점은 이렇다.

1 1

1 2

2 2

2 3

이런식의 입력이 있을때 최대 선택이 몇개가 되야하는가다. 이건 x를 한번정렬을 해주면 된다. 그래서 있는것이 stable_sort인것이다. (참고 : http://www.cplusplus.com/reference/algorithm/stable_sort/)

x를 먼저 정렬해준수 stable_sort를 써서 y정렬을 해주면 깔끔하게 해결이 된다. 과거 stable_sort와 비슷하게 구현해봤는데 정말 귀찮았었던 기억이 있다. STL을 공부해두면 여러모로 편하다.