koala 3주차 : 시뮬레이션, 투 포인터
* 시뮬레이션(구현)
시뮬레이션은 단순히 '구현'을 하는 유형이다.
2차원 공간을 다루는 문제가 자주 나오기 때문에 방향(상,하,좌,우)에 대한 자신만의 처리 방식을 가지는게 좋고 특정 게임을 구현하는 문제들은 몇 가지 자체적인 테스트 케이스를 만들어주면 유용하다.
시뮬레이션 유형 같은 경우에는 많이 풀어보고 다른 사람들의 풀이를 참고하는 것이 좋은 공부법이라고 하니, 양치기로 한번 부딪혀보자.
1. 25966 : 배찬우는 배열을 좋아해
https://www.acmicpc.net/problem/25966
import sys
input = sys.stdin.readline
n,m,q = map(int, input().split())
list1 = []
for _ in range(n):
list1.append(list(map(int, input().split())))
for _ in range(q):
n_list = list(map(int, input().split()))
i,j,k = 0,0,0
i = n_list[1]
j = n_list[2]
if len(n_list) == 4:
k = n_list[3]
list1[i][j] = k
else:
list1[i], list1[j] = list1[j], list1[i]
for i in list1:
print(*i)
리스트 요소 서로 바꿔주고 요소값 바꿔주는 문제이다. 생각보다 에러가 났었는데, 변수 = 바꿔야할 변수값 // 이렇게 했어야 했는데 반대로 한 코드가 있어서 제대로 안돌아갔던 것 같다. 아무튼 이건 크게 배울 점이 없으므로 패스!!
2. 1193 : 분수찾기
import sys
input = sys.stdin.readline
n = int(input())
line = 0
while n>0:
line += 1
n -= line
if line %2 ==0:
a = str(line+n)
b = str(abs(n)+1)
print(a+'/'+b)
else:
a = str(abs(n)+1)
b = str(line+n)
print(a+'/'+b)
1/1
1/2, 2/1
3/1, 2/2, 1/3
1/4, 2/3, 3/2, 4/1
5/1, 4/2, 3/3, 2/4, 1/5
이렇게 수들을 정렬해서 보면, 짝수라인과 홀수라인의 규칙이 보인다. 그 규칙을 생각해서 구현해주면 된다.
3. 2108 : 통계학
import sys
from collections import defaultdict
input = sys.stdin.readline
n = int(input())
list1 = []
for _ in range(n):
list1.append(int(input()))
list1.sort()
a,b,c,d = 0,0,0,0
a = round(sum(list1)/n)
b = list1[int(n/2)]
dict1 = defaultdict(int)
for i in list1:
dict1[i] += 1
mx = max(dict1.values())
mx_list = []
for i in list1:
if dict1[i] == mx:
mx_list.append(i)
mx_list = list(set(mx_list))
if len(mx_list) == 1:
c = mx_list[0]
else:
mx_list.sort()
c = mx_list[1]
d = list1[-1]-list1[0]
print(a)
print(b)
print(c)
print(d)
나머지는 정말 쉬웠지만 최빈값을 구하는 과정에서 상당히 애를 먹었던 것 같다. 리스트의 요소들 중 가장 많이 나타낸 값을 출력해야 하는데, 그냥 max를 함수를 이용하면 될 것이 아니었다. 문제 조건에 최빈값이 여러 개 있을 때는 두 번째로 작은 값을 출력해야 한다고 되어있는데, 그것이 문제였다.
해결방법은 최대값을 뽑아서 변수에 저장하고 최대값에 해당하는 dictionary의 key값들을 모아서 해당하는 key값이 하나일때는 바로 출력, 여러 개(2개 이상)일때는 다시 정렬해서 2번째로 작은 값을 출력할 수 있도록 해주었다.
* 투 포인터
- 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때까지 탐색하는 알고리즘이다.
1. 동작 방식 및 구현
- 보통 left(l), right(r)이나 start(s), end(d) 같은 식으로 포인트의 이름을 붙임
- 위처럼 포인트 2개를 준비하고, 찾는 값은 target이 됨
- 처음에는 start=end=0이고, 조건은 항상 두 포인터들의 관계는 start<=end임
- 2개의 포인터는 현재 부분 배열의 시작(start)과 끝(end)을 가리킴
+) 시간복잡도는 O(N)을 가진다.
2. 문제를 해결할 때 가질 실전적인 마인드
- 2개의 포인터를 각각 무엇으로 잡을지
- 각 포인터가 움직여야 할 상황을 정의하는 것
* 예제
1. 2467 : 용액
https://www.acmicpc.net/problem/2467
import sys
input = sys.stdin.readline
n = int(input())
list1 = list(map(int, input().split()))
left, right = 0, n-1
ans = list1[left] + list1[right]
ans_right = right
ans_left = left
while left<right:
tmp = list1[left] + list1[right]
if abs(tmp)<=abs(ans):
ans = tmp
ans_right = right
ans_left = left
if ans == 0:
break
if tmp<0:
left += 1
if tmp>0:
right -= 1
print(list1[ans_left], list1[ans_right])
중요한 부분은 2가지
1. 포인터 2개를 양끝으로 잡고
2. 포인터 2개에 해당하는 리스트값들의 합의 절대값이 기존의 최소 절대값 합보다 작으면 정답을 바꿔주고 아닌 경우에는 두 용액의 합이 0보다 작으면 왼쪽 리스트 index값을 하나 증가, 0보다 크면 오른쪽 리스트 index값을 하나 감소시키면 된다.
2. 2230 : 수 고르기
https://www.acmicpc.net/problem/2230
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
list1 = []
for _ in range(n):
list1.append(int(input()))
list1.sort()
start, end = 0, 1
ans = 2e9
while start<=end and end<n:
tmp = list1[end]-list1[start]
if tmp>=m:
if tmp<ans:
ans = tmp
start += 1
else:
end += 1
print(ans)
3. 1806 : 부분합
import sys
input = sys.stdin.readline
n,s = map(int, input().split())
list1 = list(map(int, input().split()))
end = 0
interval_sum = 0
count = 100000
for start in range(n):
while interval_sum<s and end<n:
interval_sum += list1[end]
end += 1
if interval_sum >= s:
cnt = end-start
count = min(cnt, count)
interval_sum -= list1[start]
if count == 100000:
print(0)
else:
print(count)
투포인터 관련 예제를 구글에 검색했을 때 가장 많이 나오는 것이 '부분 합'이었다. 마지막에 잘 만든 것 같은데 계속 틀리다고 해서 왜 그런지 살펴보았더니 부분합의 합이 s "이상"이 되는 것을 찾는 것이 조건이었는데, 나는 부분합의 합이 딱 's'가 되는 것으로 코딩을 해서 틀렸다. 문제의 조건을 차분히 잘 보는 것도 매우 중요하다..!