백준 if문 좀 대신 써줘
-
[알고리즘][백준] 19637. IF문 좀 대신 써줘카테고리 없음 2024. 5. 8. 02:26
문제https://www.acmicpc.net/problem/19637 문제 아이디어이 문제에서 시간 초과가 나는 경우는 보통 아래와 같습니다. 1. 그냥 O(N) (리스트 한바퀴 쭉 탐색하기) 로 탐색할 경우10^5 * 10^5 이므로 O(N)이면 무조건 시간 초과입니다. 그런데 문제 조건을 자세히 보면, if ~ else if ~ ... 요 조건이 오름차순으로 되어 있습니다. 정렬된 배열 (리스트) & O(N) 이 시간초과 = 이분 탐색 문제입니다. (무슨 공식도 아니고..) 2. 중복값을 제거하거나 맨 앞으로 이동시키려고 while문 안에서 중복값의 맨 앞 위치를 찾는 경우그런데 문제를 보면 값이 또 같은 값이 들어가 있는 경우가 있습니다. 이 경우에 중복값이 몇개 없으면 상관 없지만, 10^5개..