[BOJ] 백준 1874번 - 스택 수열(with Java)

알고리즘

풀이 시간이 상당히 오래걸렸다. 우선 리스트를 만들어서 입력받은 스택 수열을 하나씩 집어넣는 것으로 시작하였다.

처음에는 스택에 push, pop하는 과정을 통해서 연산을 뽑아놓고, 그 연산으로 다시 스택 수열을 만들어서 입력을 받은 리스트와 비교를 했기 때문에 과정도 번거롭고 시간복잡도가 크게 나왔다.

 

어떤 부분을 생략해서 시간복잡도를 줄일 수 있을까 고민한 끝에 비교하는 방식이 문제지 않을까하는 생각을 하게 됐다.

 

따라서 비교하는 방식을 과감하게 삭제하고 1부터 N까지의 숫자에 대해서 스택에 푸시를 하는데,
스택에 쌓인 모든 숫자에 대해서 맨 위에 있는 숫자가 현재 리스트가 가리키는 숫자와 일치하는 경우에만
스택으로부터 팝을 해주었고 리스트가 가리키는 숫자를 바꿔줘서 조건을 만족할 때까지 계속 반복하도록 하였다.

위와 같은 방식으로 알고리즘을 짜면 스택 수열과 일치하는 경우 스택이 비게 되고, 그렇지 않은 경우에는 스택이 비지 않게 된다.

따라서 스택이 비지 않은 경우에는 "NO"를 출력해주고, 스택이 빈 경우에는 연산 집합을 출력해주면 된다.

연산 집합은 리스트를 만들어서 스택에 푸시할 때 '+'를 넣어주고, 팝할 때 '-'를 넣어주면 완성된다.

소스코드

문제링크

1874번: 스택 수열