[백준] 1966번 프린터큐 - 파이썬 python

 

백준 1966 번 프린터큐 

 

항해 99 심화반은 파이썬으로 알고리즘을 풀어야 한다. 

Javascript도 아직 신생아라고 생각하는데 갑자기 python으로 leekcode medium 급 문제를 풀게 되었다. 

물론 나는 접근도 하지 못했고, 며칠을 풀이만 보고 하루에 한 문제만 완벽히 이해하도록 노력했다. 

 

항해 99측에서는 파이썬이 알고리즘에 최적화된 언어라서 공통적으로 푼다고 하는데

' 이정도의 난이도를 제로베이스 상태에서 푸는게 맞는건가?' 라는 생각이 들었다. 

 

결국 난 자바스크립트 위주로 알고리즘을 풀며 문법 공부를 추가로 하기로 결정했고, 하루 한 문제 정도는 자바스크립트, 파이썬으로 풀면서 코딩테스트에 왜 파이썬이 좋은지 스스로 깨닫는 과정을 밟고있다. 

 

사고력을 특히 요하는 것 같은 이 문제를 풀지는 못했지만, 구글링을 통해 가장 좋은 풀이법을 가져오고 내 것으로 만들기 위해 노력했다. 

 

 

---

 

---

문제의 길이는 길어 문제 자체를 이해하는데 시간이 걸렸다. 

 

우리가 인쇄를 할 때 프린터에 우선순위를 정해두는 경우가 있다. 그럼 프린터기는 그 우선순위를 먼저 출력하게 된다. 

그렇게 우선순위를 출력한 결과에서 이전에 testcases에서 case별로 정해진 문서(M)가 몇 번째로 인쇄되는지 출력하면 되는 문제였다. 

 

 

 

 

 

문제 이해를 돕기 위해 표를 그려봤다. 

 

 

 

 

 

case x 로 예를 들어보자.  궁금한 문서의 순서(index)가 4 이므로, 문서4가 인쇄가 몇 번째로 되는지 보면된다. 

6개의 문서중 5개가 중요도가 1로 같지만, 인쇄순서(order)는 첫번째 값보다 중요도가 큰 값이 뒤에 하나라도 있으면 첫 번째 값을 queue의 맨뒤로 하나씩 넘기는 방식으로 진행된다는 점을 유의하자.

 

 

 

 

 

그럼 이제 문제를 풀려면 input값에서 각각 값을 변수로 지정해줘야한다.

나는 이 문제를 풀지 못했기에 이 부분부터는 좋은 개발자분의 풀이를 찾아서 그 순서대로 진행하였다.  

 

 

 

 

# 1. testcases 로 입력을 받고, for 문을 돌려 n, m 과 문서의 중요도 queue 를 받는다.
for _ in range(testcases):
    n, m = list(map(int, input().split()))     
    queue = deque(map(int, input().split()))   
    idx = deque(range(0, n))           

    # order 초기화
    order = 0

    while True:
        # 1. 첫번째 if: queue 첫번째 값 = queue lists 최댓값?
        if queue[0] == max(queue):
            order += 1

            # 두번째 if: idx의 첫 번째 값 = "target"?
            if idx[0] == 'target':
                print('order: ', order)
                break
            else:
                queue.popleft()
                idx.popleft()
  
        # 2. idx의 첫번째 값이 target이 될 때까지 반복된다.
        else:
            queue.append(queue.popleft())
            idx.append(idx.popleft())

 

 

---

같은 문제를 두 언어로 풀어보고 느끼는 건데

파이썬의 pop()과 append()는 정말 강력한 것 같다. 

자바스크립트에서 pop(0)과 비슷한 기능을 하는 것이 shift()인데, shift()라는 메소드는 배열 자체를 움직이기 때문에 시간복잡도면에서 좋지 않다. 

오늘도 알고리즘은 파이썬이 더 낫다는 것은 인정하게 되는 날이지만, 그래도 프론트엔드로서 자바스크립트로 알고리즘을 푸는 것은 멈추지 않을 것이다.

 

++ 추가로 CS study 팀원분 중 한분이 list가 아닌 deque로 두는게 시간복잡도 면에서 더 나을 거라는 말씀을 해주셨다. 

오늘 강의에 나왔을텐데 오늘 강의 듣고 큐 구현해보라고해서 자바스크립트랑 파이썬 큐, 스택 다 구현해보다가 시간이 다 가서 강의 후반부는 모르는 상태였다. 

어쨌든 말씀해 주신 부분이여서 deque의 역할을 찾아봤는데 진짜 좋은거네..

말해주신 팀원분께 감사하다하고싶은데 성함이 기억안난다.  코드는 수정완료!

 

 

 

같은 문제를 자바스크립트로 풀어보기!

[프로그래머스-스택/큐] 프린터 -자바스크립트(JavaScript)

 

 

 

 

 

 

Reference :  https://assaeunji.github.io/python/2020-05-04-bj1966/