[알고리즘] direct, pattern, bucket 활용

1. 다이렉트(Direct) 배열 활용

direct 배열을 이용해 2차원 배열에서 한 좌표를 기준으로 특정 위치에 있는 좌표를 확인할 수 있다.

# 기준 좌표의 상하좌우를 합하는 과정
arr=[[3,5,4],[1,1,2],[1,3,9]]
y,x=map(int,input().split())   # 기준 좌표

# 1
directy=[-1,1,0,0]
directx=[0,0,-1,1]
sum=0
for i in range(4):
    dy=directy[i]+y
    dx=directx[i]+x
    if dy<0 or dy>2 or dx<0 or dx>2: continue
    sum += arr[dy][dx]
print(sum)

# 2
sum=0
for i,j in (-1,0),(1,0),(0,-1),(0,1): # 튜플을 이용
    dy,dx=i+y,j+x
    if 0<=dy<=2 and 0<=dx<=2:
        sum+=arr[dy][dx]
print(sum)

# 상하좌우 좌표의 합의 max와 기준 좌표 찾기
arr=[[1,2,3,4],
    [1,2,9,4],
    [1,9,3,9],
    [1,2,9,4]]

def isSum(y,x):  # 기준 좌표
    directy=[-1,1,0,0]
    directx=[0,0,-1,1]
    sum=0
    for i in range(4):
        dy=directy[i]+y
        dx=directx[i]+x
        if dy<0 or dx<0 or dy>3 or dx>3: continue # 배열범위 벗어나면 계산 안함
        sum+=arr[dy][dx]
    return sum

Max=int(-21e8)
Maxi,Maxj=0,0
for i in range(4):
    for j in range(4):
        ret=isSum(i,j)
        if ret>Max:
            Max=ret
            Maxi=i
            Maxj=j
print(Max,Maxi,Maxj)

• direct를 활용한 문제💡
  • SWEA 달팽이 숫자
  • SWEA Ladder1

2. 패턴(Pattern) 찾기

for문을 이용해 한 배열 내에서 특정 패턴이 있는지 없는지 찾을 수 있다.
함수로 분리하면 훨씬 직관적인 코드를 짤 수 있다.

def isPtn(dy, dx): # 패턴 확인 함수 분리
    for i in range(2):
        for j in range(2):
            if board[dy+i][dx+j] != ptn[i][j]:
                return 0
    return 1

board = [
    ["A", "B", "G", "K"],
    ["T", "T", "A", "B"],
    ["A", "C", "T", "T"]
]
    

ptn = [list(input()) for _ in range(2)] # 2, 2 크기의 이차원 배열을 입력 받음 (찾을 대상)

cnt = 0
for y in range(2):
    for x in range(3):
        if isPtn(y, x):          
            cnt += 1

if not cnt:
    print('미발견')
else:
    print(f'{cnt}개 발견')

# input
# AB
# TT
# output
# 2개 발견

3. 버켓(Bucket)을 활용

bucket이란 배열에 특정 값이 몇 번 등장하는지를 담은 배열이다.
bucket은 마치 dictionary와 같은 역할을 하지만 dictionary보다 실행시간이 짧다는 장점이 있다.
주의할 점은 숫자의 등장 횟수만 담을 수 있다.
그리고 배열의 최댓값을 알아야 효율적으로 사용할 수 있다.

a = list(map(int, input().split()))
bucket = [0]*len(a)

for i in range(len(a)):
    bucket[a[i]] += 1

for j in range(1, len(bucket)):
    if bucket[j] > 0:
        print(f'{j}는 {bucket[j]}개 존재')

• bucket을 활용한 문제💡
  • 삼성시의 버스 노선