문제
https://www.acmicpc.net/step/2164
풀이(첫번째 시간초과)
let input = require('fs').readFileSync('/dev/stdin')
let arr = Array.from({length:input},(v,i)=>i+1)
while(arr.length != 1){
arr.shift()
arr.push(arr.shift())
}
console.log(arr)queue를 이용하면 굉장히 쉬운 문제인데 바로 시간초과가 나버렸다
다른 방법을 생각하다가 도저히 떠오르지가 않아서 풀이를 찾아보니LinkedList라는것으로 직접 클래스를 구현해서 문제를 푸는 방식이였다.
Linked List
queue에서shift의 시간복잡도는O(n)으로 주어진 N의 범위에 벗어날 수 있다.
그래서 배열의 탐색을 많이할때는LinkedList를 이용하면 시간복잡도가 O(1)으로 낮아진다.
위 그림은 단방향 탐색을 하는
LinkedList로 처음을 가르키는HEAD와 끝인TAIL이 있다.
next는 다음 노드를 가르키는 포인터가 된다. 이를 이용해서 해당 문제를 구현 해 보았다.
다른 풀이
let input = require('fs').readFileSync('/dev/stdin').toString();
let N = Number(input)
class Node{ // 1
constructor(val){
this.val = val;
this.next = null;
}
}
class LinkedList{ // 2
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
push(val){ // 3
let newNode = new Node(val);
if(!this.head){
this.head = newNode
}else{
this.tail.next = newNode
}
this.tail = newNode;
this.length++;
return newNode;
}
getHead(){ // 4
return this.head.val;
}
removeHead(){ // 5
this.head = this.head.next;
this.length--;
}
getLength(){ // 6
return this.length;
}
}
const cards = new LinkedList(); // 7
for(let i = 1; i<=N; i++){ // 8
cards.push(i)
}
while(cards.getLength() != 1){ // 9
cards.removeHead()
cards.push(cards.getHead())
cards.removeHead()
}
console.log(cards.getHead()) // 10⭐️ (잘 알아두기)
1. 먼저 노드를 생성해준다. 노드는 위의 사진과 같이 자기가 가지는 숫자val과 다음 노드를 가리키는next가 필요하다. 처음 생성해줄때val에는 파라미터로 들어온val숫자가 들어가고next에는 초기값으로null이 들어간다.
- 만든 노드들을 연결 시켜주는
LinkedList만든다. 초기값은head,tail,length에 각각null,null,0이 들어가고head는 노드의 제일 첫번째val를 가리키게 된다.사진에서 들어있는LinkedListhead는 현재4가 되는것이고tail은2이고length는 4이다.
LinkedList에 값을 넣는 함수로 먼저val에 받은 숫자로new Node(val)에 수를 넣어서 노드를 하나 만들어준다. 만약에 첫번째로 생성되는 노드라면 ->즉head값이 없으면 이 노드의val값을head값으로 지정한다. 첫번째가 아니라면 마지막으로 생성된 노드 일것이기때문에 이 노드의tail의 다음값을 가리키는tail.next의 값은null이 되는것이다. 사진상으로4와2가 들어와 있는 상태라고 생각을 하면 될것이다. 그리고 length를 하나 늘려준다.(length를 구하는 방법이 따로 없기때문에 하나가 추가될때마다 length의 갯수를 따로 구해줘야한다)
- 맨 앞에 있는
head의val값을 구하는 함수로 노드안에 있는val값을 리턴한다
- 맨 앞에 있는
head를 다음head로 넘기는 함수이며this.head에서this.head.next로 뒤의 값으로head를 변경한다. 사진상에서 이 함수를 쓰게되면head가4에서6으로 넘어가게 되며LinkedList의 전체 길이도 줄어든다.
LinkedList전체 길이를 리턴하는 함수
후기
사람들이 이 문제를 풀면서 LinkedList를 사용할때 단방향 탐색인데 양방향 탐색처럼 next와 prev를 둘 다 사용하던데 다른 사람의 풀이를 보고 분석하면서 필요가 없는 부분은 제외하고 받아들이는것도 중요하다고 생각했다..! 💡
hunny