시작하는 중

입력에 대해 목표값까지 더하거나 나누는 문제 이런 문제는 당장 생각나는 큐를 사용하는 완탐 기반 방법이 두개가 있다. 1. 입력을 목표에 맞춰서 더하거나 곱하는 방법 2. 목표를 입력에 맞춰서 빼거나 나누는 방법 이런 문제는 2번이 적합하다. 1을 +1, *2, *3만을 사용하여 10에 하려면 최단 방법은 여러가지가 있겠지만 우선 *3 *3 +1이 생각난다. 1번으로 접근하면 1에 대해서 3번 연산, 2에 대해서 3번연산, 3에 대해서 3번연산, ... 이렇게 가지만 2번으로 접근하면 10에 대해서 2번 연산(-1, /2), 9에 대해서 2번 연산(-1,/3), 5에 대해서 1번 연산, 8에 대해서 2번 연산, 3에 대해서 2번 연산, 이렇게 진행된다. 즉 연산 횟수 자체가 많이 줄어든다. from co..

배열을 순회하면서 해당 배열의 요소를 기준으로 뒤의 요소들 중 나보다 큰 수를 먼저 만났을 때의 값을 출력하는 문제 조건을 보면 배열의 길이는 10^6이다. 단순하게 for문을 돌리고 해당 인덱스부터 다시 for문으로 검사하는 과정을 하면 시간복잡도는 O(N^2) 논리대로라면 1000000!를 계산해야해서 최악의 조건에서는 시간초과가 날 것이다. 정답을 도출해 내는 과정을 살펴보면 1. 나를 기준으로 뒤의 인덱스에서 나보다 큰 수 중 가장 가까운 수를 찾아내고 2. 있다면 해당 수가 정답이되고 없다면 -1이 된다. 가장 가까운 수를 찾는 것에서 stack을 쓰면 쉽게 할 수 있다는 것을 생각할 수 있다. 1. 스택을 마지막 수를 넣으며 선언하고 순회를 거꾸로 시작 -> 이유는 마지막 수의 정답은 항상 -..

완호의 인센티브를 받는 유무와 완호는 몇등일까를 생각하는 문제 이런 문제는 조건을 잘 읽어야 해요. 1. scores의 길이는 최대 10^5, 점수도 최대 10^5 2. 완호가 인센을 못 받으면 -1을 return 3. 회사원 중 한명이라도 나보다 두 점수가 높은 사람이 있다면 인센에서 제외 4. 공동 1등이 2명이면 2등이 없고 3등부터 존재 일반 글씨는 처음에 접근한 방법이고 + 이후는 추후에 정답을 위해 생각한 거에요 1. 완호를 제외한 나머지를 scores로 재 정의하고 2. scores를 sort하여 정렬하고 3. scores를 순회하면서 3-1. 완호(me)가 인센을 못받는 조건인지 검사하고 3-2. 이중 반복문을 통해 해당 score index의 +1부터 조건을 통과하나 검사하고 3-3. 통..

호텔의 예약 정보가 들어오고 정보를 바탕으로 대실이 몇개 필요할지 계산하는 문제 어떻게 풀어야할까? 처음에는 어렵게 생각해서 리스트 만들고 계속 검사하면서 기존 방들의 시간이 겹치면 리스트에 해당 예약 시작, 끝 정보를 담는 리스트를 추가하여 결국 2차원 리스트로 하려고 했는데 하다보니깐?? 그냥 구간합으로 풀면 되는 문제였다. 1. 길이가 60*24인 number 리스트를 만들고 2. 예약 정보에 대한 순회를 돌고 3. string 형태의 시간과 분을 파싱하고 4. 구간합을 하기 위해 시작과 끝 지점을 각각 1, -1로 마킹하고 5. 예약 정보 순회가 끝난 후 number_list를 돌면서 구간합을 하면 된다. 밑에는 코드에요. def solution(book_time_list): answer = 0 ..