1874번 문제 : 스택 수열

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

1874번: 스택 수열

첫 숫자는 수열의 갯수 num

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

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

생각보다 술술 풀었따

 

java

닫기 줄바꿈

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

java

닫기 줄바꿈

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문의 조건 수정

java

닫기 줄바꿈

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이 들어가자마자 빠졌을 때 스택이 비었을 때의 조건을 추가해줘야함.

 추가 했삼

java

닫기 줄바꿈

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

 

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

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

java

닫기 줄바꿈

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 을 먼저 깔끔하게 구현하고 조건에 맞게 코드를 수정하자.

java

닫기 줄바꿈

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을 만들 수가 없을 때. (스택에 담긴 수가 다음 수열보다 클 경우)

java

닫기 줄바꿈

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로 구현

 

굿