1406: 에디터
배열로 풀면안되는 문제다. 왜냐하면 문자열이 n개고 명령어가 m개일때 매번 대략n개정도의 이동이 m번일어난다고 가정할때 nm정도의 연산이 필요한데 그럼 1억번을 넘기기 때문이다.
배열말고 연결리스트로 구현해야할듯하다.
- 중간에 있는 요소를 삭제하는 기능
- 중간에 어떤 데이터를 삽입할줄알아야함
알게된 점
String input[] = {"A", "B"};
input[0] =="A" false
char ch[] = {'a', 'b'};
ch[0] == 'a' trueString은 wrapper class라 비교할때 주솟값을 비교, char은 기본타입이라 값자체를 비교
ArrayList vs LinkedList
ArrayList
- 배열과 비슷하여 중간에 원소를 추가하는 작업을 할때 배열에 있는 원소들을 전부복사하고 다시 만드는 작업을함 -> 비효율적
-> o(n) - 배열과 비슷하기때문에 읽기가 o(1)
LinkedList
- 중간에 원소를 추가하는 작업을 하더라도 연결리스트이기때문에 o(1)안에 할 수 있음
- 대신 읽기가 느리다
첫번째 시도
- LinkedList를 사용했는데도 느리다.
- LinkedList 를 forEach를 사용하여 출력할때 o(n)보다 크게 걸릴까봐..(접근할때오래걸린다고해서) list로 바꾸고 출력해보았지만 소용이 없었다.
- 0.3초 이내라는것은 연산이 천만 이내로 이루어져야한다는것이다. 10 000 000
- 지금이건 명령어 m(~500,000)이 있고, 이 명령어가 만약에 모두 삽입이라고치자. LinkedList가 삽입이 빠르다곤하나 삽입할때 특정위치에 삽입을 해야한다. 그러면 타고 들어가서 삽입을해야하는데 이또한 o(n)이될수밖에 없다. 그럼
n*m을하면 천만번을 넘기게 된다.
해결
- ListIterator사용
- stack사용 - 삭제, 삽입이 o(1)이기때문
ListIterator
LinkedList<Character> list = new LinkedList();
char[] ch = str.toCharArray();
//ListIterator<Character> iter = list.listIterator();여기에 두면
// ConcurrentModificationException 뜸
for(int i=0;i<ch.length;i++){
list.add(ch[i]);
}
ListIterator<Character> iter = list.listIterator();
while(iter.hasNext()){
iter.next();//ConcurrentModificationException
}list에 추가한 뒤에 선언해야
ConcurrentModificationException이 안뜬다
왜그런것일까?
- iter 선언 이후에 list에 원소를 추가하게되면
iter의 next에 값이 여전히 null이다.
그런데 this$0의 원소는 추가가되고있다
그런데 이상황에서 while(iter.hasNext())안으로 들어가게된다
next가 null인데 왜 hasNext가 true일까?
내부멤버변수cursor와 this$0의 size를 비교하는것같다
next를 할때마다 내부멤버변수 cursor가 +1 된다
그래서 next에 값을 설정해주면 뭔가가 되지않을까?
싶었는데 생각해보니 next에 뭔가 값을 할당해주는 변수는 없다.
그러니까 정리해보자면
list를 iter로 바꾸는 순간에 next는 결정이 되고
iter로 변경한 사항을 list로 반영하기 위해
list의 요소들과 iter의 요소는 동기화가 되어있다
그래서 동기화된 것과 동기화되지않은것의 불일치로 에러가 발생했던 것 같다
this$0
- 외부객체에 대한 참조
- Outer 클래스 내부의 인스턴스 변수 a는 외부 클래스를 지칭하는 this$0 에 의해(위의 코드에서는 이해하기 쉽도록 Outer로 되어 있다.) 참조가 가능함
- https://namocom.tistory.com/668
iterator
자바의 컬렉션 프레임워크에서 컬렉션에 저장되어 있는 요소들을 읽어오는 방법을 표준화한 것이다.
- 반복하는 동안 요소를 제거하는일이 가능
- 다양한 컬렉션이 있지만 이 컬렉션을 같은 방식으로 순회하는것을 가능하게 해준다
- 사용이유: collection의 종류를 모를 때 가장 안정성있게 통과할 수 있고 fail-fast속성 때문에 다음 요소를 반복하기 전에 구조 변경사항을 확인하기 때문에 안전하게 엑세스할 수 있다는 것입니다.
hasNext()
→ 다음 요소가 존재하는지 혹은 그렇지 않은지 true/false로 리턴한다. true 이면 다음 요소다 있다는 것이고, false 이면 현재 요소가 마지막이라는 뜻이다.
next()
→ 다음 요소를 가져온다.
remove()
→ next()로 호출된 요소를 제거한다.
while(itr.hasNext()){
System.out.println("itr.next()==>" + itr.next()); // 다음 요소 출력
itr.remove(); // 다음 요소 삭제
}while(itr.hasNext()){
itr.remove(); // 다음 요소 삭제
System.out.println("itr.next()==>" + itr.next()); // 다음 요소 호출(에러)
}
//IllegalStateExceptionnext로 가리키고있는것을 삭제하고 그 next를 출력했기때문.
Iterator는 hasNext, next, remove 메서드 세개밖에 없는데
ListIterator는 데이터를 추가/교체가 가능하다
stack 으로 구현
아이디어: stack 두개를 이용하여 구현 + bw사용
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//이코드에서 bw만 System.out.println을 쓰면 시간초과뜸
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine();
int n = Integer.parseInt(br.readLine());
//커서기준으로 왼쪽에있는 요소들을 담을 stack
//stack을 이용해 구현하면 삽입/삭제가 o(1)만에 일어난다.
//이 문제는 o(n)아래로 끝나야한다. 그래서 n번반복안에는 n번또 반복하는 코드가 들어가선안된다.
Stack<Character> leftStack = new Stack<>();
Stack<Character> rightStack = new Stack<>();
//string을 char로 쪼개서 stack에 넣는다
//커서는 가장끝에 위치하니 커서기준왼쪽을 의미하는 leftStack에 요소들을 모두 넣어주면된다
for(int i=0;i<str.length();i++){
leftStack.push(str.charAt(i));
}
//n번 명령어를 입력받을 것이디ㅏ
for(int i=0;i<n;i++){
//명령어는 띄어쓰기로 구분된다
String[] input = br.readLine().split(" ");
if(input[0].equals("P")) {
//input[1]을 커서 왼쪽에 추가
leftStack.push(input[1].toCharArray()[0]);
}
else if(input[0].equals("B")){
//커서왼쪽삭제, 단 만약 stack이 비어있는 경우엔 pop하면 error난다
if(!leftStack.isEmpty()) leftStack.pop();
}
else if(input[0].equals("D")){
//커서 오른쪽으로 한칸
//pop하기전에는 항상 empty를 체크해준다
if(!rightStack.isEmpty()){
//커서가 오른쪽으로 간다는것은 커서기준 오른쪽에있던 요소가 왼쪽으로 이동함을 의미한다
char c = rightStack.pop();
leftStack.push(c);
}
}
else if(input[0].equals("L")){
//커서 왼쪽으로 한칸
if(!leftStack.isEmpty()){
char c = leftStack.pop();
rightStack.push(c);
}
}
}
//leftstack에있는것을 빼서 rightstack에 넣고 rightstack에서 pop해서 출력하면
//순서대로 출력이 가능해지게 된다
while(!leftStack.isEmpty()){
char c = leftStack.pop();
rightStack.push(c);
}
while(!rightStack.isEmpty()){
bw.write(rightStack.pop());
}
bw.flush();
bw.close();
}
}17298: 오큰수
stack 이용
push할때마다 top과 비교하여 만약 내가 넣으려는수가 top보다 크다면 while문을 통해서 stack에있는 모든 수를 하나씩 꺼내고
그 수의 오큰수를 push하려는 값으로 설정해준다
(1회연산의 여러개의 오큰수를 처리)
그리고 n번의 연산끝에 남은 것들은 다 -1로 처리해주면되니 o(n)으로 끝날 수 있다
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;
public class Main{
//인덱스와 값을 저장하고, 이를 스택으로넣으려고구현함
//그냥 값만 넣어버리면 넣는순간 인덱스를 모르기때문에 아래의 class가 필요함
public static class Node{
int idx;
int value;
public Node(int idx, int val){
this.idx = idx;
this.value = val;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
String input[] = br.readLine().split(" ");
Stack<Node> stack = new Stack<>();
//i번째수에 i번째수의 값을 저장
//i번째 수에 i번째수의 오큰수를 저장
int o[] = new int[n+1];
for(int i=1;i<=n;i++){
//입력으로 들어오는 값
int val = Integer.parseInt(input[i-1]);
//stack이 비어있지 않아야함. 비어있으면 peek참조가 불가능하기때문
//peek의 value가 새로들어온 입력값보다 작은 경우에만 반복문을 돌린다
//stack에 쌓여잇는 값을 하나씩 빼서
//stack에서뺀값의 오큰수는 새로들어오는 큰수 가 되는것이다
while(!stack.isEmpty()&&stack.peek().value<val){
Node node = stack.pop();
o[node.idx] = val;
}
//stack에 들어있따는것은 아직오큰수를 찾지 못했다는 의미이다.
//새로운 값은 이전값들보다 크긴했지만 이 크수보다 더 큰 오큰수는 찾지 못했으므로 일단 stack에 추가한다
stack.push(new Node(i, val));
}
//stack에 들어있는 값들은 모두 오큰수가 없는 값들이므로 -1으로 초기화해준다
while(!stack.isEmpty()){
o[stack.pop().idx] = -1;
}
//배열에 있는값을 그대로 출력하면 맨처음에 입력받은 순서대로 오큰수를 출력할수있게된다
for(int i=1;i<=n;i++){
bw.write(o[i] + " ");
}
bw.flush();
bw.close();
}
}출처
https://thefif19wlsvy.tistory.com/41
https://tragramming.tistory.com/100
안녕하세요!