Cat on The Keyboard Cat on The Keyboard

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

문제https://www.acmicpc.net/problem/20310  문제 아이디어1. 사전 순으로 빠른 것2. 0과 1을 절반을 제거할 것 사전 순으로 빠르게 한다면 최대한 앞의 1은 다 제거해주어야 하니까 1은 앞에서부터 절반을 제거해 줍니다.사전 순으로 빨라야 하니까 0은 뒤에서부터 절반을 제거해 줍니다.일단 1을 앞에서부터 제거해주고, 뒤집어서 0을 앞에서부터 제거해준 다음에 다시 뒤집어서 출력해줍니다. s = list(input())zeroCount = s.count('0')oneCount = s.count('1')currZeroCount = zeroCount / 2currOneCount = oneCount / 2while currOneCount != 0: s.remove('1') ..

문제https://www.acmicpc.net/problem/13305  문제 아이디어맨 앞에서부터 탐색하면서 이전보다 더 적은 가격으로 주유를 넣을 수 있다면 해당 가격으로 주유를 넣으면 되는데, 그래도 최소한의 기름이 있긴 해야하니까 최소한의 기름만 넣으면서 이동하다가 더 싼 가격을 만나면 해당 가격으로 최대한 많이 넣고 이동하면 됩니다. (생각하기 편하게 거리는 일단 전부 2로 했습니다.) 아래와 같은 케이스가 있다고 생각합시다. 1번 도시2번 도시3번 도시4번 도시 5번 도시6번 도시7번 도시8번 도시9번 도시가격523182741거리222222222 1. 일단 처음에는 기름이 아예 없으니까 5원으로 2리터를 넣어줍니다.2. 2번 도시를 보니까 가격이 2원이네요? 이 때는 1번 도시에서 추가로 넣는..

배경기존에 Broadcast Receiver와 Foreground Service를 사용하는 앱이라면 신경 써주어야 하는 정책적인 변경점이 하나 생겼는데요. 최근에 Android 14가 나오고 SDK가 34 이상으로 올라감에 따라 해당 버전 값으로 올리게 되면 정책이 변경됨에 따라 처리해주어야 할 것이 많아졌습니다. 기존에는 권한 정도만 하나 올려주고, 버전 별로 사용에 다른 분기 처리 정도만 해주면 되었지만, 이게 뭔가 좀 더 바뀌었습니다. 만약 아래와 같이 추가 선언을 하지 않는다? Broadcast Receiver의 경우 이제 아래와 같은 Exception이 발생하면서 앱이 죽어버리고 Foreground Service의 경우 그냥 서비스가 실행이 되지 않습니다...java.lang.SecurityEx..

문제https://www.acmicpc.net/problem/3758 문제 아이디어문제가 어려운 건 아닌데 잘못 읽어서 시간이 많이 걸렸습니다. 단순히 각 팀 당 각 문제 번호의 최고 점수를 합산한 것을 저장하고, 합산 점수, 제출 횟수와 시간을 기준으로 정렬하면 됩니다. T = int(input())for t in range(T): test = list(map(int, input().split(' '))) n = test[0] # 팀 개수 k = test[1] # 문제 개수 t = test[2] # 우리팀의 id m = test[3] # 문제 수 # id, 문제 번호, 점수 # 1 1 30 # 2 3 30 # 1 2 40 # 1 2 20 # 3..

문제https://www.acmicpc.net/problem/15486 문제 아이디어12345673511242102010201540200 차근차근 생각해봅시다.1일차: 상담을 하면 3일차에 끝나게 됩니다. 그러면 4일차부터는 10의 비용이 더해지게 됩니다.2일차: 상담을 하면 7일차에 끝나게 되고, 7일차에 20의 비용을 더해줍니다.3일차: 상담을 하면 3일차에 끝나고, 3일차에 10의 비용을 더합니다. 4일차: 상담을 하면 4일차에 끝나고, 4일차에 20의 비용을 더하는데, 여기서 1일차에 끝난 비용을 더해준다면 총 30의 비용입니다. (혹은 3일차에 끝난 비용을 더해도 됩니다.)* 즉 이전 날짜까지 총 상담 기록을 봤을 때를 더해주는 느낌입니다.5일차: 상담은 7일차에 끝나고, 4일차까지의 기록을 보..

문제https://www.acmicpc.net/problem/11659 문제 아이디어숫자가 100000개, 케이스가 100000개 이므로 한 케이스 당 한 사이클의 개수를 더하면 시간 초과가 날 것입니다. 따라서 말 그대로 구간 합을 구해나가면 됩니다. 5 4 3 2 1 이 있다고 한다면, 아래와 같이 구할 수 있습니다.1번째까지의 합: 5 = 52번째까지의 합: 5 + 4 = 93번째까지의 합: 5 + 4 + 3 = 124번째까지의 합: 5 + 4 + 3 + 2 = 145번째가지의 합: 5 + 4 + 3+ 2 + 1 = 15 그렇다면 이제 아래와 같이 생각할 수 있습니다.2번째부터 4번째까지의 합: 4번째까지의 합 - 1번째까지의 합 (2번, 3번, 4번의 수를 더하는 것이므로 4번까지 다 더한 다음에..

문제https://www.acmicpc.net/problem/2607 문제 아이디어사실 단어 개수는 100개, 길이는 10개라 완전 탐색이면 충분합니다.리스트 하나를 돌면서 같은 단어가 있으면 하나씩 빼주고, 남는 것끼리만 비교해주면 됩니다.예를 들어,GOOOODF / GOCOOOAOOEOD GOOOODF를 기준으로 탐색해줍니다.0번째: G를 각각 빼줍니다 -> OOOODF / OOOOOOOD1번째: O를 각각 빼줍니다. -> OOODF / COOOAOOEOD... 각각 O, O, O, D가 있으므로 양쪽에서 빼줍니다. -> F / CAOOEO 이러면 각각 F와 CAOOEO가 있는데, F -> C 로 치환한다고 해도, 아직 AOOEO를 추가해야 같은 문자가 됩니다.결국 CAOOEO와 F 중에서 더 긴 문..