songhee

개발자가 되자!

2 분 소요

연결된 링크 자료구조를 공부하면서 푼 문제다.
사람들로 이루워진 원이라고 하길래 끝과 처음이 연결된 원형 연결 리스트를 만들어서 풀었다.
단일 연결 리스트를 구현한 것을 바탕으로 마지막 node의 다음 node값에 처음 node주소를 넣어서 이어지도록 만들었다. 문제를 푸는 용이기 때문에 완벽하게 구현을 하지 않았다.

  • 문제에서는 1이 무조건 들어가므로 처음 리스트를 생성할 때 data에 1을 넣어서 생성했다.

  • N명의 사람일 때 for문으로 데이터를 원형 연결 리스트에 데이터를 설정했다.

  • k번째일 때를 index로 하여 index에 해당하는 node의 데이터를 찾고 이를 제거하는 과정을 반복하여 node의 다음 node가 자기 자신이 나올때 while문을 빠져나와 값을 출력했다.

  • k가 1일 때는 모든 값을 1부터 차례대로 출력하면 되므로 따로 메소드를 만들어서 출력했다.

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 bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		int count = Integer.parseInt(st.nextToken());
		CircleList ci = new CircleList(1);
		for (int i=1; i<count; i++) {
			ci.insert(i+1);
		}
		int index = Integer.parseInt(st.nextToken());
		String result = "";
		if (index != 1) {
			result = ci.delete(index);
		} else {
			result = ci.print();
		}
		System.out.println(result);
	}
	
}

class Node {
	int data;
	Node next;
	
	public Node() {
		
	}
	
	public Node(int data) {
		this.data = data;
	}
	
	public void setData(int data) {
		this.data = data;
	}
	
	public int getData() {
		return data;
	}
}

class CircleList {
	Node node;
	
	public CircleList () {
		this.node = new Node();
		this.node.next = node;
	}
	public CircleList (int data) {
		this.node = new Node(data);
		this.node.next = node;
	}
	
	public void insert(int data) {
		Node end = new Node(data);
		Node n = node;
		while (n.next != node) {
			n = n.next;
		}
		n.next = end;
		n.next.next = node;
	}
	
	public String delete(int index) {
		Node n = node;
		StringBuffer sb = new StringBuffer();
		sb.append("<");
		int count = 1;

		while (isExist(n)) {
			count++;
			if (count%index == 0) {
				count++;
				sb.append(n.next.data).append(", ");
				n.next = n.next.next;
			}
			n = n.next;
		}
		sb.append(n.data).append(">");
		return sb.toString();
	}
	
	public boolean isExist(Node n) {
		if (n.next == n) {
			return false;
		}
		return true;
	}
	
	public String print() {
		StringBuffer sb = new StringBuffer();
		Node n = node;
		sb.append("<");
		while(n.next != node) {
			sb.append(n.data).append(", ");
			n = n.next;
		}
		sb.append(n.data).append(">");
		return sb.toString();
	}
}


코드의 양이 많기는 하지만 속도는 확실히 빠른 거 같다. 비슷한 다른 문제를 풀었을 때는 원래 java에 존재하는 LinkedList를 사용해서 문제를 풀었으나, 시간 초과의 벽에 넘지 못했는데 리스트를 만들어서 문제를 풀었을 때 빠르게 결과가 나왔다.
이 풀이 말고 훨씬 더 짧고 간단하게 푼 방식도 많다.
원형 연결 리스트를 처음 접해봤는데 잘 구현한건지도 모르겠다. ㅋㅋㅋ

자료구조와 알고리즘을 요즘 공부중인데 어렵고 어렵다ㅏㅏㅏㅏㅏ…

참고