[백준, 1874번] 스택 수열 (스택, 수열, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 스택 수열" 문제는 스택의 특성인 LIFO(Last In First Out)를 활용하여 주어진 수들을 오름차순으로 push하고, pop했을 때 원하는 수열을 만들 수 있는지를 판단하는 문제입니다.

[자료구조 JAVA] 스택 Stack 컬렉션 알아보기 (1/2)

 

스택의 peek() 메서드를 사용하여 스택의 top 값을 확인하고, 이 값과 수열의 현재 값이 같다면 pop()을 수행하고, 다르다면 push()를 수행하는 방식으로 문제를 해결할 수 있습니다.

 

이 때 주의해야 할 점은, 현재 문제에서 수를 push할 때 오름차순을 유지해야 하기 때문에, 스택을 사용하여 수열을 만들 수 있는지 여부는 다음과 같은 조건에 따라 결정됩니다.

1. 스택의 top에 있는 값보다 현재 수열의 값이 작다면, 원하는 수열을 만들 수 없습니다.
2. 스택에서는 중간에 있는 원소를 선택적으로 꺼낼 수 없기 때문에, 스택의 순서대로만 원소를 pop할 수 있습니다.

위 조건을 그림으로 표현하면 다음과 같습니다.

 

 

위 그림과 같이 스택의 top값과 수열을 비교하여 pop과 push를 해주는데, target이 3일 때 

 

• 4가 top에 있기 때문에, 3을 꺼내려면 먼저 4를 pop해야 합니다
• 하지만 4를 pop하면, 그 4는 수열에서 지금 나와버리는 것입니다
• 문제에서 우리가 만들어야 하는 수열은 "1 2 5 3 4"인데, 4를 지금 pop하면 "1 2 5 4 ..."가 되어버립니다
• 즉, 4가 3보다 먼저 나오게 되어 우리가 원하는 수열을 만들 수 없게 됩니다.

 

 

 

전체 코드

 

문제의 핵심인 stack을 구성하는 is_sequence함수만 설명하겠습니다.

 

먼저, 스택이 비어있거나 스택에 넣을 숫자가 n보다 클 경우에는 수열을 만들 수 없습니다.

이 경우, 다음과 같은 상황이 발생할 수 있습니다.

1. 스택이 비어있는 경우
   • 스택에서 pop하려고 할 때 스택이 비어 있으면 pop할 수 없습니다.
   • 예를 들어, 1부터 5까지의 수를 순서대로 넣고 pop한다고 가정했을 때, 스택이 비어있다면 원하는 수열을 만들 수 없습니다.
2. 스택에 넣을 숫자가 n보다 큰 경우
   • 예를 들어, 1부터 5까지의 숫자만 사용할 수 있는데, 만약 6이라는 숫자를 push하려고 하면 n = 5이므로 6은 수열에 포함될 수 없습니다.
   • 따라서, 6을 넣으려 하면 수열을 만들 수 없습니다.

---

먼저 스택이 비어있는지 확인하는 것이 중요한데, 그 이유는 비어있는 스택에서 맨 위의 값을 확인(peek)하려고 하면 에러가 발생하기 때문입니다.

 

그리고, 앞서 말한대로 스택의 맨 위에 있는 값(top)이 우리가 현재 만들어야 하는 수열의 값보다 크다면, 우리가 원하는 수열을 만들 수 없게 됩니다. 왜냐하면 스택에서는 중간에 있는 값은 꺼낼 수 없고 오직 맨 위의 값만 꺼낼 수 있기 때문입니다.

---

// pop : 스택의 top과 목표 값이 같다면
            if(!stack.isEmpty() && stack.peek() == seq[idx]){
                stack.pop();
                sb.append("-").append("\n");
                idx++;
            }

 

• 우리가 만들어야 할 수열의 현재 위치(idx)는 스택에서 수를 성공적으로 꺼냈을 때(pop)만 다음으로 이동해야 합니다.
• push 작업은 단순히 스택에 수를 쌓는 것이므로, 아직 수열을 만드는 것은 아닙니다.
• pop 작업을 했다는 것은 현재 위치(idx)의 수를 성공적으로 만들었다는 의미이므로, 다음 수를 만들기 위해 idx를 증가시킵니다.