[자료구조] 연결 리스트 문제 풀이 (2021.07.22 실패)

3045번: 이중 연결 리스트

 

  실패했다. 백준 알고리즘 문제 풀이를 할 때 항상 걸림돌이 되던 부분이 제한시간이어서, 시간을 최대한 단축해보고자 메모리 신경을 안 쓴 것이 이번의 걸림돌이 되었다.

 

실패한 코드

import java.util.ArrayList;
import java.util.Scanner;

class Operation {
	Operation(char ty, int t, int d){
		type = ty;
		target = t;
		dest = d;
	}
	char type;
	int target;
	int dest;
}

class Node {
	int data;
	Node prev;
	Node next;
	
	Node(int number){
		this.data = number;
	}
	
	void setNext(Node other) {
		other.prev = this;
		this.next = other;
	}
	
	void setPrev(Node other) {
		other.next = this;
		this.prev = other;
	}
	
	void moveNextTo(Node other) {
		linkNeighbor();
		
		Node otherCurrentNext = other.next;
		if(otherCurrentNext != null)
			otherCurrentNext.prev = this;

		this.next = otherCurrentNext;
		this.prev = other;
		other.next = this;
	}
	
	void movePrevTo(Node other) {
		linkNeighbor();
		
		Node otherCurrentPrev = other.prev;
		if(otherCurrentPrev != null)
			otherCurrentPrev.next = this;
		
		this.prev = otherCurrentPrev;
		this.next = other;
		other.prev = this;
	}
	
	void linkNeighbor() {
		Node currentNext = this.next;
		Node currentPrev = this.prev;
		if(currentNext != null) 
			currentNext.prev = currentPrev;
		if(currentPrev != null)
			currentPrev.next = currentNext;
	}
}


public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int listLength = scanner.nextInt();
		int numOperate = scanner.nextInt();
		Node[] nodeArray = new Node[listLength + 1];
		Operation[] operations = new Operation[numOperate];
		for(int i = 0; i < numOperate; i++) {
			char type = scanner.next().charAt(0);
			int target = scanner.nextInt();
			int dest = scanner.nextInt();
			operations[i] = new Operation(type, target, dest);
		}
		scanner.close();
		
		Node header = new Node(0);
		Node cursor = header;
		nodeArray[0] = header;
		for(int i = 1; i <= listLength; i++) {
			cursor.setNext(new Node(i));
			cursor = cursor.next;
			nodeArray[i] = cursor;
		}
		
		for(int i = 0; i < numOperate; i++) {
			Operation curOp = operations[i];
			Node target = nodeArray[curOp.target];
			Node dest = nodeArray[curOp.dest];
			if(curOp.type == 'A')
				target.movePrevTo(dest);
			else if (curOp.type == 'B') 
				target.moveNextTo(dest);
		}
		
		operations = null;
//		traversal(header);
		
		cursor = header.next;
		int lisCnt = 0;
		Node lisStart = cursor;
		Node lisEnd = cursor;
		int curCnt = 1;
		Node curStart = cursor;
		
		do {
			if(cursor.next != null && cursor.next.data > cursor.data) {
				curCnt++;
				if(curCnt > lisCnt) {
					lisStart = curStart;
					lisEnd = cursor.next;
					lisCnt = curCnt; 
				}
			}
			else {
				curStart = cursor.next;
				curCnt = 1;
			}
			cursor = cursor.next;
		} while(cursor != null);
		
		ArrayList<String> result = new ArrayList<>();
		cursor = lisStart;
		while(cursor.data != 1) {
			if(cursor.prev != null && cursor.prev.data == cursor.data -1) {
				cursor = cursor.prev;
				continue;
			}
			Node target = nodeArray[cursor.data - 1];
			target.movePrevTo(cursor);
			result.add(String.format("A %d %d", target.data, cursor.data));
			cursor = cursor.prev;
		}
		cursor = lisStart;
		while(cursor.data != listLength) {
			if(cursor.next != null && cursor.next.data == cursor.data + 1) {
				cursor = cursor.next;
				continue;
			}
			Node target = nodeArray[cursor.data + 1];
			target.moveNextTo(cursor);
			result.add(String.format("B %d %d", target.data, cursor.data));
			cursor = cursor.next;
		}
		
		System.out.println(result.size());
		for(int i = 0 ; i < result.size(); i++) {
			System.out.println(result.get(i));
		}
	}	
	
	static void traversal (Node header) {
		Node cursor = header.next;
		do {
			System.out.println(cursor.data);
			cursor = cursor.next;
		}while(cursor != null);
	}
}

 

접근 방식

1. 다중 연결 리스트 구현
2. 주어진 연산에 맞게 리스트 노드를 재배치
3. 숫자가 증가하는 리스트 중 가장 긴 것을 찾음 (ex. [ 6 1 3 5 4 2 ]의 [ 1 3 5 ] )
4. 3에서 찾은 리스트를 기준으로 리스트 바깥의 노드를 이동

 

추가

자바에서 콘솔 입력에 Scanner를 사용하면 메모리 사용이 많다고 한다.