쌓이는 순서 문제… 시간이 많이 걸렸어요!
그런데 Arraylist만으로 풀 수 있는 문제… Arraylist를 쓸 생각 없이 계속 Stack만으로 풀려고 하다 보니 시간이 오래 걸렸습니다.
package boj_basic.cp_1;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
public class Q1874 {
public static void main(String() args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int a = 0;
int c = 0;
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < n; i++) {
int num = Integer.parseInt(br.readLine());
if(a<num) {
for(int b=a+1 ; b <=num; b++) {
stack.push(b);
bw.write("+\n");
a=stack.peek();
}
}
else {
if(!
stack.isEmpty()) {
if(c!
=num) {
// "NO"를 출력하지 않고 바로 종료하지 않음
break;
}
else {
for(int d = c; d>=num; d--) {
stack.pop();
if(!
stack.isEmpty())
c=stack.peek();
bw.write("-\n");
}
continue;
}
}
}
if(!
stack.isEmpty()) {
stack.pop();
if(!
stack.isEmpty())
c=stack.peek();
bw.write("-\n");
}
}
// 입력이 끝나고 스택이 비어있지 않은 경우에 "NO"를 출력
if(!
stack.isEmpty()) {
bw.write("NO\n");
}
bw.flush();
bw.close();
br.close();
}
}제가 처음에 작성한 코드입니다.
예제 출력 1은 잘 되는데 순서가 안맞아서 예제 출력 2에서는 “NO”만 나와야 +나 – 출력이 나오지만 + – + – + + + – NO 출력은 그런 식이었습니다.
배열리스트 쓸 생각도 못하고 그냥 스택으로 해결하려다보니…^^
'추천 관련글,
그래서 arraylist를 사용하여 +와 -를 별도로 설정하고 마지막에 스택이 비어 있지 않은 경우에만 NO를 출력하도록 코드를 수정했습니다.
package boj_basic.cp_1;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;
public class Q1874_1 {
public static void main(String() args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int a = 0;
int c = 0;
Stack<Integer> stack = new Stack<>();
ArrayList<String> array = new ArrayList<>();
for(int i = 0; i < n; i++) {
int num = Integer.parseInt(br.readLine());
if(a<num) {
for(int b=a+1 ; b <=num; b++) {
stack.push(b); //1234 집어넣음
array.add("+\n"); //arraylist에 1234 ++++
a=stack.peek(); // a=4
}
}
else { //(a>=num) 3이 들어왔을 때 a인 4가 3보다 크니까
if(!
stack.isEmpty()) {
if(c!
=num) //만약 들어온 num값과 제일 위에 있는 값이 동일하지 않다면 수열을 만들 수가 없음.
break; // for(int i = 0; i < n; i++) 반복문 빠져나옴
else {
stack.pop();
if(!
stack.isEmpty())
c=stack.peek(); //c=2
array.add("-\n");
continue; //continue해서 밑에 if문 실행하지 않고 바로 위에 for문으로 올라가서 continue!
}
}
}
if(!
stack.isEmpty()) { //for문 한 번 돌릴때마다 마지막에 pop을 한번씩!
(사실은 위에 if문 만족할 때만 행해지는 if문임)
stack.pop();
if(!
stack.isEmpty())
c=stack.peek(); // c=3
array.add("-\n");
}
}
// 입력이 끝나고 스택이 비어있지 않은 경우에 "NO"를 출력
if(!
stack.isEmpty()) {
bw.write("NO\n");
}
else {
for(String st : array) {
bw.write(st);
}
}
bw.flush();
bw.close();
br.close();
}
}성공적인.
package boj_basic.cp_1;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;
public class Q1874_2 {
public static void main(String() args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Stack<Integer>stack = new Stack<>();
int() arr = new int(n);
ArrayList<String> array = new ArrayList<>();
int index = 0;
for(int i = 0; i<n; i++) {
int num = Integer.parseInt(br.readLine());
arr(i)=num;
}
for(int i = 1; i<=n; i++) {
stack.push(i);
array.add("+\n");
while(!
stack.isEmpty()) {
if(stack.peek()==arr(index)) {
stack.pop();
array.add("-\n");
index++;
}
else
break;
}
}
if(!
stack.isEmpty()) {
bw.write("NO");
}
else {
for(String st : array)
bw.write(st);
}
bw.flush();
bw.close();
br.close();
}
}남의 코드를 참고하면 깔끔한 코드 완성!
!
시간과 메모리가 모두 줄어드는 것을 볼 수 있습니다!