백준 - 송이의 카드 게임

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/22951

 

[문제 설명]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        // 참여인원
        int numOfPeople = Integer.parseInt(inputs[0]);
        // 1명당 가지는 카드 개수
        int numOfCard = Integer.parseInt(inputs[1]);
        int[] cardArray = new int[numOfPeople*numOfCard];

        // 입력 받기
        int index = 0;
        for (int peopleNo = 0; peopleNo < numOfPeople; peopleNo++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int cardNo = peopleNo*numOfCard; cardNo < peopleNo*numOfCard+numOfCard; cardNo++) {
                int number = Integer.parseInt(st.nextToken());
                cardArray[index++] = number;
            }
        }

        // 1개 남기고 나머지 0으로 만들기
        index = 0;
        int sumOfCard = numOfPeople*numOfCard;
        while (sumOfCard-- > 1) {
            int interval = cardArray[index];
            cardArray[index] = 0;
            while (interval > 0) {
                if (++index > cardArray.length-1) {
                    index = 0;
                }
                if (cardArray[index] != 0) {
                    interval--;
                }
            }
        }

        // 0이 아닌 값을 찾기
        int lastCardIndex = 0;
        for (int i = 0; i < cardArray.length; i++) {
            if (cardArray[i] != 0) {
                lastCardIndex = i;
                break;
            }
        }

        int winnerNo = (lastCardIndex)/numOfCard + 1;
        int lastCardNo = cardArray[lastCardIndex];

        System.out.println(winnerNo+" "+lastCardNo);
    }
}

시간복잡도는 N-1개의 K만큼 이동하니까 O(K(N-1))

1<=N<=100 1<=K<=10이므로 최악의 경우 1000번 연산.