2019 프로그래머스 윈터 코딩 문제 풀이

2019년 프로그래머스 동계 인턴쉽 코딩테스트. 총 3문제로 난이도는 3번을 제외하고 무난했고, 무엇보다 문제 자체가 정말 재미있었어서 정리. 문제들은 프로그래머스 웹사이트에 공개 되어있다.

문제 풀 수 있는 곳 - 클릭

  1. 멀쩡한 사각형

    • 문제 설명

      가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

    • 제한 사항

      W, H : 1억 이하의 자연수

    • 입출력 예

      W H result
      8 12 80
    • 풀이

      처음 몇분동안은 노가다로 규칙을 구해보려다 답답해서 구글링을 해보니 생각보다 쉽게 공식을 찾을 수 있었다. 이 블로그를 참고했다. 대각선에 의해 잘려지는 사각형의 개수는 대각선과 만나는 격자점의 개수와 관련이 있고, 공식에 따르면 (가로) + (세로) - (가로 세로 최대 공약수) 개의 사각형이 대각선 아래에 놓이게 된다. 요 공식 덕분에 빠르게 접근할 수 있었다. 유클리드 호제법으로 공약수 구하는 건 유명하니, 금방 짤 수 있다.

    • 코드

      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))
      
  2. 종이 접기

    • 문제 설명

      직사각형 종이를 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이니 비트 연산자를 사용했다.
      개인적으로 이 문제는 풀면서도 진짜 재미있었다. 종이 접기에 이런 규칙이…!

    • 코드

      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] 로 뒤집었기 때문에 오래 걸렸다).

      실제로 시간을 재어보니,

      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)
      
      t1 =  1.373291015625
      t2 =  0.021457672119140625
      

      reversed() 가 [::-1] 보다 훨씬 빠르다. 왜지…?

  3. 지형 이동

    • 문제 설명

      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개라도 통과한 걸 위안 삼으며 어떻게 시간초과를 해결할 지 고민해야겠다.

    • 코드(더러움 주의)

      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)