삼성전자 코딩테스트 준비를 위한 문제 풀고 다시 복기해보는 시간

어항 정리

• 난이도 : 백준 플레 5

문제 링크

풀이

삼성 코테는 진짜 문제를 꼼꼼하게 읽고 기능을 나눠서 구현을 하면 되는 것 같다.
근데, 전에 풀어본 상어 문제 같은 경우는 단순히 움직이면 되는 것 같았는데, 이 문제는 90도 회전을 시키고 등등 별 짓을 다하는, 좀 수학적 사고력이 필요한 문제 같았다.

프로세스를 5~6개의 함수로 나눠서 구현을 해보았다.

일단 먼저 입력 받아서 넣어두는 건 제끼고,

1. 가장 물고기 수 적은 어항에 물고기를 채워넣고 , 가장 왼쪽 어항을 오른쪽 어항의 위에 올려 놓는다.

2. 그리고 높이가 2 이상인 어항을 들어서 90도를 돌려서 내리고, 이 과정을 할 수 있는 만큼 무한 반복한다.

2번의 경우가 1차 난관이었는데, 좌표를 90도로 어떻게 돌리지? 생각에 종이에다가 그려서 좌표 변환을 수학계산하여 따져보았다. 90도 돌리는 방법에 대해선 숙지를 할 필요가 있을 것 같다. 그리고 못 돌리는 경우를 따지는 것도 그냥 내 스타일대로 따져주었다.

3. 물고기 수 조절

이것 같은 경우는 동시에 일어나기 때문에, 좌표를 옮겨가면서 숫자를 변환시켜주면 안되고, 좌표를 옮겨 가면서 증가할 어항을 체크를 해놓고 기록한다음에 한번에 수 조절하는 식으로 해야했다.

4. 어항 일렬로 놓기

이건 그냥 for문 돌려서 하면 된다. 어차피 어항의 길이가 길지 않아서 시간복잡도 문제가 전혀 없다.

5. 두번째 회전

이 부분이 나는 문제를 읽으면서 쉬울 줄 알았는데, 은근히 까다로웠다. 이것 또한 움직여질 좌표를 수학 식으로 구해주었고, 가장 큰 부분은 이 과정을 2번만 시행 한다는 것이 문제에 나와 있다는 것.

그래서 이 5개의 과정을 무한 반복하면 된다.

간단해 보이지만 코드 길이가 100줄이 넘고, 구현하는데 4시간정도 걸린 것 같다.

코드

N, K = map(int, input().split())
fishes = list(map(int, input().split()))
graph = [[0] * N for _ in range(N)]  # N * N 짜리 어항
for i in range(len(graph[0])):
    graph[0][i] = fishes[i]


# 가장 물고기 수 적은 어항에 물고기 채워넣기
# 그리고 가장 왼쪽 어항을 오른쪽 위에 있는 어항의 위에 올려 놓기
def add_fish():
    min_fish = min(graph[0])
    for i in range(len(graph[0])):
        if min_fish == graph[0][i]:
            graph[0][i] += 1

    graph[1][1] = graph[0][0]
    graph[0][0] = 0


init_x = 1  # 어항 시작 x값
height = 2  # 어항 최대 높이


def rotate1():
    # 첫 시작 : (0,1) , (1,1)
    global init_x
    global height
    init_x = 1
    height = 2  # 돌릴 어항의 최대 높이. 처음엔 2다.
    xlen = 1  # 돌릴 어항의 가로 길이. 처음엔 1이다

    count = 1  # count = 2가 되면 어항 높이 증가
    max_rotate = N - 1  # 어항 오른쪽에 닿는 걸 판정할 것

    # 회전하는 어항 높이 1*2 -> 2*2 -> 2*3 -> 3 -> 3-> 4
    # 회전해서 올린다.
    while True:
        for y in range(height):
            for x in range(init_x, init_x + xlen):
                graph[xlen - x + init_x][y + init_x + xlen] = graph[y][x]
                graph[y][x] = 0

        count += 1

        init_x += xlen

        if count == 2:
            xlen += 1
            count = 0
        else:
            height += 1

        if max_rotate < init_x + height + xlen - 1:  # 더는 못돌린다.
            break


##  물고기 수 조절
def adjust():
    global height
    global init_x

    ds = [(-1, 0), (1, 0), (0, 1), (0, -1)]  # 인접한 것
    q = []

    # 차이 찾아보기
    for y in range(height):
        for x in range(init_x, N):
            for d in ds:
                ny = y + d[0]
                nx = x + d[1]
                # 맵 밖을 벗어나면
                if ny < 0 or nx < 0 or ny > N - 1 or nx > N - 1:
                    continue

                new = graph[ny][nx]
                origin = graph[y][x]

                # 어항수가 0 이면 안된다.
                if new == 0 or origin == 0:
                    continue

                if new >= origin:
                    d = (new - origin) // 5
                    if d > 0:
                        q.append([d, y, x])
                        q.append([-d, ny, nx])  # y,x 좌표에 d마리 추가

    # 조절 완료
    while q:
        d, y, x = q.pop()
        graph[y][x] += d


