본문 바로가기

정렬6

백준 3172 / C++ https://www.acmicpc.net/problem/3172 3172번: 현주와 윤주의 재미있는 단어 게임 현주와 윤주는 일요일마다 재미있는 단어 게임을 하면서 시간을 보낸다. 단어 게임을 하던 중, 두 사람은 서로 좋아하지 않는 단어가 있다는 사실을 알게 되었다. 두 단어 A와 B가 있을 때, A가 B www.acmicpc.net [ 풀이 ] 문자열을 우선 정렬해놓자. 이제 정렬후 인덱스로만 보면 처음 문자열의 사전순을 알 수 있다. 이 인덱스를 문자열과 함께 묶어서 들고다니자. 이제 정렬한 문자열을 모두 뒤집는다. 뒤집고 다시 정렬한다. 이제 순회를 시작해보자. 순회의 방향은 항상 뒤집은 문자열이 앞서는 순으로 진행된다. 그럼 좋아하지 않는 순서쌍이 되려면 다음에 보는 문자열의 인덱스가 현재보는.. 2022. 8. 4.
백준 12099 / C++ https://www.acmicpc.net/problem/12099 12099번: 점심메뉴 Q개의 줄에 줄마다 각 날의 영우와 승관이가 둘 다 좋아하는 메뉴의 수, 즉 u ≤ a ≤ v 이고, x ≤ b ≤ y 인 메뉴의 수를 출력한다 www.acmicpc.net [ 풀이 ] 매운맛, 단맛 수치가 [u,v], [x,y]에 포함되는 메뉴의 개수를 구하는 문제이다. 값이 10억이므로 빠르게 구간 인덱스 판단을 위해 이분탐색을 해야한다. 먼저 값을 매운맛 기준으로 정렬한 후, u보다 크거나 같은 최소 인덱스, v 초과 최소 인덱스를 찾는다. 그 인덱스사이를 순회하며 단맛 또는 [x,y]에 포함되는지 판단해주면 된다. [ 코드 ] #include using namespace std; int n, q, u, v,.. 2022. 7. 15.

티스토리툴바