2023년 7월 28일 알고리즘 문제풀

백준 11866번

문제 링크

1차 시도

나의 생각

처음엔 인덱스를 옮겨가면서 없어진 수를 표시하는 방법을 생각했다. 예를 들어 [[1,0].[2,0],[3,0],[4,0].[5,0]] 이런 식을 설정하고 빠지는 원소는 2번째 원소를 1로 바꿔주는 방법. 하지만 굳이 배열을 한번 더 복잡하게 만들어야 할 필요성이 없다고 생각했다. 따라서 덱으로 설정한 배열의 가장 앞 원소만 주목하되, 현재 뺄 차례인지 그냥 넘어갈 차례인지만 분류하면 되겠다고 판단하였다. 뺄 차례라면 popleft 한 후 따로 만들어둔 정답을 위한 배열에 append 하였다. 로직 자체는 어려움이 없었으나 예제에서 출력할 때 수열을 담는 괄호가 대괄호가 아니라 그냥 괄호 ‘<>‘였다. 이 부분이 신경쓰였지만 가장 먼저 ‘<‘를 배열의 앞에 넣어주고, 수열을 넣을 때 마다 숫자를 str로 바꾼 후 따옴표(,)와 공백( )을 붙여서 넣었다. 그 이후 *를 이용해 원소들만 출력했다.

결과

오답

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import sys
from collections import deque

n,k = map(int,sys.stdin.readline().split())

arr = deque()
ans = []
ans.append('<')

for i in range(1,n+1):
    arr.append(i)

cnt = 1
while arr:
    if cnt == k:
        tmp = arr.popleft()
        tmp = str(tmp)+','+' '
        ans.append(tmp)
        cnt = 1
    else:
        tmp = arr.popleft()
        arr.append(tmp)
        cnt += 1
q = ans.pop()
ans.append(q[0])
ans.append('>')
print(*ans,sep='')

2차 시도

나의 생각

아무리 생각해도 알고리즘 상 반례나 잘못된 부분을 찾을 수 없었다. 결과를 출력하는 부분이 마음에 걸려 join을 사용하였더니 바로 정답처리 되었다. 하지만 왜 첫번째 코드가 잘못됐냐는 물음에 답이 안나왔다. 하지만 결국 찾아냈다!

첫번째 코드에 11,1 을 넣으면 알 수있다.

11, 1 을 넣으면 올바른 정답은 <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11> 이 나와야 한다. 하지만 넣어보니 <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1>이 나왔다! 맨 마지막에 11이 들어가지만, 마지막 원소의 쉼표와 공백을 빼주느라 pop한후 q[0]만 넣는 위 코드의 24번~26번 행에서 문제가 발생했다. 11은 두자리 수니까 q[1]까지 다 넣어야 하는데!

즉 저 코드는 마지막 에 들어온 수가 한 자리 수 일때만 작동하는 코드였다.

그냥 join으로 원소마다 쉼표 붙여주는게 편리했다..

결과

정답

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys
from collections import deque

n,k = map(int,sys.stdin.readline().split())

arr = deque()
ans = []

for i in range(1,n+1):
    arr.append(i)

cnt = 1
while arr:
    if cnt == k:
        tmp = arr.popleft()
        ans.append(str(tmp))
        cnt = 1
    else:
        tmp = arr.popleft()
        arr.append(tmp)
        cnt += 1
print("<", ', '.join(ans), ">", sep="")

백준 3190번

문제 링크

1차 시도

나의 생각

문제에서 제시한 그대로 로직을 처리하였다. 우선 뱀이 존재하는 배열, 사과를 위한 배열, 방향 전환을 위한 배열을 만들었다. 시간초가 바뀌면 머리가 이동한 좌표가 보드 내부인지 검사하고 괜찮으면 배열에 추가하였다. 그 후 사과의 존재 여부에 따라 꼬리를 빼거나 뺴지 않도록 결정하고 방향전환은 문제에서 정렬되어 주니 마지막에 방향전환할 때인지 검사해주었다.

