[백준 1874/자바(Java)] 스택으로 오름차순 수열 만들기

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

백준(baekjoon) 1874 스택으로 수열 만들기

스택 연산 수행 방법

1. 현재 수열 값 ≥ 자연수 현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push한다. 그리고 push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다.
2. 현재 수열 값 < 자연수 현재 수열 값보다 자연수가 크다면 pop으로 스택에 있는 값을 꺼낸다. 꺼낸 값이 현재 수열 값이거나 아닐 수 있다.
   1. 아니라면 후입선출 원리에 따라 수열 표현 불가능 → NO 출력 후 문제 종료
   2. 현재 수열 값이라면 그대로 조건문을 빠져나온다.

---

슈도코드 작성

N(수열 개수) A[](수열 배열)
수열 배열 채우기
for(N만큼 반복)
{
	if(현재 수열 값 >= 오름차순 자연수) {
		while(값이 같아질 때까지)
		{
			push()
			(+)저장
		}
		pop()
		(-)저장
	}
	else(현재 수열 값 < 오름차순 자연수) {
		pop()
		if(스택 pop 결과값 > 수열의 수) NO 출력
		else(-)저장
	}
}
if(-값을 출력한 적이 없으면) 저장한 값 출력

---

코드 작성

1. Scanner & StringBuffer

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0 ; i < N ; i++) {
            A[i] = sc.nextInt();
        }
        Stack<Integer> stack = new Stack<>();
        StringBuffer sb = new StringBuffer();
        int num = 1;    //오름차순 수
        boolean result = true;
        for (int i = 0 ; i < N ; i++) {
            int seriesNum = A[i];   //현재 수열의 수
            if (seriesNum >= num) { //현재 수열 값 >= 오름차순 자연수: 값이 같아질 때까지 push() 수행
                while (seriesNum >= num) {  //push()
                    stack.push(num++);
                    sb.append("+\\n");
                }
                stack.pop();
                sb.append("-\\n");
            } else {  //현재 수열 값 < 오름차순 자연수: pop()을 수행해 수열 원소를 꺼냄
                int n = stack.pop();
                //스택의 가장 위의 수가 만들어야 하는 수열의 수보다 크면 수열을 출력할 수 없음
                if (n > seriesNum) {
                    System.out.println("NO");
                    result = false;
                    break;
                } else {
                    sb.append("-\\n");
                }
            }
        }
        if (result) System.out.println(sb.toString());
    }
}

2. BufferedReader & StringBuilder

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int arr[] = new int[n];
        for (int i = 0 ; i < n ; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int num = 1;
        boolean result = false;

        for (int i = 0 ; i < n ; i++) {
            int seriesNum = arr[i];
            if (seriesNum >= num) {
                while (seriesNum >= num) {
                    stack.push(num++);
                    sb.append("+\\n");
                }
                stack.pop();
                sb.append("-\\n");
            } else {
                int x = stack.pop();
                if (x > seriesNum) {
                    System.out.println("NO");
                    result = false;
                    break;
                } else {
                    sb.append("-\\n");
                }
            }
        }
        if (result) {
            System.out.println(sb.toString());
        }
    }
}

 

StringBuffer vs StringBuilder

공통점:

1. 가변성(Mutability): StringBuffer와 StringBuilder 모두 문자열을 가변적으로 다룰 수 있다.
   즉, 문자열을 수정하거나 추가하는 등의 연산을 수행할 수 있다.
2. API (Application Programming Interface): 두 클래스는 거의 동일한 메서드와 기능을 제공
   → 그래서 사용법이 유사하며, 대부분의 메서드 이름과 동작이 같다.
3. 문자열 연결: 두 클래스는 문자열 연결 연산에 특히 유용하다.
   이들은 문자열을 직접 수정하면서 여러 조각을 하나의 문자열로 합치는데 최적화

차이점:

1. 스레드 안정성(Thread Safety):
   • StringBuffer: 스레드 안전성을 보장. 여러 스레드가 동시에 하나의 StringBuffer 인스턴스에 접근하더라도 안전하게 작동.
     하지만 스레드 동기화로 인해 성능이 조금 떨어질 수 있다.
   • StringBuilder: 스레드 안전성을 보장하지 않음. 따라서 단일 스레드 환경에서 사용하는 것이 좋다.
     스레드 동기화가 없기 때문에 성능이 StringBuffer보다 조금 더 우수
2. 성능:
   • StringBuffer: 스레드 동기화로 인해 약간의 성능 저하가 발생. 멀티 스레드 환경에서 안전하게 사용할 수 있도록 설계
   • StringBuilder: 스레드 동기화가 없기 때문에 성능이 StringBuffer보다 빠르다. 단일 스레드 환경에서의 사용에 적합

요약하자면 StringBuffer는 스레드 안전성을 보장하며, StringBuilder는 스레드 안전성을 보장하지 않고 성능이 더 우수
따라서 단일 스레드 환경에서는 StringBuilder를, 멀티 스레드 환경에서는 StringBuffer를 사용하는 것이 일반적인 권장사항