문제에서 주어진 기준에 맞게 정렬하는 문제다. 다만 주어진 조건이 일반적인 크기비교가 아닌 다소 복잡한 조건이다. 따라서 이에 맞게 compare 함수를 정의해야 한다. 나는 map을 사용해 각 단어에 대한 횟수를 저장하고 이를 활용해 vector에 정렬하여 저장했다. 정답 코드 #include #include #include #include using namespace std; int n, m; map word; vector v; bool cmp(string a, string b){ if (a.length() == b.length() && word[a] == word[b]) { return a b.l..

O(n^2) 알고리즘은 시간초과가 발생하므로 O(nlogn) 알고리즘을 구현해야한다. 그럼 가장 먼저 생각나는 것이 이분탐색이다. 처음엔 입력들을 오름차순으로 정렬하고, 이분탐색하려고 했다. 그런데 중복되는 원소가 존재한다는 것이 까다로웠다. 어차피 작은 원소들의 개수만 알면 되므로 중복되는 원소들은 제거해도 된다. unique 함수(를 이용해서 중복되는 원소들을 제거하고, 이분탐색을 진행하면 O(nlogn)으로 정답을 구할 수 있다. (unique 함수의 반환 값은 중복없이 나열된 마지막 원소 다음의 반복자다.) 정답 #include #include #include using namespace std; int n; vector x, temp, answer; int binary_search(int num..

딱봐도 좌표를 하나씩 증가시키면서 확인하면 시간초과가 날 것 같다. 그러면 각각의 사람에 대해서 검사해야겠지? 사람을 좌표화 시켜보자. 문제에서 주어지는 h와 o의 구분은 할 필요없다. 그냥 둘 중에 더 작은 놈을 먼저 저장하는 것이 더 의미있다. 각각의 사람에 대한 정보를 입력받으면 정렬하는 것이 굉장히 중요하다. h를 기준으로 하든 o를 기준으로 하든 상관없다. 둘 중에 하나로 정해서 정렬해보도록 하자. 나는 o를 기준으로 정렬했다. o를 기준으로 정렬했으면 이제 한 사람씩 검사하는 것이다. 첫번째 사람부터 검사해보자. d를 어떻게 놓아야 하느냐. o를 기준으로 했으므로 철로의 오른쪽 끝을 첫번째 사람의 o에 맞추고, 왼쪽은 o - d를 하면 딱 길이 d의 철로가 만들어질 것이다. 그러면 h가 왼쪽인..

생각보다 쉽지 않은 문제... 처음부터 위상정렬을 떠올리긴 했으나 그냥 deque으로 구현했는데 시간초과가 나왔다. 그리고나서 삽질을 엄청하다가 결국 다른 분들의 도움을 받고야 마는데... 중요한 개념은 '나보다 앞에 설 사람이 없을 때 줄을 서는 것'!! 나는 무조건 입력이 들어오는대로 다 세우고 중간마다 위치를 바꿨는데 그냥 설 차례가 되면 서면 되는 것이었다!! 입력을 받으면서 나보다 앞에 서는 사람들의 수를 cnt 배열에 저장하고, 나보다 뒤에 서는 사람들의 목록을 v 벡터에 저장한다. 그러면 나보다 앞에 서는 사람들의 수가 0인 사람들부터 큐에 집어넣고, 한 명씩 줄 세우면서 그 사람의 v 벡터를 참조한다. 참조할 때 뒤에 서는 사람들 중 앞에 서는 사람의 수가 0인 사람을 큐에 집어넣는다. (..

map이라는 자료구조만 사용할 줄 알면 어렵지 않은 문제였다. 를 이용해 사람이름과 빈도 수를 사상시켰다. 일반적인 배열만 이용해도 풀 수 있을 것 같다. 하지만 확실히 여러가지 자료구조를 익히고, 상황에 맞게 사용할 줄 아는 것도 중요하다고 생각한다. 먼저 듣도 못한 사람의 입력을 map으로 받는다. 듣도 못한 사람의 입력을 받을 때는 중복되는 사람이 없으므로 조건없이 map에 삽입하기만 하면 된다. 그리고 보도 못한 사람의 입력을 받을 때는 중복되는 사람이 있을 수 있으므로 조건에 맞게 삽입한다. 입력을 모두 받은 후에 map에 있는 문자열 중 그 빈도가 2인 경우에만 따로 벡터에 저장한다. 이제 벡터를 정렬한 후, 벡터의 크기와 벡터의 내용을 출력하면 끝이다. #include #include #in..

구현자체는 쉬웠는데 그 구현을 생각해내기가 조금 걸렸다. 처음엔 단순히 숫자라 생각해서 long long형으로 전화번호를 입력받았는데 생각해보니 0으로 시작하는 전화번호도 있을거라 생각해서 string으로 입력받았다. (최대 10자리이기 때문에 int형보다 큰 숫자가 가능해서 처음에 long long형으로 선택했다.) 그리고 각 문자열들끼리 비교를 해야하는데 처음엔 모든 문자열끼리 비교했고, 당연히 시간초과가 나왔다. 최악의 경우 문자열을 비교하는 데에만 10,000*10,000=100,000,000번 비교해야하기 때문에 시간초과는 당연했다. 그래서 조금 고민하다가 정렬된 벡터를 출력해보면서 해결할 수 있었다. string으로 입력받으면 벡터를 정렬했을 때 숫자의 크기가 아니라 문자열의 크기순으로 정렬되..