주어진 예제에서 2번만 답이 1 더 나와서 해결하지 못했다.

결과

오답

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

import sys
from collections import deque

t = 0
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
snake = deque()
snake.append([1,1])
apples = []

for _ in range(k):
    a,b = map(int,sys.stdin.readline().split())
    apples.append([a,b])

l = int(sys.stdin.readline())
move = deque()
for _ in range(l):
    x,c = sys.stdin.readline().rstrip().split()
    move.append([x,c])

i = 0
direction_a = [0,-1,0,1]
direction_b = [1,0,-1,0]

next_move = move.popleft()

while True:
    t += 1
    head_a = snake[-1][0]
    head_b = snake[-1][1]
    newhead_a = head_a + direction_a[i]
    newhead_b = head_b + direction_b[i]
    newhead = [newhead_a,newhead_b]

    if newhead_a > n or newhead_a < 0 or newhead_b < 0 or newhead_b > n or newhead in snake:
        break

    snake.append(newhead)
    if newhead in apples:
        apples.remove(newhead)
    else:
        snake.popleft()

    if str(t) == next_move[0]:
        if next_move[1] == 'L':
            i += 1
        else:
            i -= 1
        next_move = move.popleft()
        if i > 3:
            i %= i
        elif i < 0:
            i += 4

print(t)

2차 시도

나의 생각

딱 2번 예제만 안되는 것 같아 디버깅을 해보았더니 결과를 찾았다.

보드의 의 범위는 1부터 n까지였다!

뱀의 다음 이동 좌표를 검사할때 범위 설정을 잘못해서 발생한 문제였다.

결과

정답

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

	import sys
from collections import deque

t = 0
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
snake = deque()
snake.append([1, 1])
apples = []

for _ in range(k):
    a, b = map(int, sys.stdin.readline().split())
    apples.append([a, b])

l = int(sys.stdin.readline())
move = deque()
for _ in range(l):
    x, c = sys.stdin.readline().rstrip().split()
    move.append([x, c])

i = 0
direction_a = [0, -1, 0, 1]
direction_b = [1, 0, -1, 0]

next_move = move.popleft()

while True:
    t += 1
    head_a = snake[-1][0]
    head_b = snake[-1][1]
    head_a += direction_a[i]
    head_b += direction_b[i]
    head = [head_a, head_b]

    if head_a > n or head_a < 1 or head_b < 1 or head_b > n or head in snake:
        break

    snake.append(head)
    if head in apples:
        apples.remove(head)
    else:
        snake.popleft()

    if str(t) == next_move[0]:
        if next_move[1] == 'L':
            i += 1
        else:
            i -= 1
        if move:
            next_move = move.popleft()
        if i > 3:
            i %= i
        elif i < 0:
            i += 4

print(t)

백준 11279번

문제링크

1차 시도

나의 생각

heapq 를 예전에 공부했던 기억이 가물가물 났다. 그리고 분명히 최소힙 이였던 것 같았다. 우선 import 한 후 heapq를 쓰고 마우스를 올려 읽어보니 어떻게 쓰는건지, 어떻게 써야할지 알게 되었다. from heapq이고 heappop, heappush를 import해야 하는것, heapq는 가장 작은 수가 앞에 있다는 것. 문제는 자연수 중 최대라는 조건이니 넣을 때 음수로 변환하여 넣고 최솟값을 뽑아 출력할땐 양수로 바꿔주었다.

결과

정답

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import sys
from heapq import heappop,heappush
n = int(sys.stdin.readline())
arr = []
for _ in range(n):
    x = int(sys.stdin.readline())
    if x == 0:
        if arr:
            tmp = heappop(arr)
        else:
            tmp = 0
        tmp *= -1
        print(tmp)
    else:
        heappush(arr,-x)