[15회차] 빛의 경로 사이클, 가장 큰 수

Programmers Level.2 빛의 경로 사이클

def move(direction, state): # 다음에 이동할 방향을 반환하는 함수
    n_direction = [] # direction : 이동하고 있는 방향. state : 도착 지점의 상태.
    if state == 'S':
        n_direction = direction
    if state == 'R':
        if direction == [-1, 0]:
            n_direction = [0, 1]
        elif direction == [1, 0]:
            n_direction = [0, -1]
        elif direction == [0, 1]:
            n_direction = [1, 0]
        elif direction == [0, -1]:
            n_direction = [-1, 0]
    if state == 'L':
        if direction == [-1, 0]:
            n_direction = [0, -1]
        elif direction == [1, 0]:
            n_direction = [0, 1]
        elif direction == [0, 1]:
            n_direction = [-1, 0]
        elif direction == [0, -1]:
            n_direction = [1, 0]
    return n_direction


def solution(grid):
    answer = []
    visited = [[[0, 0, 0, 0] for m in range(len(grid[0]))] for _ in range(len(grid))]
    way = [[-1, 0], [1, 0], [0, 1], [0, -1]]  # U, D, R, L 방향
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for k in range(4):
                if visited[i][j][k] != 0: # 이미 방문한 지점이라면 패스
                    continue
                x = i
                y = j
                d = k
                visited[x][y][d] = 1
                while True:
                    nd = way.index(move(way[d], grid[x][y]))
                    nx = (x + way[nd][0]) % len(grid) # 격자 밖으로 벗어날 때 고려하기
                    ny = (y + way[nd][1]) % len(grid[0])
                    if visited[nx][ny][nd] == 0:
                        visited[nx][ny][nd] = visited[x][y][d] + 1
                    else:
                        answer.append(visited[x][y][d])
                        break
                    x = nx
                    y = ny
                    d = nd
    answer = sorted(answer) # 오름차순 정리
    return answer

- 격자 밖으로 벗어나면 안되는 다른 문제들과 다르게 격자를 벗어나면 반대쪽 끝으로 돌아온다는 조건이 있었다. 이 조건에 따라 이동하면 결국에는 사이클이 생긴다는 것을 암시한다.

 - 이동하는 것을 구현하려면 '직전에 상하좌우 중 어떤 방향으로 이동했는 지'와 '지금 도착한 지점이 S, L, R 중 어떤 것인지' 두 가지 조건이 필요했고 이를 이용해 move 함수를 만들었다.

 - 이미 방문한 지점은 패스하고 사이클을 이룰 때마다 answer에 추가시키고 오름차순으로 리턴해주면 정답.

 

 

Programmers Level.2 가장 큰 수

def solution(numbers):
    numbers = list(map(str, numbers))
    dicts = dict()
    while numbers:
        number = numbers.pop()
        n_number = number
        if len(number) < 4:
            a = 4 - len(number)
            n_number = number + a * number[0]
        if n_number not in dicts:
            dicts[n_number] = [number]
        else:
            dicts[n_number].append(number)
            dicts[n_number] = sorted(dicts[n_number])
    dicts = sorted(dicts.items(), reverse=True)
    answer = ''
    for i in dicts:
        answer += ''.join(i[1])
    return answer

 - 틀렸다.

 - 내가 생각한 아이디어를 말하자면,

 - 주어진 수 중 앞 자리 숫자가 큰 수 부터 붙여 나가면 된다.

 - 앞 자리 수가 같지만 전체 자리 수가 다를 경우에는 우선 순위를 어떻게 줘야 하는지 고민했다. 예를 들어 5,52,59,591,596은 596>59>591>5>52 순으로 붙여야 한다. 이를 구현하기 위해 각 숫자의 뒤에 맨 앞자리 수를 이어서 붙였다. 5면 5555, 52는 5255, 59는 5955, 591은 5915, 596은 5965로 만들고 큰 수 부터 나열하면 된다고 생각했다.

 - 57, 575는 모두 5755라는 숫자가 만들어지므로 이들 사이의 우열 관계를 만들기 위해 dicts에 원소를 추가할 때 정렬하는 과정을 넣어줬다. dicts[5755] = [57, 575]이고 57575 > 57557이므로 맞다고 생각했다.(결과적으로 틀린 아이디어)

 - 구현 방식에 문제가 있는건지, 테스트 케이스에서 절반 이상을 틀렸다.

 

 - 결국 구글의 힘을 빌려서 답을 확인해봤다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x * 3, reverse=True)
    return str(int(''.join(numbers)))

 - 문자열에는 숫자를 앞 자리부터 뒷 자리까지 순서대로 비교한다.

 - 전체 자리 수가 다를 경우를 비교하기 위해 문자열 x를 3배 해준 후 비교했다. ( 어떻게 이런 아이디어를 떠올릴 수 있었는지 놀라울 따름이다... )

 

 - 내 아이디어(맨 앞자리 수를 뒤에 이어 붙인다.)가 안되는 이유를 알기 위해 반례를 찾아야 했다.

 - 52와 525의 경우 내 아이디어에 의하면 dicts[5255] = [52, 525]가 되어 52525로 문자열이 생성되는데, 52552라는 더 큰 수가 존재하므로 내 아이디어는 틀렸다.