코딩테스트 연습 스택/큐 프로세스

https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

Solution

def solution(priorities, location):
    answer = 0
    val_pr = list(zip(list(range(len(priorities))), priorities))
    stack = []
    while True:
        _max = max([t[1] for t in val_pr])
        if _max == val_pr[0][1]:
            stack.append(val_pr.pop(0))
        else:
            val_pr.append(val_pr.pop(0))
        
        if val_pr == []:
            break
    print(stack)
    return [t[0] for t in stack].index(location)+1

주어진 실행 대기 큐에서 우선순위에 따라 프로세스를 실행하는데, 특정 프로세스가 몇 번째로 실행되는지 알아내는 문제입니다. 실행 대기 큐에는 프로세스의 중요도가 순서대로 담긴 배열과 실행하고자 하는 프로세스의 위치가 주어집니다. 이때, 해당 프로세스가 몇 번째로 실행되는지 반환하는 함수를 작성해야 합니다.

 

처음엔 queue로 안 풀고 다른 가상 리스트를 만들어서 그에 넣고 우선순위를 각각 비교하는 알고리즘으로 짰는데 엄청나게 복잡했습니다. 문제에서 주어진 "큐"라는 것에 주목했고 제대로 이해한 후에 문제를 푸니, 쉽게 술술 풀렸습니다.

 

Attempt

def solution(priorities, location):
    answer = 0
    val_pr = list(zip(list(range(len(priorities))), priorities))
    stack = []
    # print(val_pr)
    _max = max([t[1] for t in val_pr])
    # print(_2ndMax)
    
    """
    1. max값이 val_pr에 있을 때
    2. max 값이 stack에 있을 때
    3. max 값이 val_pr과 stack에 둘 다 있을 때
    """
    breaker = True
    i=0
    while breaker:
        val_pr_1e = [t[1] for t in val_pr]
        stack_1e = [t[1] for t in stack]
        _max = max(val_pr_1e + stack_1e)
        light = True
        
        try:
            if _max == val_pr_1e[-1]:
                val_pr.pop()
                print('_max = val_pr_1e[-1]')
                light= False
            elif _max == stack_1e[-1]:
                stack.pop()
                print('_max = stack_1e[-1]')
                light= False
        except:
            pass
        
        if light:
            if _max in val_pr_1e and _max in stack_1e:
                print('both')
                print('val_pr_1e_index', val_pr_1e.index(_max), 'stack_1e_index', stack_1e.index(_max))
            elif _max in val_pr_1e:
                stack.append(val_pr.pop())

                print('_max in val_pr_1e')
            elif _max in stack_1e:
                print('_max in stack_1e')

        print("stack", stack, "val_pr", val_pr)
        i+=1
        if i == 4:
            breaker = False
    
    return answer

 

다른 사람의 풀이

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

any() 함수는 주어진 반복 가능한(iterable) 객체의 요소 중에서 하나라도 참(True)인 요소가 있는지 검사하는 함수입니다. 만약 하나라도 참인 요소가 있으면 True를 반환하고, 모든 요소가 거짓(False)이면 False를 반환합니다.

any(cur[1] < q[1] for q in queue)는 queue 리스트에서 cur 요소의 우선순위(cur[1])보다 작은 우선순위를 가진 요소가 있는지 검사합니다. 즉, 현재 요소보다 더 높은 우선순위를 가진 요소가 있는지를 확인하는 것입니다. queue에서 현재 요소와 나머지 것들의 값을 비교해서 그 요소가 max 값이 아니라는 것을 바탕으로 알고리즘을 푼 솔루션입니다. any라는 함수에 대해 배우게되었네용.