삼성 SW 코테 기출, 어항정리

삼성전자 SW 코딩테스트 기출문제 해설입니다.

https://www.acmicpc.net/problem/23291

23291번: 어항 정리

 

문제에 나와있는 스텝대로 구현하기만 하면 되는 문제였다. 특별한 자료구조 사용하지 않고 그냥 2차원 배열로 구현하였는데, 따로 시간초과가 뜨지는 않았다. 하지만 코드를 최적화시키기에는 시간이 부족했다. 그래서 코드가 엉망이다.. 따로 함수로 빼고 싶은 것들이 많은데 일단 실전이라 생각하고 그냥 적어보겠다.

위와 같은 어항이 주어졌다. 가장 간단히 생각할 수 있듯이 자연스럽게 list에 넣어주었다. 가장 작은 물고기가 들어있는 어항에 1개씩 물고기를 추가한다. Min 함수를 이용해주었다. 

맨 왼쪽에 있는 어항을 2층에 쌓는다. fish=[[3,3,14,9,3,11,8],[5]] 와 같이 층을 나누어주었다.

 

어항쌓기

그 다음부터는 2개 이상 쌓여있는 어항을 들어서 시계방향으로 90도 회전시켜 쌓아야 한다. while문을 이용해서 전체 층 수보다 1층에 남아있는 어항개수가 작으면 break 하도록 해준다. 그냥 인덱스만 잘 조절해줘서 n^2으로 풀었다. 

어항쌓기를 끝내면 위와 같은 상태가 되는데, 이제 물고기 수 조절하기 단계다.

 

물고기 수 조절하기

먼저 list fish와 같은 사이즈, 0으로 채워져있는 temp를 마련하였다. 두개의 어항의 차를 계산하는 것이 중복되면 안되기 때문에, 각 어항에서 오른쪽과 위쪽, 총 2방향만 고려해서 d를 temp에 반영해주었다. 처음에는 문제를 대충읽어서 어느 쪽 어항부터 조절해야하지? 라고 생각했는데, 그냥 동시에 하는 거였다. 문제를 잘 읽고 시간낭비를 줄여야겠다!

물고기 수를 조절하면 다음과 같다. 그 후 이를 일렬로 펴주어야 하는데, transpose를 구하면 쉽겠지만 구할 수 있는 형태가 아니어서 for문을 사용하였다. new_fish=[3,3,1,1] 로 놓고 이를 이용해서 펴주었다.

이렇게 핀 이후 2번 접고, 다시 위의 물고기 조절 작업을 한 다음 다시 펴주면 된다. 

N, K = map(int, input().split())
fish = list(map(int, input().split()))
# N, K = 4, 0
# fish = [1, 10000, 1, 10000]

def fish_shuffle(fish, N):
    # 작은 것에 1씩 더한다
    a = min(fish)
    temp = []
    for i, v in enumerate(fish):
        if v == a:
            temp.append(i)
    for i in temp:
        fish[i] += 1

    # 맨 앞 어항을 2층으로 보낸다
    a = fish.pop(0)
    fish = [fish]
    fish.append([a])

    # 어항 쌓기
    while True:
        floor2 = len(fish[1])
        new_fish = [fish[0][floor2:]]  # 1층 완료
        if len(new_fish[0]) < len(fish): # 층수보다 1층에 남아있는 어항개수가 작으면 stop
            break
        for i in range(floor2):
            b = [fish[j][floor2-i-1] for j in range(len(fish))]
            new_fish.append(b)
        fish = new_fish

    # 어항 속 물고기수 조절하기, 각 어항에서 2방향만 확인
    temp = [[] for i in range(len(fish))]
    for i in range(len(fish)):
        for j in range(len(fish[i])):
            temp[i].append(0)
    for i in range(len(fish)):
        for j, v in enumerate(fish[i]):
            #오른쪽 확인
            try:
                if fish[i][j] > fish[i][j+1]:
                    d = (fish[i][j] - fish[i][j + 1]) // 5
                    temp[i][j] -= d
                    temp[i][j+1] += d
                else:
                    d = (fish[i][j+1] - fish[i][j]) // 5
                    temp[i][j] += d
                    temp[i][j + 1] -= d
            except:
                pass

            #위쪽 확인
            try:
                if fish[i][j] > fish[i+1][j]:
                    d = (fish[i][j] - fish[i+1][j]) // 5
                    temp[i][j] -= d
                    temp[i+1][j] += d
                else:
                    d = (fish[i+1][j] - fish[i][j]) // 5
                    temp[i][j] += d
                    temp[i+1][j] -= d
            except:
                pass


    for i in range(len(fish)):
        for j in range(len(fish[i])):
            fish[i][j] += temp[i][j]

    # 일렬 배치
    new_fish = []
    for j in range(len(fish[1])):
        new_fish.append(len(fish))
    for i in range(len(fish[0])-len(fish[1])):
        new_fish.append(1)

    temp = []
    for i in range(len(new_fish)):
        for j in range(new_fish[i]):
            temp.append(fish[j][i])
    fish = temp


    # 1번 접기
    floor1 = fish[N//2:]
    new_fish = [floor1]
    temp = []

    for i in range(N//2):
        temp.append(fish[N//2-i-1])
    new_fish.append(temp)
    fish = new_fish

    # 2번 접기
    new_fish = [fish[0][N//4:], fish[1][N//4:], list(reversed(fish[1][:N//4])), list(reversed(fish[0][:N//4]))]
    fish = new_fish
    # 다시 물고기 조절 작업
    # 어항 속 물고기수 조절하기, 각 어항에서 2방향만 확인

    temp = [[] for i in range(len(fish))]
    for i in range(len(fish)):
        for j in range(len(fish[i])):
            temp[i].append(0)

    for i in range(len(fish)):
        for j, v in enumerate(fish[i]):
            #오른쪽 확인
            try:
                if fish[i][j] > fish[i][j+1]:
                    d = (fish[i][j] - fish[i][j + 1]) // 5
                    temp[i][j] -= d
                    temp[i][j+1] += d
                else:
                    d = (fish[i][j+1] - fish[i][j]) // 5
                    temp[i][j] += d
                    temp[i][j + 1] -= d
            except:
                pass

            #위쪽 확인
            try:
                if fish[i][j] > fish[i+1][j]:
                    d = (fish[i][j] - fish[i+1][j]) // 5
                    temp[i][j] -= d
                    temp[i+1][j] += d
                else:
                    d = (fish[i+1][j] - fish[i][j]) // 5
                    temp[i][j] += d
                    temp[i+1][j] -= d
            except:
                pass

    for i in range(len(fish)):
        for j in range(len(fish[i])):
            fish[i][j] += temp[i][j]

    # 다시 펼치기
    new_fish = []
    for j in range(len(fish[1])):
        new_fish.append(len(fish))
    for i in range(len(fish[0])-len(fish[1])):
        new_fish.append(1)

    temp = []
    for i in range(len(new_fish)):
        for j in range(new_fish[i]):
            temp.append(fish[j][i])
    fish = temp

    # 가장 많이 들어있는 어항, 가장 적게 들어 있는 어항의 물고기 수 차이
    a = min(fish)
    b = max(fish)
    k = max(fish)-min(fish)
    return k, fish

# 메인 함수
count = 1
while True:
    a, fish = fish_shuffle(fish, N)
    if a<=K:
        break
    else:
        count+=1
print(count)