-
[BOJ 19941, Python 3] 햄버거 분배알고리즘/BOJ 2021. 8. 4. 13:50반응형
https://www.acmicpc.net/problem/19941
풀이
컵홀더 문제랑 비슷한데, 컵홀더는 K = 1일때만 가능한 문제이고 이건 K가 아무런 값이 주어졌을 때도 풀 수 있는 좀 더 업그레이드된 문제입니다.
저는 큐를 불러오면 코드가 길어지기 때문에 그냥 ←방향으로 스택을 이용해서 풀었습니다.
풀이는 간단합니다. 일단 큐나 스택을 2개 만들어서 햄버거의 좌표, 사람의 좌표를 따로따로 넣어줍니다.
그다음 → 방향이든, ← 방향이든 햄버거를 먹을 수 있는 사람이 있으면 답에 1을 더해줍니다.
이제 방향에 따라서 코드가 살짝 달라지는데, 제가 풀은 ← 방향 기준으로 설명하겠습니다.
← 방향은 스택으로 값을 넣어서 pop을 사용하기 때문에 인덱스가 큰 값에서 작은 값으로 이동하는 점을 기억하셔야 합니다.
햄버거의 위치가 (현재 사람의 위치) - K보다 작을 때는 다음 사람이 저 햄버거를 먹을 수도 있습니다.(ex K = 1, HPP) 그래서 사람의 좌표가 들어간 스택을 하나 빼줍니다.
반대로 햄버거의 위치가 (현재 사람의 위치) + K보다 클 경우에는 다음 사람도 저 햄버거를 먹지 못하는 경우입니다.(ex K = 1, PPHHHH) 이 경우엔 햄버거의 좌표가 들어간 스택을 하나 빼줍니다.
이렇게 풀면 답이 나옵니다.
코드
1234567891011121314151617n, k = map(int, input().split())s = [*input()]p = []h = []for i in range(n):if s[i] == 'H': h.append(i)else: p.append(i)ans = 0while p and h:if p[-1] - k <= h[-1] <= p[-1] + k:ans += 1h.pop()p.pop()elif p[-1] - k > h[-1]: p.pop()else: h.pop()print(ans)cs 반응형'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ 1541, Python 3] 잃어버린 괄호 (0) 2021.08.04 [BOJ 1080, Python 3] 행렬 (0) 2021.08.04 [BOJ 18310, Python 3] 안테나 (0) 2021.08.03 [BOJ 11508, Python 3] 2+1 세일 (0) 2021.08.03 [BOJ 11501, C++, Python 3] 주식 (0) 2021.08.03