1874번 문제 : 스택 수열

1874번: 스택 수열 (acmicpc.net)

1874번: 스택 수열

첫 숫자는 수열의 갯수 num

그 아래로 num개의 중복되지 않은 숫자 1~num까지 

1~num까지의 수를 스택에 push하고 pop해서 나온 수열이 입력값을 만족시키면 됨 !

생각보다 술술 풀었따

 

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		int arr[] = new int [num];
		List <Integer>stack = new ArrayList<>();
		int j=0;
		
		for(int i=0;i<num;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		stack.add(1); System.out.println("+");
		for(int i=2;i<=num;i++) {
			while(true) {
				if(stack.get(stack.size()-1) == arr[j]) {
					System.out.println("-");
					j++;
					stack.remove(stack.size()-1);
				}
				else {
					stack.add(i);
					System.out.println("+");
				}
				if((stack.get(stack.size()-1)==i && stack.get(stack.size()-1) != num) || stack.isEmpty())
					break;
			}
		}
	}
}

근데 여기서 자바 index오류 나구 수열을 만들 수 없을 때no 값 출력되게 추가해야함. 낼 고밍 !

 

3/20

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		int arr[] = new int [num];
		List <Integer>stack = new ArrayList<>();
		int j=0;
		int count=0; //스택에서 뽑아져 나온 수들 갯수 헤아리는 변수
		int out=0;
		for(int i=0;i<num;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		stack.add(1); System.out.println("+");
		for(int i=2;i<=num;i++) {
			while(!stack.isEmpty() && count != num) {
				if(stack.get(stack.size()-1) == arr[j]) {
					System.out.println("-");
					count++;
					out = stack.get(stack.size()-1);
					stack.remove(stack.size()-1);
					j++;
				}
				else {
					stack.add(i);
					System.out.println("+");
				}
				if((stack.get(stack.size()-1)==i && stack.get(stack.size()-1) != num))
					break;
				/*else {
					System.out.println("NO");
					break;
				}*/
			}/*if(stack.isEmpty() && out == j) {
				stack.add(i);
				System.out.println("+");
			}*/
			}
	}
}

훙 예제 2 만족하게 만들다가 1도 꼬여서 다시 어제 코드에서 수정 !!

 

index오류 수정 33번째 줄이랑 while문의 조건 수정

while(!stack.isEmpty()) {
				if(stack.get(stack.size()-1) == arr[j]) {
					System.out.println("-");
					j++;
					stack.remove(stack.size()-1);
				}
				else {
					stack.add(i);
					System.out.println("+");
				}
				if(!stack.isEmpty())
					if(stack.get(stack.size()-1)==i && stack.get(stack.size()-1) != num)
						break;
			}

근데 이거는 첫 번째 입력 예제가 스택이 중간에 아예비는 경우가 없이 만들어진 거라

ex) 1이 들어가자마자 빠졌을 때 스택이 비었을 때의 조건을 추가해줘야함.

 추가 했삼

		if(stack.isEmpty() && out == j) { //스택이 비어있고 나간 수가 j번째랑 같으면
				stack.add(i);
				System.out.println("+");
			}

 

이제 수열이 성립 될 수 없을 때를 추가해줘야하는데 보니까

stack의 맨 위 요소가 현재 나와야될 수열 인덱스의 숫자보다 크면 안 되더라 

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		int arr[] = new int [num];
		List <Integer>stack = new ArrayList<>();
		int j=0;
		int out = 0;
		String str = " ";
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<num;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		stack.add(1); sb.append("+\n");
		for(int i=2;i<=num;i++) {
			while(!stack.isEmpty()) {
				if(stack.get(stack.size()-1) <= arr[j]) {
					if(stack.get(stack.size()-1) == arr[j]) {
						sb.append("-\n");
						j++;
						out = stack.get(stack.size()-1);
						stack.remove(stack.size()-1);
					}
					else {
						stack.add(i);
						sb.append("+\n");
					}
					if(!stack.isEmpty())
						if(stack.get(stack.size()-1)==i && stack.get(stack.size()-1) != num)
							break;
					//stack의 맨 위 요소가 i랑 같고 (stack에 값이 방금 들어간 수이고), 
					//stack맨 위 요소가 num이 아니라면(끝까지 안 담긴 거니까 반복을 더 해야함)
				}
				else {
					str = "NO";
					break;
				}
			} 
			if(stack.isEmpty() && out == j) { //스택이 비어있고 나간 수가 j번째랑 같으면
				stack.add(i);
				sb.append("+\n");
			}
			if(str.equals("NO")) {
				System.out.println(str);
				break;
			}
		}if(!stack.isEmpty()) //로직이 다 끝났는데 스택이 비어있지 않으면 - 추가
			sb.append("-");
			if( !str.equals("NO"))
				System.out.print(sb);
	}
}

