백준 알고리즘 문제_1874번

이번 시간에는 1874번 문제를 풀어보겠습니다.

 

백준 알고리즘 1874번 : https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

문제 :

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

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

 

 

생각해보기 :

-. n은 input 함수사용

-. n개의 수를 리스트에 저장 → 입력 1개에 출력 1개가 아니므로

-. 첫 번째 수만큼 push를 해주어야한다 → 그 후 pop을 사용하면 첫번째 수가 수열에 쌓인다.

(ex. 4라면 ++++-를해야 4가 수열에 들어간다)

-. 다음 입력되는 수가 더 작다면? 그 차이만큼 -(pop)를 해준다

-. 다음 입력되는 수가 크다면? 그 차이만큼 +(push)를 해주는데,

이전에 입력되었던 수들보다 클경우? → 이전 입력된 것 중 최댓값과의 차이만큼 +(push)

이전에 입력되었던 수들보다 작을 경우? → ....

-. 오름차순-Max-오름차순 → NO 출력

 

<내가 짠 코드>------- 백준 런타임 에러 + 풀지 못했다... (코드 짠시간 2hr)

 

n = int(input())
stack = []
stack2 = []

#n개만큼 list에 저장시킨다
for i in range(n):
  a = int(input())
  stack.append(a)

# 중복값X므로 max는 하나다 -> 인덱스를 찾는다
max_value = max(stack)
max_index = stack.index(max_value)

after_max_index = max_index + 1

# No를 출력하는 조건먼저 적어야한다.
for j in range(1, len(stack) - max_index -1):
  if stack[max_index + j] < stack[max_index + j +1]:
    print("No")

for value in stack:
  if value > max(stack2):
    for k in range(value - max(stack2)):
      print('+')
    print('-')
    stack.remove(value)
    stack2.append(value)
  elif value < max(stack2):
    for k in range(max(stack2) - value):
      print('-')
    stack.remove(value)
    stack2.append(value)

 

NO를 출력하는 것은 구현해 보았지만(사실 100% 정답인지는 모름...) 도저히 오름차순 - Max - 내림차순에서 내림차순 구현을 못하였다... 구글링으로 문제 푸는 방식을 확인 후 내일 아침에 다시 풀어보아야겠다.. ㅠㅠ

 

구글링 결과 내 코드가 정말 안 좋은 코드라는 걸 한번더 느낄 수 있었다...

아직 공부해야 할 것이 너무 많다는 것을 다시 한 번 느낄 수 있었다.

 

개선 필요 사항 및 배운 점!

-. 문제 이해 부족 → 완벽히 이해를 못해서 푸는데 지장이 있었다.

[입력받은 것을 리스트에 넣는 게 아니라 1부터 입력받은 수까지 리스트에 넣어야 한다.]

-. 리스트에 있는 값들로만 구현 가능 → 굳이 새로운 리스트를 만들 필요 없었다.

-. NO가 나오는 조건은 따로 변수 하나를 할당해서 통제 가능하다. [리스트 인덱스 뽑는 시간낭비를 안 할 수 있었다 ㅠㅠ]

 

<내가 짠 코드 Ver2>------ 정답!

 

n = int(input())
#1부터 쭉 들어가는 스택 / count
stack = []
count = 0
#수열
row = []
#부호를 출력하기 위해 저장하는 곳
operator = []
# 수열 성립이 안되었을때 "No"를 출력하기 위해
state = "Yes"

for i in range(n):
  num = int(input())
  # count가 n까지 커지면서 stack에 쌓이고 '+'부호저장 
  # count 초기화가 안되어서 다음 수 입력시 1부터 다시 쌓이는것 방지!!
  while count < num:
    count += 1
    stack.append(count)
    operator.append('+')
    
  # stack의 마지막 요소가 num과 같다면 제거하고 '-'부호 저장
  if stack[-1] == num:
    stack.pop()
    operator.append('-')
  # stack의 마지막 값이 num이 아니면 수열 성립이 안된다  
  else:
    state = "NO"
    break

#Stste의 상황에 따라 NO를 출력할지 결정
if state == "NO":
  print("NO")
else:
  for i in range(len(operator)):
    print(operator[i])

 

※ state = "NO" 이유의 부가설명 :

n = 5, num = 1,2,5,3,4를 예로 들면 1,2,5 까지는 while 문과 if를 통해 append/pop 이 진행된다.

하지만 5가 pop이 되면 stack = [3, 4]가 되므로 3을 뽑으려면 4가 없어야 한다. → 수열 성립 X

 

n = 5, num = 1,2,5,4,3 인 경우, 1,2,5까지 동일하게 append/pop이 진행되어 stack = [3, 4] 가된다. → 수열 성립!

 

♠이 문제를 풀면서 느낀 점

-. 문제를 이해하는 것이 가장 중요하다는 것을 느꼈고, python 기초[알고리즘/자료구조]를 조금 더 공부하여야겠다.