• TOC {:toc}

이 글은 백준 온라인 저지의 1966번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.04.25 (Python)

메모리 시간 코드 길이
32676 KB 100 ms 448 B 
import sys
from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    Q = deque((p, i) for i, p in enumerate(P))
    count = 0

    while True:
        now = Q.popleft()
        if Q and now[0] < max(Q)[0]:
            Q.append(now)
        else:
            count += 1
            if now[1] == M:
                break

    print(order)

아이디어 & 풀이

[[programmers-42587]]{프로그래머스 42587번} 문제를 참고하면 된다.

2022.03.18 (JS)

메모리 시간 코드 길이
12216 KB 204 ms 1102 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 15:55:45 16:01:01
풀이 생각 16:47:05 16:51:45
코딩 1 16:56:32 17:11:31
코딩 2 17:19:35 18:17:41 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [T, ...E] = input;

function main(N, M, P) {
    let print = [...P];
    const priority = [...P].sort((a, b) => a - b);
    let max_prior = priority[priority.length - 1];
    let count = 1;

    while (priority.length) {
        const new_print = [];

        for (const [i, prior] of print.entries()) {
            if (prior === max_prior) {
                if (M === i) {
                    return count;
                } else {
                    count += 1;
                    max_prior = priority.pop();
                    max_prior = priority[priority.length - 1];
                }
            } else {
                new_print.push(prior);
                if (M === i) {
                    M = new_print.length - 1;
                }
            }
        }

        print = new_print;
    }
}

for (i = 0; i < T; i++) {
    const [N, M] = E[2 * i].split(" ").map((n) => parseInt(n));
    const P = [...E[2 * i + 1].split(" ").map((n) => parseInt(n))];
    console.log(main(N, M, P));
}

피드백

  • 어차피 priority의 원소에 따라서만 count를 계산하기 때문이 print의 원소를 굳이 pop하거나 그것 때문에 새로 new_print 배열을 만들지 않아도 된다. 출력한 문서를 남겨놓고 반복해서 순회해도 어차피 현재 prior과 같은 값만 보기 때문에 그것보다 큰 prior 값은 무시되고 넘어감.
  • 실행 속도 빠른 예제들 검토해보기

참고 답안 1

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N, M = map(int, input().split())
    Q = list(map(int, input().split()))
    count = 0

    while True:
        tmp = Q.pop(0)
        # pop을 했기 때문에 타깃 문서의 위치(인덱스)를 하나 감소시킨다.
        M -= 1
        if Q and tmp != MX = max(Q):
            Q.append(tmp)
            # pop 한 대상이 타깃 문서이면 M이 -1 된다.
            # M이 -1이면
            if M == -1:
                # Q의 마지막 인덱스로 바꿔준다.
                M = len(Q) - 1
        else:
            count += 1
            # pop 한 대상이 타깃 문서이고
            # 그게 우선순위 최댓값을 갖기 때문에
            if M == -1:
                # break 한다.
                break

    print("%d" % count)

아이디어 & 풀이

인쇄하려는 타깃 문서의 위치를 별도의 변수로 관리한다.

  • 인덱스를 받아올 필요가 없게 된다.
  • 입력받은 M 값을 그대로 이용했다.

참고 답안 2

import sys
input = sys.stdin.readline

for i in range(int(input())):
    count = 0
    N, M = map(int, input().split())
    Q = list(map(int, input().split()))
    # Q에서 타깃 문서의 위치를 관리하기 위한 리스트
    DQ = [True if i == M else False for i in range(N)]

    while True:
        # 우선순위 최댓값의 인덱스(MX)를 구한다.
        MX = Q.index(max(Q))

        # MX를 기준으로 기존 리스트를 두 부분으로 나눠서
        # 조건에 따라 최댓값이 가장 앞으로 오도록 리스트를 재구성한다.
        Q = Q[MX:] + Q[:MX]
        DQ = DQ[MX:] + DQ[:MX]

        # 최댓값과 타깃 문서 여부를 pop 한다.
        Q.pop(0)
        is_target = DQ.pop(0)

        # count를 1 증가시키고 
        count += 1

        # pop한 대상이 타깃 문서였으면 break 한다.
        if is_target:
            break
    print(count)

아이디어 & 풀이

타깃 문서의 위치는 타깃 문서의 위치만 True나 1이고 나머지는 False 나 0인 리스트(i.e., DQ)를 만들어서 관리한다.

  • 우선순위를 담는 리스트에 하는 연산을 타겟 리스트에 동일하게 해주면 된다.

최댓값보다 작은 값들을 뒤로 보낼 때 popleft() & append() 대신 slice notation을 사용한다.

  • 기존 배열을 Q 최댓값이 MX라고 하면
  • Q[MX:]: 최댓값부터 끝값까지, Q[:MX]: 처음 값부터 최댓값 직전까지이므로
  • Q = Q[MX:] + Q[:MX]로 하면 최댓값이 가장 앞에 위치하고 그보다 작은 값은 뒤로 보낸 리스트를 만들 수 있다.

참고 답안 3

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N, M = input().split()
    Q = list(input().split())
    # 우선순위 최댓값을 파악하기 위한 리스트
    # SQ[0]: 최댓값
    SQ = sorted(Q, reverse=True)
    
    count = 0
    i = 0
    while True:
        # 현재 Q의 우선순위가 최댓값일 경우
        if Q[i] == SQ[0]:
            # count를 증가시키고
            SQ.pop(0)
            count += 1
            # 현재 위치가 타깃 문서의 위치와 일치할 경우
            if i == M:
                print(count)
                break
        # 아닐 경우 다음으로 이동한다.
        i = (i + 1) % N

아이디어 & 풀이

우선순위 최댓값을 max()를 이용하지 않고 입력한 우선순위 리스트를 sorted() 해서 구한다.

  • reverse=True를 이용해 내림차순으로 정렬하거나 역으로 순회하면 된다.

참고 답안 4

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N, M = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    SQ = sorted(Q, reverse=True)

    count, c = 0, 0
    while True:
        # Q의 인덱스와 우선순위를 순회하면서
        for i , p in enumerate(Q):
            # 우선순위 최댓값 m을 구하고
            m = SQ[c]
            # 현재 우선순위 값이 최댓값과 같으면
            if p == m:
                # count를 1 증가시킨 뒤
                count += 1
                # 최댓값을 다음으로 한 칸 이동한다.
                # 다음 최댓값으로 이동하는 것으로 pop 하는 것과 같은 효과이다.
                c += 1
                # 현재 인덱스가 M과 같으면
                if i == M:
                    # break 해서 반복문을 빠져나온다.
                    break
        else:
            # for문이 break 없이 끝났을 경우 다시 for문부터 반복하고
            continue
        # 반복문을 break 해서 빠져나왔을 경우 while True도 빠져나온다.
        break

    print(count)

아이디어 & 풀이

for ... else 문을 이용해 구현할 수도 있다 (풀이 4).