그래서 완성한 예제 입력 다 만족하는 코드 !

그런데 3%에서 틀렸다고 나온다. 반례를 찾아보고 분석해보니까

수가 연속으로 빠져나가고 stack이 비었을 때 i값을 넣어줘야하는데 그 조건이 없어...

이렇게 경우 하나하나마다 조건을 달면 코드가 한정없이 길어질 것 같다. 간단하게 다시 구현하는 작업이 필요할 것 같다.

스택의 기본 push , pop 을 먼저 깔끔하게 구현하고 조건에 맞게 코드를 수정하자.

for(int i=1;i<=num;i++) {
		//push
			stack.add(i);
		//pop
			stack.remove(stack.remove(stack.size()-1));
		}

완전한 스택의 기초

 

--------------------------------------

기초부터 차근차근 만드니까 되었다 !ㅜㅜㅜ

케이스는 총 4개

1. push

2. pop

3. stack이 비었을 때

4. stack을 만들 수가 없을 때. (스택에 담긴 수가 다음 수열보다 클 경우)

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		int arr[] = new int [num];
		List <Integer>stack = new ArrayList<>();
		StringBuilder sb = new StringBuilder();
		int i=2;
		int j=0;
		int count =0;
		String str = " ";
		for(int k=0;k<num;k++) {
			arr[k] = Integer.parseInt(br.readLine());
		}
		stack.add(1);
		sb.append("+\n"); //일단 무조건 1은 들어가고 시작해야돼

			while(count != num) {
				//stack empty
				if(stack.isEmpty()) {//스택이 비어있다면
					stack.add(i);
					sb.append("+\n");
					i++;
				}
				//stack을 만들 수가 없을 때
				if(stack.get(stack.size()-1) >arr[j]) {
					str = "NO";
					break;
				}
				//push
				if(arr[j] != stack.get(stack.size()-1) ) {//수열과 1부터 n까지 증가하는 수가 같지않으면
					stack.add(i); //다음수를 스택에 넣음
					sb.append("+\n");
					i++; //1부터 증가하는 
				}
				//pop
				else {//스택의 맨 위에 수와 수열의 수가 같으면
					if(!stack.isEmpty()) {
						stack.remove(stack.remove(stack.size()-1)); //스택에서 pop
						sb.append("-\n");
						count++; //숫자가 몇 개나 pop돼서 나왔나(==수열과 일치하는 수를 몇 개 얻었는지)
						j++; //수열의 다음 수랑 비교해야되니까 인덱스값 1증가
					}
						
			}
		}
			if(str.equals("NO"))
				System.out.println(str);
			else
				System.out.print(sb);
	}
}

완떵 ! ㅎㅎ 뿌우듯 아무것도 참고하지 않았따

 

와 그런데 다른 코드 찾아보니까 아예 stack이라는 자료구조가 있네 !>!>!?!?!?!!!!>!!!?>!>!>!!

공부해야겠따.

 

기존 코드에서 ArrayList로 구현한 stack을

Stach <Integer> stack = new Stack<>();

으로 바꿨는데 아무런 오류도 나지 않는다. 왜냐면 stack은 vector클래스를 상속받아서 만들어지기 때문에

stack의 메소드 : push(element),pop(),empty(),size(),peek(),search(data) 가 아닌

add,remove,size,isEmpty가 다 vector 클래스 안에 있는 것들이라 고대로 사용이 가능함 ! 

이렇게 보니까 뭐 아주 조금 간단해진 거 말고는 거의 비슷한데 가장 큰 차이가 바로 ..!!!

시간 !~!!!!

 

위 : Stack으로 구현

아래 : ArrayList로 구현

 

굿