백준 ) 알고리즘 수업 - 삽입 정렬 1
해당 문제는 문제의 이름에서 나와 있듯이 삽입 정렬을 구현하여 진행하는 문제이다
문제에서 대강의 로직을 주어져 있기에 그것을 기반으로 문제를 풀어 나가면 되는 문제였다.
그런데 쉽게 풀릴 이문제는 생각 보다 많이 틀리게 되었는데 이번 포스팅은 왜 이렇게까지 많이 틀렸는지 에 대한 내용을 다룰려고 한다.
위의 사진 처럼 10번 째에 맞추게 되었는데 맞춘 부분도 PyPy3에서는 통과가 되고 Python 3에는 시간 초과가 났다. print() 함수를 사용해서 안되는가 해서 sys.stdout.write()도 쓰고 중간 중간 return 해주는 종료 문들도 넣어 주었는데도 시간 초과가 난 것을보아 코딩 로직의 문제보다는 성능 문제 때문인거 같다
실패 1
import sys
N, K = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
def insertion_sort(A, k): # A[1..N]을 오름차순 정렬한다.
answer = 3
v = 0
for i in range(1, N):
loc = i - 1
newItem = A[i]
while (0 <= loc and newItem < A[loc]):
A[loc + 1] = A[loc]
answer += 1
if answer == k-3:
v = A[loc + 1]
loc -= 1
A[loc + 1] = newItem
return answer, v
check, v = insertion_sort(a, K)
if check >= K:
print(v)
else:
print(-1)위 코드는 어찌되었든 예시만 출력 해 보자라는 마인드로 어거지로 만든 부분이다. 코드를 보시면 아시겠지만 answer 값을 초기에 3을 추가 해주고 돌린 부분이다.
지금 생각해보면 왜 저렇게까지 했는지 아직도 의아한 부분이다....(많이 힘들었나? 뭐, 백준 구슬탈출을 계속 실패만 머리도 식힐겸 푼 부분이라...)
어찌 되었든 위의 코드는 말그대로 예시만 출력 해주는 부분이기에 당연히 다른 반례가 들어가면 정상 동작이 안되는 부분이다.
그렇다면 어떻게 코드를 풀어야 할까?
실패 코드 2
import sys
N, K = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
def insertion_sort(A, k): # A[1..N]을 오름차순 정렬한다.
answer = -1
v = 0
for i in range(1, N):
loc = i - 1
newItem = A[i]
answer += 1
if answer == k:
v = A[loc + 1]
while (0 <= loc and newItem < A[loc]):
A[loc + 1] = A[loc]
answer += 1
if answer == k:
v = A[i]
loc -= 1
A[loc + 1] = newItem
return answer, v
check, v = insertion_sort(a, K)
if check >= K:
print(v)
else:
print(-1)일단 초기값 answer를 원래대로 돌리는게 맞다. 임의 값을 주는게 아닌 시작값을 고정으로 해야 맞고 이후 정렬 작업시 answer 값을 컨트롤 하는게 맞다
그런데 이 코드도 자세히 보면 answer 값이 -1로 되어있다. 이 부분은 내가 생각한 값보다 1이 더 출력이 되기에 시작 값을 -1로 했는데 그러면 안된다. 이렇게 푸는 건 첫번째로 풀었던 예시만 정답이다라는 생각을 가지고 푼거랑 크게 다를바가 없기 때문이다
그러므로 answer 의 값은 0 이 되어야 한다.
자 그럼 이제 해결 방법들이 거의다 나왔다.
1. answer의 값은 0으로 시작
2. answer 값이 K일때 값을 찾아 출력 해주기
3. answer 값이 K 보다 작으면 -1을 출력 해주기
실패 코드 3
import sys
N, K = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
def insertion_sort(A, k): # A[1..N]을 오름차순 정렬한다.
answer = 0
v = 0
for i in range(2, N):
loc = i - 1
newItem = A[i]
while 0 <= loc and newItem < A[loc]:
A[loc + 1] = A[loc]
answer += 1
if answer == k:
v = A[loc + 1]
loc -= 1
if loc + 1 != i:
A[loc + 1] = newItem
answer += 1
if answer == k:
v = A[loc + 1]
return answer, v
check, v = insertion_sort(a, K)
if check < K:
print(-1)
else:
print(v)그렇게 해서 문제에서 요구한 사항 대로 거의다 만들었다. 그런데 이때 나는 큰 실수를 했다. 그건 문제에서 2부터 시작 한다는 부분에서 착각을 하여 for 문 시작 값으 2로 준것이다
그리고 for문 마지막의 answer 증가 부분을 무조건으로 했던 부분도 있었다.
최종! 정답 주의 !!!
import sys
N, K = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
def insertion_sort(A, k): # A[1..N]을 오름차순 정렬한다.
answer = 0
v = 0
for i in range(1, N):
loc = i - 1
newItem = A[i]
while 0 <= loc and newItem < A[loc]:
A[loc + 1] = A[loc]
answer += 1
if answer == k:
v = A[loc + 1]
loc -= 1
if loc + 1 != i:
A[loc + 1] = newItem
answer += 1
if answer == k:
v = A[loc + 1]
return answer, v
check, v = insertion_sort(a, K)
if check < K:
print(-1)
else:
print(v)그렇게 실수들을 바로 잡고 코드를 작성하니 무사히 통과를 하게 되었다.
이번에 문제를 통하여 느낀점은 너무 내 생각에 빠져 무조건 그 코드만 가지고 풀려고 하는 부분이 컸던거 같다.
때문 처음으로 돌아가 새로운 방식으로 접근도 해보고 왜 내가 작성 한 코드는 초기 값을 0이 아닌 다른 것으로 주고 해야지만 맞는 건지에 대해 깊게 고민해 보는 습관을 길러야 할 거같다
초기값을 임의로 문제에 정답이 나오도록 셋팅하는 건 틀린 코드이다.
물론 틀린 코드 또한 어찌 되었든 만드는게 중요하다. 우리는 무에서 유를 창조를 할 수 있는 능력자가 아니다.
그러니 아예 손도 못대기 보다는 어떻게든 손을 대고 그 손댄 부분에서 어떻게 하면 돌아 갈지 라는 생각까지 해내는게 무엇보다 중요하다고 나는 생각한다
이글은 누군가 읽어 보게 된다면 어찌되었든 포기는 하지말고 끝까지 엉덩이 붙이고 해결 해 나가려는 끈기를 가지기를 바라며 글을 마치겠다.