백준 1158 문제 풀이

문제링크: https://www.acmicpc.net/problem/1158

사용한 자료구조 : Linked List

같은 작업을 링크드리스트가 빌때까지 반복해야 한다. 따라서 원형 링크드리스트를 구현하기 위해 링크드 리스트를 사용하였다.

---

찾아낸 규칙

숫자들을 거쳐가며 얼마나 거쳐갔는지를 세는 cnt변수를 만든다. 그리고 숫자들을 거쳐갈때마다 하나씩 증가해준다. 만약에 cnt가 k로 나눠떨어지면 k번째 수가 되므로 결과 배열에 저장해준다!!!

cnt를 계속 증가해 나가며 특정 숫자로 나눠떨어지면 특정 숫자번째가 되는것이다!

반복적으로 k번째로 오는 수를 찾아 줄때는 %연산을 사용하자!

지나온 숫자들을 계속해서 순회해야 하므로 지나온 숫자를 빼서 다시 뒤에 넣어준다 => 원형으로 돌아가도록 한다.

원형이라면 앞의 수를 다시 뒤로 넣어주는 것은 그 전과 같은 모양이다!!!

---

코드 설명

일단 1~n까지 링크드 리스트에 차례대로 넣어준다.
맨앞 데이터를 뽑아 data변수에 저장하고 링크드리스트에서 지워준다. 뽑은 횟수인 cnt변수를 1씩 증가해준다.
만약 cnt변수가 k로 나눠떨어지면 k번째 숫자이므로 결과 배열에 data를 넣는다.
만약 나눠떨어지지 않으면 데이터 순회를 계속하기위해 뽑았던 data를 링크드리스트안에 넣는다. (원형링크드리스트 형식이므로 앞의 데이터를 뒤에 넣는것은 같은 모양이 된다.)
이를 링크드 리스트가 빌때까지 반복한다.

package linkedListPractice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Yosepus {
    public static void solution(int n, int k){
        LinkedList<Integer> list = new LinkedList<>();
        IntStream.range(1, n+1).forEach(x-> list.add(x));

        ArrayList<Integer> result = new ArrayList<>();
        int cnt = 0;
        while(!list.isEmpty()){
            int data = list.pollFirst();
            cnt+=1;
            if(cnt % k == 0){
                result.add(data);
            } else{
                list.add(data);
            }
        }
        paintResult(result);
    }

    public static void paintResult(ArrayList<Integer> result){
        System.out.print("<");
        for(int i = 0; i<result.size(); i++){
            if(i == result.size()-1){
                System.out.print(result.get(i));
            } else{
                System.out.print(result.get(i)+", ");
            }
        }
        System.out.println(">");
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        solution(n,k);
    }
}

시행착오 및 교훈

이 문제는 원형 큐를 사용해서 풀어주면 되는 문제이다. 오늘의 주제는 링크드리스트를 사용하여 문제를 풀어야 했다. 하지만 큐는 인터페이스라 실제로 사용할땐 LinkedList로 만들어서 사용하는걸!!! 다형성덕분에 Queue자료형을 가진 링크드리스트를 선언할 수 있으니까.. 그래서 그런지 링크드리스트에도 queue와 비슷한 메소드들이 많더라. 예를 들어 큐에서의 poll()은 링크드리스트에서 pollFirst()를 사용하면 된다.

그래서 링크드리스트로 원형 링크드리스트를 구현하는 방식을 사용해서 문제를 풀었다.

반복적으로 같은 데이터를 순회하며 연산하는 문제가 있다면 원형링크드리스트를 떠올리는게 잘 안된다..!! 앞으로 비슷한 문제를 많이 풀다보면 이건 원형자료구조로 풀어야한다는 감이 오길 기대한다.

지나온 숫자들을 계속해서 순회해야 하므로 지나온 숫자를 빼서 다시 뒤에 넣어준다 => 원형으로 돌아가도록 한다.
원형이라면 앞의 수를 다시 뒤로 넣어주는 것은 그 전과 같은 모양이다!!!

또 한 변수를 숫자세기 용으로 선언하고 그 숫자를 나머지 연산하여 특정 순서를 확인해보는 스킬도 꼭 체화해서 문제를 빨리 풀어내야지!

반복적으로 k번째로 오는 수를 찾아 줄때는 %연산을 사용하자!