2019년 프로그래머스 동계 인턴쉽 코딩테스트. 총 3문제로 난이도는 3번을 제외하고 무난했고, 무엇보다 문제 자체가 정말 재미있었어서 정리. 문제들은 프로그래머스 웹사이트에 공개 되어있다.
문제 풀 수 있는 곳 - 클릭
멀쩡한 사각형
문제 설명
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
제한 사항
W, H : 1억 이하의 자연수
입출력 예
W H result 8 12 80 풀이
처음 몇분동안은 노가다로 규칙을 구해보려다 답답해서 구글링을 해보니 생각보다 쉽게 공식을 찾을 수 있었다. 이 블로그를 참고했다. 대각선에 의해 잘려지는 사각형의 개수는 대각선과 만나는 격자점의 개수와 관련이 있고, 공식에 따르면 (가로) + (세로) - (가로 세로 최대 공약수) 개의 사각형이 대각선 아래에 놓이게 된다. 요 공식 덕분에 빠르게 접근할 수 있었다. 유클리드 호제법으로 공약수 구하는 건 유명하니, 금방 짤 수 있다.
코드
1 2 3 4 5 6 7 8 9 10
def gcd(x, y): if y == 0: return x return gcd (y, x%y) def solution(w,h): if w < h: w, h = h, w return (w*h) - (w+h-gcd(w, h))
종이 접기
문제 설명
직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다.
![image]()
먼저 오른쪽 절반을 왼쪽으로 접습니다.
![image]()
다시 오른쪽 절반을 왼쪽으로 접습니다.
![image]()
종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 아래 그림과 같이 종이에 접은 흔적이 생기게 됩니다.
![image]()
위 그림에서 ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다.
종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 종이를 접는 횟수 n은 1 이상 20 이하의 자연수입니다.
- 종이를 접었다 편 후 생긴 굴곡이 ∨ 모양이면 0, ∧ 모양이면 1로 나타냅니다
- 가장 왼쪽의 굴곡 모양부터 순서대로 배열에 담아 return 해주세요.
입출력 예
n result 1 [0] 2 [0,0,1] 3 [0,0,1,0,0,1,1] 풀이
이것 역시 구글링을 통해 힌트를 얻었다. 이 사이트 를 참고했다. 잘 보면 처음 접은 가운데 ‘0’ 을 기준으로 양쪽이 대칭이다. 예컨대 n이 3일 때를 보면, 가운데 ‘0’을 기준으로 오른쪽 세개의 굴곡 ‘0 0 1’에서 0은 1로 1은 0으로 뒤바꾼 후 순서를 거꾸로 배열하면 ‘ 0 1 1’이 된다. 처음 접은 굴곡인 0을 기준으로 그 다음 접을 때부터는 완전히 대칭으로 굴곡이 생겨나며, 이렇게 함께 접힌 굴곡은 한쪽이 0이면 다른 한쪽은 1일 수밖에 없어서 그렇다. n이 2일 때 어떻게 양쪽에 0과 1이 추가되었는 지 생각해보고, 이후 n이 하나씩 늘어날수록 Top-down 재귀처럼 똑같은 일이 반복됨을 알 수 있다. 그러므로 가운데 0을 기준으로 왼쪽이나 오른쪽 중 한 쪽의 굴곡들만 파악하면 된다.
그런데 한쪽의 굴곡은 어떻게 파악해야 할까? 놀랍게도 n-1의 결과가 n의 왼쪽 굴곡이 된다 (n=2일 때의 결과가 n=3의 왼편 굴곡과 같음). 다 구했다. 이제 코딩만 하면 된다. 마침 0과 1이니 비트 연산자를 사용했다.
개인적으로 이 문제는 풀면서도 진짜 재미있었다. 종이 접기에 이런 규칙이…!코드
1 2 3 4 5
def solution(n): l_side = [0] for _ in range(n-1): l_side = l_side + [0] + [ele^1 for ele in reversed(l_side)] return l_side
원래는 이것보다 2 ~3 줄 더 길었는데 다른 분들 풀이를 보고 불필요한 부분을 줄였다.
추가 궁금증
처음 제출을 했을 때 테스트 케이스 중 유독 시간이 오래 걸리는 게 몇개 있었다. 왜 오래 걸리지 싶어 살펴보다가, 리스트를 뒤집을 때 reversed() 함수를 사용하니 시간이 확 단축 된다는 것을 발견했다 (처음 제출할 땐 reversed 대신 [::-1] 로 뒤집었기 때문에 오래 걸렸다).
실제로 시간을 재어보니,
1 2 3 4 5 6 7 8 9 10 11 12
import time lst = [n for n in range(10000)] start1 = time.time() lst = lst[::-1] t1 = time.time() - start1 print('t1 = ', t1*10000) start2 = time.time() lst = reversed(lst) t2 = time.time() - start2 print('t2 = ', t2*10000)
1 2
t1 = 1.373291015625 t2 = 0.021457672119140625
reversed() 가 [::-1] 보다 훨씬 빠르다. 왜지…?
지형 이동
문제 설명
N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.
이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.
각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.
제한 사항
- land는 N x N크기인 2차원 배열입니다.
- land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
- land의 원소는 각 격자 칸의 높이를 나타냅니다.
- 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
- height는 1 이상 10,000 이하인 자연수입니다.
입출력 예
land height result [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 풀이
마지막 문제… 좀 어렵다. BFS나 DFS로 사다리 없이 이동 가능한 그룹들을 나눠야 한다는 것까지는 알겠는데 그 이후가 문제였다. 그룹을 나눈 뒤 최소 비용을 어떻게 구하나- 다익스트라? 재귀? 갈피를 못 잡다가 테스트 시간이 얼마 안 남아서 일단 그룹 나누기에 착수했다. BFS를 사용했고 노드 클래스를 만들어 해당 칸의 높이와 속해있는 그룹을 식별할 번호를 부여했다. 아직 아무데에도 속하지 않은(그룹 번호가 0) 노드들에 대해 bfs를 돌려 그룹까지는 잘 구분한 것 같았다. 이제 각 그룹 간 이동가능한 최소 사다리 높이를 구해놓고 그 높이들을 잘 조합하여 전체 최소 비용을 구하면 된다고 생각하고 몇 줄 적기 시작했는데 테스트 시간이 끝났다. 그리고 몇 주 후 이 사이트 에서 공식 해법을 공개했다. 최소 사다리 높이를 조합할 방법을 찾지 못했었는데 최소 신장 트리(Minimum Spanning Tree) 를 쓰면 된다고 한다. 근데 정작 풀이 코드는 주지 않아서 일단 시키는대로 한번 짜보았다. 나눈 그룹 번호를 참고하여 각 그룹별 생성 가능한 간선들을 생성한 뒤, 최소 신장 트리 중에서도 크루스칼 알고리즘을 구현하였다. Union, FindSet과 같은 기본 기능을 구현한 후 수도 코드 그대로 따라 작성하였다. 자세한 건 이 블로그 를 참고하였다. 이렇게 했는데 30개 중 마지막 테스트 케이스 10개에서 시간 초과가 떴다. 20개라도 통과한 걸 위안 삼으며 어떻게 시간초과를 해결할 지 고민해야겠다.
코드(더러움 주의)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
from collections import deque class Node(): def __init__(self, h): self.h = h self.group = 0 def bfs(land, x, y, height, group_num): group_lst = [] n = len(land) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] que = deque() que.append((x, y)) while (que): x, y = que.popleft() group_lst.append(land[x][y].h) land[x][y].group = group_num for i in range(4): next_x, next_y = x + dx[i], y + dy[i] if 0 <= next_x < n and 0 <= next_y < n: diff = abs(land[next_x][next_y].h - land[x][y].h) if land[next_x][next_y].group == 0 and diff <= height: que.append((next_x, next_y)) return land, group_lst def findRoot(x, parent): if x == parent[x]: return x return findRoot(parent[x], parent) def union(x, y, parent, level): x = findRoot(x, parent) y = findRoot(y, parent) if x == y: return if level[x] > level[y]: x, y = y, x #항상 x가 더 작은 트리가 되도록 설정 parent[x] = y if level[x] == level[y]: level[x] += 1 #깊이가 같을 경우 x의 level을 늘려준다. def MST_kruskal(edges, group_cnt): # SORTED edges = (distance, (A, B)) parent = [i for i in range(0, group_cnt)] level = [1 for _ in range(0, group_cnt)] cost = 0 for edge, (a, b) in edges: if findRoot(a, parent) != findRoot(b, parent): cost += edge union(a, b, parent, level) return cost def solution(land, height): answer = 0 n = len(land) for row_idx, row in enumerate(land): land[row_idx] = list(map(Node, row)) # 1. Group movable stages group_cnt = 1 group_dict = [] for i in range(n): for j in range(n): if land[i][j].group == 0: land, temp = bfs(land, i, j, height, group_cnt) group_dict.append(temp) group_cnt += 1 # 2. Create edges dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] edges = [] # (distance, (A, B)) for x in range(n): for y in range(n): for i in range(4): next_x, next_y = x + dx[i], y + dy[i] if 0 <= next_x < n and 0 <= next_y < n: if land[next_x][next_y].group != land[x][y].group: diff = abs(land[next_x][next_y].h - land[x][y].h) a = land[x][y].group b = land[next_x][next_y].group if a > b: a, b = b, a edges.append((diff, (a, b))) # 3. MST algorithm if edges: edges = [ele for ele in set(edges)] edges = sorted(edges, key=lambda x: x[0]) return MST_kruskal(edges, group_cnt)
