Hoguz

입국심사.

문제:

입국하는 사람수 : n

심사대 :[심사시간, 심사시간..]

으로 하여 최소 입국 심사 시간을 구하는 것이다.

예를 들어 6, [7,10] 일 경우, 6명을 2개의 심사대에서(7분, 10분 심사 걸림) 심사를 할 경우 제일 빠른 경우가 언제인지를 알아내야한다.

이진탐색 문제로 분류가 되어있는데 처음에 풀때는 이걸 그렇게 접근 못했고 결국 다른 사람들의 해설을 확인할 수 밖에 없었다.

이 문제를 처음에는 동적계획으로 풀거나 아니면 횟수 구분을 통한 변수 조절 등.. 다르게 생각해봤는데 사실상 손으로도 풀리지가 않아서...

핵심은 다음과 같다.

위 예시의 경우 최악의 시간은 60분이다.(6명이 전부 10분 걸리는 심사대로 갔을 경우를 뜻한다)

그리고 상징적인 값인 1분을 상정한 후 1분과 60분 사이의 중간값, 30분을 정한다.

이제 우리에겐 30분이란 시간이 있으니 이 30분 동안 과연 몇명을 입국심사 할 수 있는지 계산 해본다.

계산 방법은 단순하다. 30분 // 7 + 30분 // 10이면 된다. 

즉 30분 동안 7분 심사대는 4명을 심사할 수 있고 10분 심사대는 3명을 심사할 수 있으므로 총 7명을 해결 할 수 있다.

그렇다면 다시 문제로 돌아가보자. 문제에서는 6명이 대기자로 제시되어있다.

우리는 30분의 시간동안 7명을 심사 할 수 있다. 7명 > 6명, 즉 30분은 매우 충분한 시간이다.

그렇다면 우리는 30분보다 작은 값을 주고 똑같은 방법을 통해서 해당 시간이 해결할 수 있는 인원수를 구해볼 수 있다.

제일 처음에는 1, 30, 60이었으나 이제는 시간을 줄여야 하므로 1, ?, 30이 된다.

그럼 이제 중간 값은 15가 되고 15 //7 + 15// 10 은 3명이 된다.

3명은 6명에 한참 모자라므로 15분이란 시간은 매우 부족한 시간임을 알 수 있다.

이제는 15, ? , 30이 된다. 

중간값은 22가 될 것이고 22분 동안 해결할 사람 수는 22//7 + 22//10, 5명이 된다.

이 역시 매우 부족하므로 시간이 더 필요하다

이제는 22 ? 30 이 될 것이고 중간 값은 26, 26분동안 해결할 사람 수는 26 //7 + 26//10으로 5명이 된다.

아직도 부족하다

26 ? 30에서 중간 값은 28이 된다. 28//7 + 28//10 은 6명이다.

6명은 문제에서 제시한 사람수이다!! 그런데 혹시 모르니 27로도 해보자...

이런 방식으로 이 문제를 풀면 된다.

결국 최악의 시간(max_time)으로 부터 아래로 줄여가면서 해당 시간대가 소화할 수 있는 사람수를 찾는 것이고

하나씩 내리게 되면 O(N) 시간이 들지만 이진탐색을 하게되면 O(logN)이므로 훨씬 빠르게 가능하기에 이진 탐색으로 접근 하는 것이다.

def solution(n, time):
    mid = n/2 * max(time) # 최악의 시간의 경우
    Left = 1
    Right = n * max(time)
    while Left <= Right:
        tot = 0
        for i in time:
            tot += mid // i
        if tot == n:
            temp_tot = 0
            for k in time:
                temp_tot += (mid-1)//k
            if temp_tot == n:
                return mid-1
            return mid
        if tot > n:
            Right = mid - 1
        else:
            Left = mid + 1
        mid = (Right + Left) // 2
        
if __name__ == "__main__":
    print(solution(6, [7,10]))

라고 해설을 위해서 썻지만 정작 내 코드는 실패만 주르극...아무래도 종료조건에 뭔가 다른게 더 필요해 보이는데..지금 내눈엔 안보인다.

def solution(str):
	lst = [i for i in str]
	temp = 1;
	flag = 0;
	if len(lst) % 2 != 0 :
			return 0;
	while temp < len(lst):
		if lst[temp-1] == lst[temp]: 
				lst.pop(temp-1)
				lst.pop(temp-1)
				temp = temp-1 if temp >= 2 else temp;
		#		print(lst)
	#			print("temp", temp)
				flag = 1;
				continue;
		else:
				if flag == 1:
						return 0
				else:
						temp +=1;
	num = 1 if len(lst) == 0 else 0;
	return num;

위 코드는 보면 최초에는 flag 값을 안줬다.

이렇게 코드를 실행할 경우 위 알고리즘은 주어진 단어를 끝까지 다 확인을 해야한다 = 시간이 초과된다.

이 문제의 핵심은 단어를 모두 확인하는것이 아니라 오히려 안되는 경우를 얼마나 빠르게 찾아내느냐 인것 처럼 보인다.

그렇기에 내가 접근했던 방식은 한번이라도 글자가 짝지어제거됬을경우 다음에 안되는 경우가 나오면 무조건 아니다 라고 하고 싶었으나

추가적으로 뒤에 더 가서 없어지는 경우가 있을 수도 있음을 알게 되었다.

바쁘다 바빠

import math;

