[백준 알고리즘] 23253번 : 자료구조는 정말 최고야, c++

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

23253번: 자료구조는 정말 최고야

c++로 백준 23253번 문제를 풀어보겠다.

 

 

 

 

 

문제

찬우는 스택을 배운 뒤 자료구조 과목과 사랑에 빠지고 말았다.

자료구조 과목만을 바라보기로 다짐한 찬우는 나머지 과목의 교과서 N$N$권을 방 구석에 M$M$개의 더미로 아무렇게나 쌓아 두었다. 하지만 중간고사가 다가오자 더 이상 자료구조만 공부할 수는 없었고, 결국 찬우는 팽개쳤던 나머지 과목의 교과서를 정리하고 번호순으로 나열하려 한다.

 N$N$권의 교과서는 각각 1$1$부터 N$N$까지의 번호가 매겨져 있다. 찬우는 각 더미의 맨 위에 있는 교과서만 꺼낼 수 있으며, 반드시 교과서를 꺼낸 순서대로 나열해야 하기 때문에 번호순으로 나열하기 위해서는 1$1$번, 2$2$번, … N−1$N - 1$번, N$N$번 교과서 순으로 꺼내야 한다. 교과서를 올바르게 나열할 수 없다면 중간고사 공부를 때려치겠다는 찬우를 위해 번호순으로 나열할 수 있는지 여부를 알려주는 프로그램을 작성해 주자.

입력

첫째 줄에 교과서의 수 N$N$, 교과서 더미의 수 M$M$이 주어진다.

둘째 줄부터 2×M$2\times M$줄에 걸쳐 각 더미의 정보가 주어진다.

 i$i$번째 더미를 나타내는 첫 번째 줄에는 더미에 쌓인 교과서의 수 ki$k_{i}$ 가 주어지며, 두 번째 줄에는 ki$k_{i}$ 개의 정수가 공백으로 구분되어 주어진다.

각 정수는 교과서의 번호를 나타내며, 아래에 있는 교과서의 번호부터 주어진다.

교과서의 번호는 1$1$부터 N$N$까지의 정수가 한 번씩만 등장한다.

출력

올바른 순서대로 교과서를 꺼낼 수 있다면 Yes를, 불가능하다면 No를 출력한다.

예제 입력 1 복사

4 2
2
3 1
2
4 2

예제 출력 1 복사

Yes

 

 

 

 

 

<문제 풀이>

 

처음에 작성한 코드는 다음과 같다.

 

 

잘 돌아갈 거라 생각했지만 런타임 에러가 떴다.

segfault 오류라 내가 접근할 수 없는 곳에 접근하도록 했는지 확인해야했다.

이 문제는 s.empty()를 사용해 스택이 비었으면 그냥 지나가록 설계해주어 해결했다.

두번째로 작성한 코드는 다음과 같다.

 

 

online c++ compiler에서 간단한 숫자들로 실행시켜봤을 때는 잘 출력됐지만

백준 사이트에서는 '시간 초과' 가 발생했다. 

중첩 for문이 있어 시간복잡도가 늘어난 것 같다.

시간복잡도를 해결하는 것은 나중에 알고리즘을 배우면 시도해봐야겠다.

일단 간단한 숫자들로는 잘 돌아가는 것을 확인했다.

 

 

이 문제에서 중요한 점 : 

스택을 배열로 선언해 스택안에 스택이 들어가게 한다.!  =>  " stack<int> s[M]; "