컴퓨터공부하기

각각의 카드문양과 숫자를 저장하기 위한 2차원 배열 card[4][14]를 이용하여 각 문양에 해당하는 카드를 입력받아 개수를 카운트한다.

그런 후, 2개 이상의 중복된 카드가 있으면 오류,

오류가 아니라면 부족한 카드 개수를 출력한다.

Day가 11<= D <= 14이기 때문에, 연도, 월은 따로 계산해 주지 않아도 되서 편하다.

단순하기 분단위로 차이를 계산하였다.

문자열을 입력받아 첫번째부터 모음인지 확인 후, 모음이 아니면 출력, 모음이면 넘어간다.

시간복잡도 O(n)

n개를 입력받아 내림차순으로 정렬후에

큰수부터 k개를 더해서 최대 총점을 계산한다.

?는 와일드 카드로 하나의 임의의 문자가 된다.

문자열을 입력받은 후 

가장 앞을 가르키는 변수 i와 맨뒤를 가르키는 변수 j를 둬서

i++ , j--하면서 문자를 1대1로 비교한다.

같으면 둘이 만날때 까지 반복하며,

다른 경우 '?' 키워드 인 경우에는 계속 탐색, 서로 다른 문자일 경우에는 팰린드롬이 아니므로 fail 체크를 하고 탐색을 종료한다.

시간복잡도는 문자열 길이 n에 대하여 n/2번 반복하므로 O(n)

개인적으로 D3문제중에서 해결하기위해 가장 많은 시도를 한 문제이다..

n,m이 10^5이기 때문에 시간초과가 발생한다. 비교 횟수를 줄여야만했다.

아래 소스로 제출했을 때, 2,338ms나 걸렸다. 그러나 다른 사람들 보면 600ms 걸린사람도 있다. 심지어 JAVA인데! 아직 공부가 한참 부족하다.

문제해결한 방법은

string으로 입력을 받아 vector에 하나씩 저장했다.

그리고 vector를 오름차순으로 정렬했다. 두 문자열을 비교하여 맞는 문자열을 찾으면, 그다음부터는 두번째 비교 대상 벡터에서는 앞에있는 문자열은 신경쓰지 않기 위해서이다.

그부분이 iterator를 이용했다. v1에서 비교하기 위한 하나의 string을 v2 가장 첫번째 부터 비교하여 같은 문자열이 있으면 해당 위치를 기록하고 다음에 비교할 때는 이전 문자열을 신경쓰지 않는다.( 5번째에서 발견되었다고 하면 그다음 비교할 때에는 6번째부터 비교하면 된다)

시간을 줄이기 위한 방법을 생각해보면 pair를 이용해서 문자열 길이와 문자열을 같이 저장한 후에, 같은 길이의 문자열에 대해서만 비교해주면 시간이 훨신 줄어들지 않을까라는 생각을 해본다. 나중에 시간나면 추가 구현해보면 좋을 것 같다.

배열에서 왼쪽2칸, 오른쪽 2칸이 비어있는지 계산한다.

0~100점을 기록할 배열을 두고, 점수가 입력될 때마다 해당 점수의 개수를 1개 증가시킨다.

모든 입력을 받은 후, 가장 많이 발생한 점수를 찾아 출력한다.

STL을 사용하면 편하게 구현할 수 있다.

string 에 문자열을 입력 받은 후, 벡터에 문자열을 저장하고, 가장 앞의 문자를 제거하고, 다시 문자열을 저장하고, 가장 앞의 문자를 제거하고.. 를 반복했다.

이러면 벡터에 가장 앞의 문자 하나씩 제거되며 들어가게 된다.

그리고 벡터를 sort해주면 알아서 문자열을 알파벳 순서로 정렬해준다. 

정렬 후 , K번째 문자열을 출력하면 결과가 나온다.

시간 제한이 2초로 넉넉하므로 모든 경우의 수를 계산하도록 했다.

3 1 2 3 1 2 의 비용이 들고 L=3일 때, 

(3 + 1 + 2) / 3

(3 + 1 + 2 + 3) / 4

(3 + 1 + 2 + 3 + 1) / 5

(3 + 1 + 2 + 3 + 1 + 2) / 6

(1 + 2 + 3) / 3

...

(3 + 1 + 2) / 3

까지 모든 경우의 수에서 평균 비용이 최소가 되는 값을 출력하도록했다.

시간복잡도는 O(n^2)