μ€ν μμ΄
π λ¬Έμ
λ¬Έμ
μ€ν (stack)μ κΈ°λ³Έμ μΈ μλ£κ΅¬μ‘° μ€ νλλ‘, μ»΄ν¨ν° νλ‘κ·Έλ¨μ μμ±ν λ μμ£Ό μ΄μ©λλ κ°λ μ΄λ€.
μ€νμ μλ£λ₯Ό λ£λ (push) μ ꡬμ μλ£λ₯Ό λ½λ (pop) μ κ΅¬κ° κ°μ
μ μΌ λμ€μ λ€μ΄κ° μλ£κ° μ μΌ λ¨Όμ λμ€λ (LIFO, Last in First out) νΉμ±μ κ°μ§κ³ μλ€.1λΆν° nκΉμ§μ μλ₯Ό μ€νμ λ£μλ€κ° λ½μ λμ΄λμμΌλ‘μ¨, νλμ μμ΄μ λ§λ€ μ μλ€.
μ΄λ, μ€νμ pushνλ μμλ λ°λμ μ€λ¦μ°¨μμ μ§ν€λλ‘ νλ€κ³ νμ.
μμμ μμ΄μ΄ μ£Όμ΄μ‘μ λ μ€νμ μ΄μ©ν΄ κ·Έ μμ΄μ λ§λ€ μ μλμ§ μλμ§,
μλ€λ©΄ μ΄λ€ μμλ‘ pushμ pop μ°μ°μ μνν΄μΌ νλμ§λ₯Ό μμλΌ μ μλ€.
μ΄λ₯Ό κ³μ°νλ νλ‘κ·Έλ¨μ μμ±νλΌ.μ λ ₯
첫 μ€μ n (1 ≤ n ≤ 100,000)μ΄ μ£Όμ΄μ§λ€.
λμ§Έ μ€λΆν° nκ°μ μ€μλ μμ΄μ μ΄λ£¨λ 1μ΄μ nμ΄νμ μ μκ° νλμ© μμλλ‘ μ£Όμ΄μ§λ€.
λ¬Όλ‘ κ°μ μ μκ° λ λ² λμ€λ μΌμ μλ€.μΆλ ₯
μ λ ₯λ μμ΄μ λ§λ€κΈ° μν΄ νμν μ°μ°μ ν μ€μ ν κ°μ© μΆλ ₯νλ€.
pushμ°μ°μ +λ‘, pop μ°μ°μ -λ‘ νννλλ‘ νλ€. λΆκ°λ₯ν κ²½μ° NOλ₯Ό μΆλ ₯νλ€.
π§ νμ΄
νμ΄ (μκ° μ΄κ³Ό) (μ§κΈ νμΈνλ, νΉμ μ λ ₯κ°μ λν μ€λ₯λ μμ)
# 100,000μ μ ν μκ° 2μ΄λ©΄ μ΄μ€ forλ¬Έμ λ릴 λ, νμ μ μΌλ‘ μκ° μ΄κ³Όκ° λλ€.
# [νμ΄μ¬] λ°±μ€ 1874λ² λ¬Έμ : μ€ν μμ΄
import sys
n = int(sys.stdin.readline())
stack = []
c_list = []
for _ in range(n):
tmp = int(sys.stdin.readline())
for i in range(1, tmp+1):
if i not in stack and i not in c_list:
stack.append(i)
print('+')
c_list.append(stack.pop())
print('-')
λ€λ₯Έ μ¬λ νμ΄
n = int(input()) # n μ
λ ₯ λ° ν λΉ
stack = [] # λΉ μ€ν ν λΉ
result = [] # κ²°κ³Όκ° λ΄μ 리μ€νΈ ν λΉ
count = 0 # λ€μ΄κ° μ«μλ₯Ό μ
count λ³μ ν λΉ
X = True # λΆκ°λ₯ν κ²½μ° Falseλ‘ λ°κΏμ€
for _ in range(n): # nλ§νΌ λ°λ³΅
num = int(input()) # numμ μ«μ μ
λ ₯ λ°μ
while count < num: # countκ° numλ³΄λ€ ν¬μ§ μμ κ²½μ° κ³μ λ°λ³΅
count += 1 # count 1 μ¦κ°
stack.append(count) # μ€νμ count μΆκ°
result.append("+") # result 리μ€νΈμλ '+' μΆκ°
if stack[-1] == num: # stackμ λ§μ§λ§ μ«μκ° numκ³Ό κ°μ λ,
stack.pop() # ν΄λΉ μ«μλ₯Ό pop()
result.append("-") # λμμ result 리μ€νΈμ '-' μΆκ°
else:
X = False # κ·Έλ μ§ μμ κ²½μ°, Falseλ‘ X κ°μ λ³ν
break # μ΄ν breakλ₯Ό ν΅ν΄ λ°λ‘ λ°λ³΅λ¬Έ μ’
λ£
if X == False: # λ§μ½ Xκ° False κ°μ΄λ©΄
print("NO") # 'No'λ₯Ό μΆλ ₯
else:
for i in result: # result 리μ€νΈμ κ° μμ λ³λ‘
print(i) # μΆλ ₯
'𧩠Algorithm > π¨ Python' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[νμ΄μ¬] λ°±μ€ 7576λ² λ¬Έμ : ν λ§ν (0) | 2022.08.27 |
---|---|
[νμ΄μ¬] λ°±μ€ 1926λ² λ¬Έμ : κ·Έλ¦Ό (0) | 2022.08.27 |
[νμ΄μ¬] λ°±μ€ 3135λ² λ¬Έμ : λΌλμ€ (0) | 2022.08.26 |
[νμ΄μ¬] λ°±μ€ 2468λ² λ¬Έμ : μμ μμ (0) | 2022.08.26 |
[νμ΄μ¬] λ°±μ€ 2667λ² λ¬Έμ : λ¨μ§λ²νΈλΆμ΄κΈ° (0) | 2022.08.26 |