robinjoon의 개발이야기

package test; import java.util.*; public class Main{ public static long calc(int lv,int now,long item_cost,int goal) { int costs_100[] = {41000, 81000, 121000, 161000, 201000, 241000, 281000, 321000}; int costs_110[] = {54200, 107500, 160700, 214000, 267200, 320400, 373700, 426900, 480200, 533400}; int costs_120[] = {70100, 139200, 208400, 277500, 346600, 415700, 484800, 554000, 623100, 692200, ..

그룹 단어 체커 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 31501 15969 13941 51.926% 문제 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며..

문제는 위와같다. 입력의 크기가 백만인데 시간제한이 2초다. 시간복잡도가 대충 O(n) ~ O(nlogn) 정도면 무난하게 통과할 것이라 생각하고 알고리즘을 구현해 보았다. 우선, 각 알파벳이 문장내에서 몇번 쓰였는지 횟수를 구해야 한다. 그래야 가장 많이 사용된 알파벳을 구할 수 있을테니까. 즉, 문장 하나를 문자단위로 탐색해야 하므로 O(n)의 복잡도가 걸리고, 이를 26개의 알파벳마다 모두 반복해야 한다. 입력이 낮을 때는 26이라는 상수가 의미가 있겠지만, 여기선 최대 입력이 백만이므로 의미가 없다. 각 알파벳이 문장 내에서 몇번 쓰였는지 확인 했으므로 이제 그 중에서 최댓값을 구해야 한다. 단, 이때 최댓값이 여러개 존재하는지도 확인해야 한다. 최대값이 여러개일 경우 ?를 출력하라고 적혀있기 때..