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

걸린 시간: 53m32s

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

문제 접근 방법

처음에는 입력된 수열만 보고 어떻게 판단할 수 있지 않을까 해서 이리저리 계산해보고 했으나 없는 것 같아서 포기

• 1부터 하나하나 스택에 집어넣는다. 이때 ans라고 선언한 문자배열에 +를 저장.
• 스택에 집어넣으면서 해당 숫자가 주어인 순열에 숫자와 일치하면 pop하고 ans 배열에 -를 저장.
• 위 과정을 반복하면서 만들어진 순열과 주어진 순열을 비교해서 같으면 연산 순서를 츨력하고 다르면 NO를 출력하면 된다.

시도 1 - 틀림

7% 정도에서 틀렸습니다가 나왔다.

1#include <bits/stdc++.h> 
2using namespace std;
3
4int given[100001];
5char ansTxt[100001];
6char ans[200001];
7
8int main() {
9  int n;
10  scanf("%d", &n);
11  for(int i=0; i<n; ++i) {
12    scanf("%d", &given[i]);
13  }
14
15  int curr = 1;
16  int ansIdx = 0;
17  int ansTxtIdx = 0;
18  int givenIdx = 0;
19
20  stack<int> stk;
21  while(curr <= n) {
22    if(!stk.empty() && stk.top() == given[givenIdx]) {
23      ansTxt[ansTxtIdx++] = stk.top();
24      stk.pop();
25      ans[ansIdx++] = '-';
26      ++givenIdx;
27      continue;
28    }
29    stk.push(curr);
30    ans[ansIdx] = '+';
31
32    ++ansIdx;
33    ++curr;
34  }
35
36  while(!stk.empty()) {
37    ans[ansIdx++] = '-';
38    ansTxt[ansTxtIdx++] = stk.top();
39    stk.pop();
40  }
41
42  for(int i=0; i<n; ++i) {
43    if(given[i] != ansTxt[i]) {
44      printf("NO\n");
45      return 0;
46    }
47  }
48
49  for(int i=0; i<ansIdx; ++i) {
50    printf("%c\n", ans[i]);
51  }
52  return 0;
53}

시도 2 - 정답

바보같이 ansTxt 배열을 정수(int)가 아닌 문자(char) 배열로 선언해서 틀린거였다.

1...
2int given[100001];
3int ansTxt[100001];
4char ans[200001]
5...

시간 복잡도

• n개의 숫자를 입력받는다 - O(N)
• while(curr <= n) - O(N)
• 스택 연산 - O(1)
• while(!stk.empty()) {...} - O(N)
• 주어진 순열과 만들어진 순열이 같은지 비교 - O(N)
• 정답 출력 - O(N)
• 최종 시간 복잡도: O(5N) => O(N)

공간 복잡도

• 주어진 순열을 담을 배열 - O(S), S = 순열 길이
• 만들어진 순열을 담을 배열 - O(S)
• push/pop 연산을 담을 배열 - O(2*S)
• 최종 공간 복잡도: O(4S) => O(S), S = 순열 길이