Red Salmon

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

정답 : 

문제를 보면 인풋이 천만개이다. 그리고 더 읽어보면 10,000보다 작거나 같은 자연수라고 한다. 즉, 10000개의 숫자들을 가지고 천만개를 입력하게 되니 반드시 중복이 있다는 말이다. 

이 부분을 캐치해야 문제를 풀 수있다. 나는 맵을 사용하여 풀었는데, 맵을 사용하지 않고도 풀 수있다.

맵을 사용하지 않는다면 어차피 숫자는 10000개니까 bool 함수를 써서 인풋이 들어오면 그 부분을 참으로 맞춘다.

그리고 int배열을 하나만들고 해당 부분을 카운팅해준다.

입력이 끝나면 for(1만) 을 돌려서 bool이 참이면 그에따른 int배열의 개수만큼 그 수를 출력해주면된다. 

결국 입력은 천만번이지만 정렬도 없고 그냥 포문 1만번으로 답을 구할수있다.

그리고 이런 문제의 경우 인풋도 출력도 엄청많은데 cin, cout보다는 scanf와 printf를 센스있게 써줘야한다. 

속도면에서 엄청난 차이가 있다.

출처 : 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/2632

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

이 문제는 좀 괜찮은 문제같다. 어렵지 않으면서 이것저것 생각할것도 조금 있고, 코딩도 상당히 해야한다.

문제를 살펴보면 피자의 크기의 최대는 2백만이고, 피자조각의 최대크기는 1000조각이다.

그럼 n^2(1000^2)까지는 계산이 허용된다는 말이니 여기에 중점을 두고 생각해보자.

그리고 주목해야할 부분이 바로 피자의 조각을 뺄때는 연속으로만 뽑을 수 있다고 한다.

그럼 각 피자당 뽑을수있는 경우의수는 매우 제한적이게 될 것이다. 

먼저 피자가 총 2조각으로 이루어져있다면 1조각짜리 2개 2조각짜리 1개로 구성되어 3개이다.

그리고 총 3조각이라면 1조각짜리 3개 2조각짜리 3개 3조각짜리 한개여서 총 5조각이다. 

수식으로 구해보면 n*(n-1)+1이 성립한다.

그럼 최대 인풋이 1000이니 식을 구해보면 대략 100만이 조금 안되는 값이 나온다. 그렇다면 배열에 모든 경우의수를 담아볼수있다.

피자는 2개로 구성되어있으니 총 2백만개의 배열이 필요하다.

그렇게 하여 각 피자당 구할수있는 모든 조각의 크기를 미리 구해놓는다. 그리고 한개의 피자에서 한개의 조각을 꺼냈을때 남은피자에서 n-사용한 조각을 하면 현재 필요한 조각수를 알수있으므로 그 조각수가 나오는 경우가 있는지 살펴보면 된다.

즉!! 이진탐색문제이다. 그러므로 당연히 정렬이 필요하다. 미리 구해둔 모든 조각의 크기를 정렬하고 구하고자 하는 값을 찾아보면 된다. 이때 중복이 있을수 있으니, 중복에 대한 경우를 체크하도록 한다.

그리고 하나더

시간단축을 위해 이진탐색에서 찾을 값이 음수이거나, 최대크기보다 큰값이라면 구할수 없으니 종료를 한다.

뿐만아니라 나는 나중에 깨달았지만 미리 idx배열을 1부터 시작한다면 즉 0인값을 넣어놓는다면 하단부분 계산파트에서 0인경우를 나처럼 따로 처리하지 않아도 된다. 그럼 코드가 더 간략해질것이다.