# 어항 일렬로 놓기
def array():
    global init_x
    global height
    def_x = 0
    for x in range(init_x, N):
        for y in range(height):
            if graph[y][x] == 0:
                break

            graph[0][def_x] = graph[y][x]
            if y != 0:
                graph[y][x] = 0
            def_x += 1
    init_x = 0


def rotate2():
    global init_x
    global height
    init_x = 0  # 첫 시작은 N/2이다.
    height = 1
    count = 0
    n = 2
    while True:
        if count == 2:
            break
        for y in range(height):
            for x in range(init_x, init_x + N // n):
                graph[height + (height - (y + 1))][N // n + x] = graph[y][(init_x + N // n - (x - init_x + 1))]
                graph[y][(init_x + N // n - (x - init_x + 1))] = 0

        height *= 2
        init_x += N // n
        n = n * 2
        count += 1


answer = 0
while True:
    add_fish()

    rotate1()

    adjust()
    array()
    rotate2()
    adjust()
    array()

    answer += 1
    min_val = min(graph[0])
    max_val = max(graph[0])
    if max_val - min_val <= K:
        break

print(answer)

마법사 상어와 복제

• 난이도 : 백준 골드 1

문제 링크

난이도는 더 쉬웠는데, 내가 문제를 잘못 이해해서 해맸다. 오히려 어항 정리보다 훨씬 오래 걸렸다. 삼성 문제는 문제를 정말 꼼꼼히 읽어야 겠다는 생각이 든다..

이것또한 순차적으로 작업해주면 된다.

풀이

1. 복제할 물고기를 저장해둔다.

파이썬을 사용할때마다 이런 부분이 항상 무섭다. 참조가 기본이므로,, 그래서 똑같은 크기의 배열을 하나 생성해서 거기다가 값을 복사하는 방식으로 했다.

2. 물고기가 방향대로 이동. 방향대로 이동하지 못하면 이동할 수 있을 때까지 45도 회전한다. 이때 이제 이동못하는 케이스가 상어가 있는 칸이랑, 맵 밖이랑, 물고기의 냄새가 남아있는 칸, 이 세가지를 따져주면 된다.

45도 회전해서 이동하는 건 이제 뭐 별일 아니다. 그냥 배열에 8가지 경우 넣어놓고 돌리면 된다.

3. 상어를 3칸 이동시키는데, 이 때 물고기가 있는 칸으로 이동하면 물고기를 다 잡아먹고 2턴 유지되는 냄새를 남긴다. 그리고 상어는 이동했던 칸을 다시 이동할 수 있다.

저 굵은 글씨가 가장 중요한데, 저걸 무시했다가 진짜 엄청 해맸다....하.. 다시 이동하는 경우 물고기를 잡아먹지 않는 것을 따져주면 해결이 된다.

그리고 사전 순으로 정렬해야하는데, 이경우는 노트에 친절히 나와있다. 나같은 경우는 그냥 64가지를 배열에 넣어놓고 매번 따져주었다.

4. 2턴 전에 있던 물고기의 냄새가 사라진다.

이것 같은경우는 물고기의 냄새를 2로 설정해놓고 이 과정마다 1씩 감소시키면 된다.

5. 1에서 복제시킨 물고기들이 생긴다.

이것을 S번 반복하면 된다.

import는 heap하나만 사용했다. 삼성에서는 최대한 기본 import만 사용해서 풀어야 한다.

코드

import heapq

# 가장 왼쪽위는 (1,1) 오른쪽 아래 (4,4)
# 물고기 M마리
# 이동방향 : 8가지 방향

# 0. 복제 마법 시전. (물고기 현재 저장해뒀다가, 나중에 생성한다.)
# 1. 모든 물고기 한 칸 이동.  물고기들은 이동할 수 있을 때 까지 45도 회전, 이동할 수 있는 칸이 없으면 이동 x
# 물고기가 이동할 수 없는 칸 :
# 1) 격자의 범위를 벗어나는 칸
# 2) 상어가 있는 칸
# 3) 물고기의 냄새가 있는 칸


# 2. 상어가 현재 칸에서 상하좌우 인접한 칸으로 3칸 이동한다. 물고기 만나면 물고기 아웃 그리고 냄새를 남긴다.
# 3. 두 번 전 연습에서 생긴 물고기 냄새가 사라진다.
# 4. 0번에서 시전한 복제가 완료되어서, 복제한 위치와 방향을 그대로 붙여넣는다.

# 1부터 순서대로 반시계 방향  (y,x)
delta = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)]
M, S = map(int, input().split())

graph = [[[] for _ in range(5)] for _ in range(5)]  # graph[y][x] : 이 칸에 들어있는 물고기 번호 집합

# 상어가 움직일 수 있는 모든 경우의 수. 상 좌 하 우 순서. (y,x)
dir_list = [(0, -1), (-1, 0), (0, 1), (1, 0)]
shark_case = []
for i in range(4):
    for j in range(4):
        for k in range(4):
            shark_case.append([dir_list[i], dir_list[j], dir_list[k]])


# 맵 벗어나는지 확인하는 함수
def check(check_x, check_y):
    if 1 <= check_x <= 4 and 1 <= check_y <= 4:
        return True

    return False


fish_smell = [[0] * 5 for _ in range(5)]  # 이 칸에 물고기 냄새가 몇턴 전에 있던 냄새인지.

# 처음 입력 받기
for _ in range(M):
    fx, fy, d = map(int, input().split())
    graph[fx][fy].append(d - 1)

shark_x, shark_y = map(int, input().split())


# ---------------입력 끝 함수 시작-------------


# 0. 물고기 복사
def magic():
    fish_copy = [[[] for _ in range(5)] for _ in range(5)]
    global graph
    for yy in range(1, 5):
        for xx in range(1, 5):
            for dd in graph[xx][yy]:
                fish_copy[xx][yy].append(dd)
    return fish_copy


# 1. 물고기 이동
def move_fish():
    global graph
    global fish_smell
    move_temp = [[[] for _ in range(5)] for _ in range(5)]
    for xx in range(1, 5):
        for yy in range(1, 5):
            while graph[xx][yy]:
                dd = graph[xx][yy].pop()
                move_flag = True
                for count in range(8):
                    nd = (dd - count) % 8
                    ny = yy + delta[nd][0]
                    nx = xx + delta[nd][1]

                    if not check(nx, ny):  # 1. 격자 밖을 나가는 경우
                        continue

                    if shark_x == nx and shark_y == ny:  # 2. 상어가 있는 칸인 경우
                        continue

                    if fish_smell[nx][ny] > 0:  # 3. 냄새가 있는 칸인 경우
                        continue

                    # 그 외의 경우는 이동할 수 있다.
                    move_temp[nx][ny].append(nd)
                    move_flag = False
                    break

                if move_flag:  # 움직일 수 없는 경우
                    move_temp[xx][yy].append(dd)

    return move_temp


# 2. 상어가 이동
def move_shark():
    global shark_y
    global shark_x
    q = []  # 상어 이동 경로 찾기 위해서,, 우선순위큐를 역순으로 사용할 것
    case = 0
    for shark_dir in shark_case:
        isvisited = [[False for _ in range(5)] for _ in range(5)]
        eat_fishnum = 0
        flag = True
        shark_ny = shark_y
        shark_nx = shark_x
        for dir_y, dir_x in shark_dir:  # 각 경우 별로 움직이는 것
            shark_nx += dir_x
            shark_ny += dir_y
            if not check(shark_nx, shark_ny):  # 격자를 벗어나는 경우, 상어는 움직이지 못하므로 제외
                flag = False
                break

            if not isvisited[shark_nx][shark_ny]:
                eat_fishnum += len(graph[shark_nx][shark_ny])
                isvisited[shark_nx][shark_ny] = True

        if flag:  # 격자를 안벗어난 경우
            heapq.heappush(q, (-eat_fishnum, case, shark_dir))  # case가 사전순이므로, case로 넣어서 사전 순 판별.
            case += 1

    c, cc, moves = heapq.heappop(q)  # 제일 많이 없어진 경우 뽑아온다. 그래서 상어 움직여 줘야 한다.
    for dir_y, dir_x in moves:
        shark_y += dir_y  # 상어 움직인다.
        shark_x += dir_x
        if graph[shark_x][shark_y]:  # 물고기가 있는 경우
            fish_smell[shark_x][shark_y] = 3  # 냄새를 남기고
            graph[shark_x][shark_y].clear()


# 3. 냄새가 사라진다.
def remove_smell():
    global fish_smell
    for sy in range(1, 5):
        for sx in range(1, 5):
            if fish_smell[sx][sy] > 0:  # 0이 아니면 냄새가 있는 것이므로, 1씩 줄어든다. 처음에 2일 것이므로, 2->1->0 이런식
                fish_smell[sx][sy] -= 1


# 4. 복제 완료
def copy_complete(copy_fish):
    for yy in range(1, 5):
        for xx in range(1, 5):
            while copy_fish[xx][yy]:
                dd = copy_fish[xx][yy].pop()
                graph[xx][yy].append(dd)


for _ in range(S):
    # 0. 복제 마법 시전 -> 복제할 리스트에 물고기 저장
    cf = magic()
    graph = move_fish()
    move_shark()
    remove_smell()
    copy_complete(cf)

answer = 0
for y in range(1, 5):
    for x in range(1, 5):
        answer += len(graph[x][y])

print(answer)

파이썬의 참조 문제 때문에, 고민을 많이 하게 되는 문제였다. 이런 방식에 좀 익숙해질 필요가 있다고 생각한다.