오늘의 알고리즘(4월 7일)

1. 백준, 프린터 큐, 1966번 

 

www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

---

2. 생각해보자

- 문제부터 이해 해보자. 

 

첫번째 예시

3  

1 0

5

 

• 최초의 입력은 총 테스트 케이스의 개수를 의미한다. 그러므로 3개의 테스트 케이스가 있다는 뜻이다.
• 두번째 줄의 1은 총 문서의 개수를 의미한다. 그러므로 총 1개의 문서가 있다는 뜻이다. 
• 두번째 줄의 0은 현재 찾고 있는 문서가 몇번 인덱스에 위치했는지를 의미한다. 그러므로 0번 인덱스에 있다. 
• 세번째 줄의 5는 중요도를 의미한다.
• 중요도가 5인 문서 하나밖에 없기에 정답은 1이 된다. 

 

두번째 예시

4 2 

1 2 3 4 

 

• 첫번째 줄은 총 4개의 문서가 있고 2번 인덱스에 위치한 문서( = 중요도 3)가 몇번째로 출력될지를 찾는다는 뜻이다. 
• 중요도 3짜리 문서는 중요도 4짜리 문서가 출력된 다음 두번째로 출력되기 때문에 정답은 2가 된다. 

- 문제의 이해가 잘 되었는가? 그렇다면 이제 문제에서 정보를 정리해보자. 

 

 

문제의 힌트 정리

• Queue를 사용한다.
• 찾는 문서가 몇번째 인덱스에 위치한 문서인지 찾는다.
• 중요도가 가장 큰 문서가 index 0번 자리에 올 때 프린트(= pop)를 할 수 있다.
• 현재 queue에 있는 요소와 index 자리를 묶어주고 for문을 사용하여 가장 우선순위가 큰 요소부터 프린트하여 찾는 문서가 몇번째로 print 되는지 찾으면 될 것 같다. 
• 프린트 순서를 저장하는 변수가 따로 있으면 편할 것 같다. 

 

---

3. 풀이 및 코드분석 

test_case = int(input()) # 총 몇개의 테스트가 있는지 찾아본다. 

for _ in range(test_case): # 테스트 케이스 만큼 for문을 돌린다.

    n, m = list(map(int, input().split(' '))) 
    # 총 문서 개수와 찾는 문서의 위치를 저장한다.
    
    queue = list(map(int,input().split(' '))) 
    # 문서의 나열을 queue에 저장한다. 
    
    queue = [(i, idx) for idx, i in enumerate(queue)] 
    # 순서가 변동되기 전에 각 요소와 인덱스를 묶어준다.  
    
    count = 0 
    # 프린트 순서를 체크하기 위함(= 프린트 횟수를 체크함)
    
    while True: 
    # 찾는 문서가 프린트 될 때까지 무한루프를 돌린다. 
    
        if queue[0][0] == max(queue, key = lambda x: x[0])[0]:
        # 큐의 가장 첫번째 요소가 가장 큰 우선순위를 갖고 있는지 확인한다. 
        
            count += 1
            # 만약 맞다면 프린트를 할 것이기 때문에, 프린트 횟수를 1 증가한다.
            # 0번째로 프린트 되는 것이 아니라 첫번째로 프린트 된다고 표현하기 때문이다. 
            
            if queue[0][1] == m:
            # 그리고 해당 요소가 우리가 찾고있는 위치의 문서인지 확인한다. 
            
                print(count)
                # 만약 맞다면 프린트 순서를 출력하고 
                
                break 
                # 무한루프를 탈출한다. 
                
            else:
            # 가장 큰 우선순위를 가졌지만, 우리가 찾는 요소가 아니라면 
            
                queue.pop(0)
                # 해당 요소를 뽑아낸다. 
        else:
        # 가장 큰 우선순위를 갖고 있지 않다면 
        
            queue.append(queue.pop(0))
            # 뽑아낸 요소를 다시 큐의 가장 맨 뒤에 삽입한다. 

 

---

4. 주요 함수 

 

a) queue = [(i, idx) for idx, i in enumerate(queue)] 

- 기능을 설명하기 이전에 간단한 예시를 살펴보자 

queue = [1,2,3,4]
queue = [(i, idx) for idx, i in enumerate(queue)]
print(queue)

 

- 위의 코드를 실행하면 아래와 같은 결과값을 반환한다. 

 

- 이로써, enumerate 함수는 리스트의 요소와 index 번호를 묶어주는 역할을 하는 것이다. 

- 더 자세한 설명은 아래의 사이트를 참고하자. 

 

https://wikidocs.net/16045

 

b) if queue[0][0] == max(queue, key = lambda x: x[0])[0]:

여기서 중요한 부분은 람다식이다. 우선 람다식이 무엇인지 알아보자. 

 

https://wikidocs.net/64

 

이정도의 람다개념만 알고 있어도 지금 분석하는 코드를 이해하기에는 충분하다. 

 

if queue[0][0] == max(queue, key = lambda x: x[0])[0]: 라는 이 코드가 의미하는 것은 queue[0][0]이 가장 큰 우선순위를 갖고 있는 지를 확인하는 것이다. 앞서 enurmerate를 사용했기 때문에, 큐는 (중요도, 인덱스)의 묶음으로 값을 갖고 있다. 

 

max(queue, key = lambda x: x[0])[0] 에서 의미하는 바를 하나씩 알아보자 

• key는 파이썬에서 람다식을 쓰기위한 표현이다.
• 해당 람다식에서는 queue를 인자로 사용했기 때문에 x는 queue를 의미한다. 
• 그러므로 x[0]은 queue[0]을 의미하며, queue[0]은 (중요도, 인덱스) 묶음을 의미한다. 
• max 함수를 사용하여 가장 큰 요소를 갖고 있는 묶음을 찾고 중요도만 추출한다. 

만약 위의 설명이 잘 이해되지 않는다면 아래의 첨부사진을 참고하자.