삼성SW아카데미 문제 - 덕환이의 카드 뽑기 문제 질문입니다.

  • remocon33
    remocon33

    이곳저곳 검색해도 관련 문제가 나오지 않아 이렇게 질문드립니다.
    덕환이의 카드 뽑기

    처음 카드의 개수 N 만큼의 값들을 저장하기 위해 배열을 사용하려고 했습니다.
    예를들어 다음과 같은 배열에 저장한다고 하겠습니다.
    long long arr[N]
    그러면, K개의 카드를 아래로 넣고 가장 위에 있는 카드를 뺀다는 것은 arr[K] 를 제거한다고 볼 수 있습니다.
    그러면 K+1번째 값부터 N번째 값들을 한칸씩 앞으로 이동시켜주어야 하는 작업을 매번 해주어야 합니다.
    이는 시간초과가 될 것 같다고 생각했습니다.
    두번째 방법으로는 연결리스트를 사용하는 방법입니다.
    연결리스트 lt에 카드의 값들을 순서대로 넣은 후에 K+1번째 노드를 제거하고 그 앞뒤노드를 이어줍니다.
    그리고 K+1번째 노드부터 다시 K+1 번째 노드를 탐사하여 같은 작업을 반복합니다.
    그러나 이 방법은 매 라운드마다 한 노드씩 탐사를 해야해서 이 또한 시간초과가 발생합니다.

    입력받는 값이 적당히 크면 상관이 없을 것 같은데 N의 최대값이 천만이고 K의 최대값이 백조 단위라 계속 시간초과가 뜹니다.

    혹시 이 문제를 해결하기 위한 방법을 아시는 분이 계시나요?


    2년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.