def solution(n, a, b):
    min_ = min(a, b);
    max_ = max(a, b);
    root_temp = n // 2;
    temp = root_temp;
    while True:
        if min_ >  temp : # 두개 모두  temp 보다 큼
            root_temp //= 2;
            temp += root_temp;
            continue;
        elif max_ < temp:
            root_temp //= 2;
            temp -= root_temp;
            continue;
        elif min_ == temp:
            print("min")
            return int(math.log(root_temp, 2)) +1
        elif max_ == temp:
            return int(math.log(root_temp, 2))
        else:
            return int(math.log(root_temp, 2)) + 1;

import math
def solution(n,a,b):
    a, b = min(a,b), max(a,b)
    for k in range(1, int(math.log2(n)+1)):
        if a%2 != 0 and a+1 == b:
            return k
        else:
            n, a, b = n/2, math.ceil(a/2), math.ceil(b/2) ###

def solution(lst):
    max_num = max(lst);
    print("max_num", max_num)
    empty_lst = [];
    for i in range(2, max_num+1):
        for j in range(len(lst)):
            if lst[j] % i == 0:
                if i not in empty_lst:
                    empty_lst.append(i)
                lst[j] = lst[j] // i;
    num = 1;
    for k in (empty_lst + lst):
        num *= k
    return num

위에 내용을 적용한 코드는 아래와 같다.

def solution(n, works):
    tot_left_time = sum(works) -n; # 총 일해야하는 시간 - 남은 시간을 뺀것, [4,3,3], 4 이면 6이 나옴
    avg_part_time = round(tot_left_time / len(works)) # 야근해야하는 시간을 종류의 갯수로 남아서 반올림함, 6 / 3 이므로 2
    # 평균값에 근접하도록 각 종류를 바꾸는게 포인트
    ans = 0;
    if tot_left_time < n: # 야근할 필요가 없으니 0
        return 0;
    elif avg_part_time == 1: # [2,1,2], 1 의 경우 1이 평균값이므로 1,1,2 이렇게 구성이 되어야함.
        ans = (len(works) - 1) + (tot_left_time- ((len(works)-1)))**2
        return ans
    elif (tot_left_time) % avg_part_time == 0: # 야근해야하는 총시간이 6시간이고 temp가 2시간이면
        return avg_part_time**2 * len(works)
    else: # 7시간 야근해야하고 종류가 4개인 경우, 2,2,2,1 이렇게 해야함
        ans = (tot_left_time - avg_part_time * (len(works)-1))**2 + avg_part_time**2 * (len(works)-1)
    return ans

위에 처럼 해서 끝이나면 정말 아름다웠을 것이다..

하지만 이러한 풀이 방법 역시 제대로 적용되지 않는다..

왜냐하면 최초의 야근 양이 평균값보다 작을경우 오히려 일을 늘리는 경우가 발생하기 때문..

(4,2,1이 주어지고 평균이 2가 나왔다고 가정하면 1이 오히려 2가 되는 기이한 상황이 발생)

그렇기에 이를 해결하기 위해선 처음부터 다시 생각해봐야한다...

def solution(str):
    lst = []
    for i in range(len(str)):
        for j in range(i+1, len(str)+1):
            ans = str[i:j];
            print(ans)
            if ans == ans[::-1]:
                    lst.append(len(ans))
    return max(lst)

def solution(s):
    return max([len(s[i:j+1]) for i in range(len(s)) for j in range(i, len(s)) if s[i:j+1]==s[i:j+1][::-1]])

위 코드와 아래코는 똑같은 내용인데 축약형에 대해 정리하려고 두개 다 넣었다.

위 코드 기준 A-B-C 순의 코드를 축약할 경우 C-B-A로 쓸줄 알았는데 동일하게  A-B-C로 사용한다.

물론 제일 아래 마지막부분은 제일 앞에 나와있다.

def solution(A, B):
    gop = 0
    result = 0
    an=[]
    for k in range(2):
        answer=[]
        for i in range(0,2):
            result = 0
            for j in range(0,2):
                gop = (A[k][j]*B[j][i])
                result = result + gop
            answer.append(result)
        an.append(answer)
    return an

# 아래는 테스트로 출력해 보기 위한 코드입니다.
a = [ [ 1, 2 ], [ 2, 3 ]];
b = [[ 3, 4], [5, 6]];
print("결과 : {}".format(productMatrix(a,b)));

# 위는 과거 내 코드이고(약 1년전) 아래는 현재 내 코드이다

def solution(lst, alst):
    ans = [[0] * len(alst[0]) for i in range(len(lst))]
    print(ans)
    for i in range(len(lst)):
            for k in range(len(lst[i])):
                print("first lst" , lst[i][k])
                for j in range(len(alst[k])):
                    ans[i][j] += lst[i][k] * alst[k][j]
    return ans

주어진 행렬을 곱해서 결과를 내는 문제이고 작년에 이미 한번 풀었던 문제이다.

새삼 다시 푸니 다른 느낌이고 무엇보다 많이 발전? 한것 같다 

저 코드를 더 쉽게 하기위해선 zip 함수를 사용하면 된다.

사실상 두번째 접근법을 제외하고 보면

결국은 피보나치이다..

두번째 접근 방법은 승선생이 알려주었다.

프로그래머스 문제를 계속 접하다 보면 결국 풀이 자체는 어렵지 않으나 

그 풀이에 접근하는 방법, 생각하는 방법, 유추하는 힘이 중요...

위 문제도 a,a,a, b,b를 나열하는 경우의 수를 구하시오와 같기에..