파이썬 알고리즘 19일차
처음으로 ~! 다른 사람의 풀이를 봤다! 괜찮다 ~! 하루종일 고민하기보다는 다른 사람의 풀이를 제대로 이해하고 나한테 녹여내기만 한다면... 된다고 했다 !!!
1874: 스택 수열
이건 진짜 문제부터 이해하기 어려웠다... 1~n까지의 수열을 내가 가지고 있을 때, 입력으로 들어온 수열을 pop과 push를 이용해서 만들 수 있으면 +와 -를 이용해 나타내보라, 만들 수 없으면 NO를 출력해라! 라는 문제였다.
음, 수열이 3개가 있다고 생각하면 쉽다.
- 내가 가진 수열: 1부터 n까지 정렬된 수열
- 입력으로 주어진 수열 (정답 레이블)
- 빈 수열
여기서 내가 가진 수열로 pop과 push를 하게 된다. 입력으로 주어진 수열에 맞춰 pop과 push를 진행하다가, pop으로 나온 숫자들은 다시 빈 수열 (3번 수열)에 차곡차곡 쌓는다. 그리고 내가 가진 수열(1번 수열)에서 더 이상 push할 게 없다면! 그런데 pop 명령이 있다면! 빈 수열에서 (3번 수열) 차례대로 꺼내서 정답에 맞게 쌓는 것이다!
휴 정말 이해하는데 힘들었다.
문제를 이해하는 것도 이해하는 것이지만, 입력으로 주어진 수열을 만족하지 못하는 조건을 생각하는 것도 어려웠다. 그래서 생각해보니, 꼭대기 top에서부터 간격이 1씩 증가하는 게 있으면 만족하지 못하는 것이 아닌가...! 생각했다. 네... 딱 여기까지만 생각나고 더 이상 생각에 진전이 없어서 결국 인터넷을 찾아봤다.
1. 내 풀이: 실패
뭐 사실 실패라고 할 것도 없음... 그냥 끝까지 코드를 작성하지 못했으니...
import sys
N = int(sys.stdin.readline())
seq = [int(sys.stdin.readline().strip()) for _ in range(N)]
for i in range(1, len(seq)):
err = seq[i-1]+1
if err == seq[i]:
print('NO')
break
이렇게 하면... 예제 2번에 맞게 NO를 잘 출력하기는 한다...
2. 다른 풀이: 성공
역시 이번에도 깨지고 부서져라님의 풀이를 참고했다.
import sys
N = int(sys.stdin.readline())
s = []
op = []
count = 1
temp = True
for i in range(N):
num = int(sys.stdin.readline().strip())
while count <= num:
s.append(count)
op.append('+')
count+=1
if s[-1] == num:
s.pop()
op.append('-')
else:
temp = False
if temp == False:
print('NO')
else:
for i in op:
print(i)
(출처: https://pacific-ocean.tistory.com/231)
놀라운 건 이 풀이를 보고도 "우오아아앗...!!" 이 아닌... "어...?" 라는 것...^^ 풀이를 이해하는데도 한참 걸렸다.
하나하나 뜯어보자.
import sys
N = int(sys.stdin.readline())
s = []
op = []
count = 1
temp = True
일단 몇 개의 숫자를 입력 받을지를 정해주는 N을 정의한다. 그리고 들어오는 숫자를 담을 리스트 s, pop과 push 를 표시할 리스트 op도 추가해준다. 사실... count를 정의하는데 있어서는 정확히 이해하지 못했는데, 나중에 들어올 num과 비교를 해주기 위해 + s에 count 값을 append 하기 위해 쓰이는 것 같다 (?) 그리고 만들 수 있는 수열인지 아닌지를 판단해줄 temp 변수를 추가해준다. True 값으로 설정해줬기 때문에 일단은 만들 수 있다!고 생각하자는 의미.
for i in range(N):
num = int(sys.stdin.readline().strip())
while count <= num:
s.append(count)
op.append('+')
count+=1
if s[-1] == num:
s.pop()
op.append('-')
else:
temp = False
N을 이용한 for 문과 num을 통해 수열의 숫자를 하나씩 입력 받는다. 이 부분의 코드를 보면 아까 count를 왜 썼는지를 알 수 있는데, num을 통해서 들어오는 숫자들은 꼭대기 top의 숫자들이다. 그런데 우리는 맨 아랫 부분부터 차곡차곡 쌓아 나가야 하니까 이 둘을 비교하면서 s에 count 값들을 append 하는 것이다.
그래서 while 문을 통해서 num보다 count가 작으면 계속해서 count를 s에 append, op에 +(push)를 append를 해준다.
자, 그렇게 num까지 append를 해줬는데, s의 맨 끝 숫자가 num이다 ?! 그러면 다시 빼준다. 왜냐하면 우리의 num은 top에서부터 내려오기 때문이다. 아직 s의 중간 부분(?)에 쌓이면 안되는 것임.
이 부분은 나도 이해가 잘 안 돼서 하나하나 다 찍어보면서 이해해보려 했다.
여기서 5까지 정상적으로 작동되는데, num이 count보다 작아진 순간 while 문이 아닌 바로 if-else문으로 넘어가게 되고, s[-1] = 4이고 num =3 이므로 else문을 따르게 된다. 그러면 temp에 false가 저장되는 것이다. 더 이상 빼고 더하고의 문제가 아니라 그냥 만들 수 없는 수열인 것!!!
if temp == False:
print('NO')
else:
for i in op:
print(i)
그 후에는 쉽다. 그냥 저장된 값 찍어내기...
3. 에필로그: 새로운 오류
temp를 이용해서 조건을 판단하지 말고 내가 만든 조건문으로는 판단할 수 없을까?! 해서 코드를 조금 수정해서 돌려봤다.
import sys
N = int(sys.stdin.readline())
s = []
op = []
count = 1
temp = True
for i in range(N):
num = int(sys.stdin.readline().strip())
while count <= num:
s.append(count)
op.append('+')
count+=1
if s[-1] == num:
s.pop()
op.append('-')
else:
temp = False
print(f'num: {num}, count: {count}, s: {s}, op: {op}, temp: {temp}')
for i in range(1, len(s)):
err = s[i-1]+1
if err == s[i]:
print('NO')
break
for i in op:
print(i)
결론은,
안된다 ^^ 내가 생각한 조건은 조건이 아니었던 걸로... ^^
번외로, 깨지고 부서져라님의 코드를 읽다가 작성자님도 나와 같이 문제를 이해하기 어렵다고 하셨다. 그런데...
네?
네?
네... 더 열심히 공부하겠습니다...........
오늘도 신기한 알고리즘의 세계 끝...^^
Author And Source
이 문제에 관하여(파이썬 알고리즘 19일차), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@drizzle0171/파이썬-알고리즘-19일차저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)