자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Stack,Queue_공주구하기_Queue)

 

 

6. 공주구하기

 

예시 입력 1 

8 3

예시 출력 1

7

 

 

 

 

내가 푼 풀이(Time: 165ms Memory: 27MB)

Q 원소의 사이즈가 1일때까지 반복문을 돌면서 1)cnt가 3일때 빼주고 cnt=0으로 재 세팅하고, 2)나머지는 다시 뒤로 넣습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public int solution(int n, int k) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.offer(i);
        }
        int cnt = 0;
        while (queue.size() > 1) {
            int front = queue.poll();
            cnt++;
            if (cnt == k) cnt = 0;
            else queue.offer(front);
        }
        return queue.peek();
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        System.out.println(T.solution(n, k));
    }
}

 

 

강의 풀이(Time: 163ms Memory: 27MB)

• Queue<Integer> queue = new LinkedList<>();
• q.offer(x) : 큐에 데이터 넣기
• q.poll() : 제일 앞에 있는거 꺼내기
• q.peek() : 제일 앞에 있는거 확인하기
• q.size() : 큐에 있는 원소 개수
• q.contains(x) : x가 큐에 포함되어 있는지
• q.isEmpty() : 스택과 큐같은 컬렉션 프레임워크는 주로 isEmpty()라는 메서드를 지원한다

 

먼저 n개까지 자연수를 큐에 전부 집어넣은 다음에, k-1개 만큼을 2번을 빼서 다시 집어넣어줍니다.

3번째인건 빼버리고, 다시 2개를 뒤로 넣고 3번째인건 빼는걸 Q의 원소개수가 1개가 남을때까지 반복합니다.

Q를 while문으로 순회할때 큐가 비어있으면 멈추던가 하면 됩니다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Answer {
    public int solution(int n, int k) {
        int answer = 0;
        Queue<Integer> queue = new LinkedList<>();
        // 먼저 큐에 1부터 n까지 넣어주기
        for (int i = 1; i <= n ; i++) queue.offer(i);
		// q가 비어있을때 까지 반복문 순회
        while(!queue.isEmpty()) {
        	// 꺼내기용 반복문 : 2번 돌면서 i를 집어넣는게 아니라 
            // 기존에 넣어준거 꺼내서 다시 집어넣기
            for (int i = 1; i < k; i++) queue.offer(queue.poll());
            // 3번째꺼 빼내기
            queue.poll();
            // 원소 사이즈가 1이면 마지막남은 원소 꺼내기
            if (queue.size()==1) answer = queue.poll();
        }
        return answer;
    }

    public static void main(String[] args) {
        Answer T = new Answer();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        System.out.println(T.solution(n, k));
    }
}