티스토리 뷰
내가 제일 약한 자료구조문제
자료구조문제는 자료구조를 응용해서 푸는 문제이긴한데, 그 동작이 영 익숙치 않다.
이번 문제는 다음과 같다. 한 개의 큐와 한 개의 스택를 이용해 하나의 배열로 정렬하여 두어야한다.
문제는 그림으로 그려보면 대충 다음과같다.
1과 2의 동작을 할 수 있는데 array에 반드시 sorting 되어야한다.
그래서 문제 이름이 stack sorting 이다. 그래서 sorting 이 될수 없으면 -1을 반환해야한다.
문제가 여기까지이면 nice이다. (그래도 까다롭고 어려울 듯)
그런데 문제는 이 요구사항에서 한 걸음 더 나가는데,
배열 size가 n이라고 할 때 단 k만 주어진다.
그래서 문제 input은 다음처럼 주어질 수 있다.
5 3 (n, k)
3 2 1
이 경우 우리는 initial을 3 2 1 4 5 , 3 2 1 5 4 로 할 수 있다.
이 상황에서 두 개 모두 sorting이 가능하다. 3 2 1 5 4 를 살펴보자.
[3 2 1 5 4] [] []
[5 4] [3 2 1] [] //3 2 1 -> queue pop
[5 4] [] [1 2 3] //1 2 3 -> stack pop
[] [5 4] [1 2 3] //5 4 -> queue pop
[] [] [1 2 3 4 5] //4 5 -> stack pop , sorting end
이 때 input 5, 3, [3 2 1] 에 대한 정답은 3 2 1 5 4 가 되어야한다.
3 2 1 4 5 도 가능하지만, 숫자가 가장 큰 정답을 출력해야한다. 따라서 스페셜 저지 문제가 아니라 항상 정답 하나가 존재한다. 3 2 1 5 4 처럼말이다.
우선 있는 그대로 잘 구현하면된다. 하지만 난 이걸 하지 못했고,,, 에디토리얼에서 정답을 구할 수 있엇다. 굉장히 간단한 구현이였던것 같지만, 동작원리가 몸에 와닿지 않고 예외처리가 조금 신경쓰인다. ..
동작은 입력하자마자 스택에 넣고, 뽑아야 할것을 cur로 마크한뒤 뽑아내면된다.
그리고 예외 처리는 약간 어려운데, 좀더 성장하면 깔끔하게 풀 수 있었음좋겠다.
소스보기
https://github.com/ingyeoking13/algorithm/blob/master/cf/datastructure/911E.cc
'알고리즘 문제 > data structure' 카테고리의 다른 글
백준 9202 Boggle, Trie with 할당, 비할당 그리고 Hashing 비교 (0) | 2019.04.16 |
---|---|
백준 6549 히스토그램에서 가장 큰 직사각형 (0) | 2019.02.16 |
백준1620 나는야 포켓몬 마스터 이다솜 (0) | 2018.11.23 |
swexpert 3135 홍준이의 사전놀이 (0) | 2018.03.10 |
- Total
- Today
- Yesterday
- arena simulation
- 조합 코딩
- Propositional and Predicate Logic
- 이산 수학
- 시뮬레이션
- 아레나
- Simulation
- 명제논리
- javascript
- Discrete Mathematics
- 데이터 중심 애플리케이션 설계
- paul wilton
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- 대규모 시스템 설계 기초
- 로젠
- grafana cloud
- 이산수학
- 자바스크립트 예제
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- Arena
- Trie
- beginning javascript
- flutter
- 아레나시뮬레이션
- 아레나 시뮬레이션
- 백준
- 자바스크립트
- 최단경로 알고리즘
- 그라파나
- rosen
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |