이것이 코딩테스트다 Chapter 4 구현

4-1) 상하좌우

난이도 1 / 풀이시간 15분 / 시간제한 1초 / 메모리 제한 128 MB

 

나의 풀이)

 

- 처음에는 맵 이중 배열을 선언했다가 막상 작성하다보니 필요 없다는 것을 깨달았다. (언제 맵이 필요하고, 언제 맵이 필요하지 않는지 정리해보아야겠다.)

- 이동 횟수가 최대 100 이기 때문에 이 풀이는 최대 O(100)의 시간 복잡도를 가진다.

( Python은 1초에 최대 2000만번의 연산이 가능하다고 한다.  시간제한이 1초이고, 데이터의 개수가 100만개인 문제가 있다면 O(NlogN)이내에 알고리즘을 풀어야한다.) 

num = int(input())
route = list(input().split())

px=0
py=0

for d in route :
  if d == 'R' :
    if py+1 < num :
      py = py+1
  elif d == 'L' :
    if py-1 > -1 :
      py = py-1
  elif d == 'U' :
    if px-1  > -1 :
      px = px-1
  else :
    if px+1 < num :
      px = px+1

print(px+1, py+1)

 

이렇게 개체를 차례대로 이동시키는 문제를 시뮬레이션 유형이라고 한다고 한다. 

 

모범 답안)

n = int(input())
plans = input().split()

dx = [0,0,-1,1]
dy = [1,-1,0,0]

move_types = ['R','L','U','D']
px, py = 1,1

for i in plans :
  for j in range(len(move_types)) :
    if i == move_types[j] :
      nx = px + dx[j]
      ny = py + dy[j]
  if nx < 1 or ny < 1 or nx > n or ny > n :
    continue 
  else :
    px, py = nx, ny

print(px, py)

- 개체를 이동시키는 문제에서 위와 같이 dx, dy에 이동량을 세팅해놓고 인덱스에 맞춰서 이동시키는 방식에 대해서 기억해두면 좋을 것 같다.

- 시작점을 0,0이 아니라 1,1로 세팅해두면 코딩할 때 헷갈리지 않아서 좋을 것 같다.

 

참고로 이 문제랑 큰 연관은 없지만,,,

맵 이차원 배열을 선언하려고 하면서 알아본 이차원 배열 선언법에 대해서 정리해보겠다.

 

# 1. for문을 사용한 리스트 컴프리헨션

array =[[0] * m for _ in range(n)]

>>>> 동일한 목록의 사본 5개이기 때문에 하나를 수정하면 모두 변경되는 문제점이 있음

>>>>>> array[4,4] = 2

>>>>>>[[0,0,0,0,2],[0,0,0,0,2],[0,0,0,0,2],[0,0,0,0,2]]

>>>>>> array = [[0 for _ in range(5)] for _ in range(5)] 로 수정 필요.

Q. 이중 for문 만큼 메모리를 사용할까?

 

#2. numpy 행렬연산 사용

numpy.zeros((m,n))) >>> m*n의 0으로 초기화및 생성 가능

 

#3. 초기화 없이 선언만 한다면 matrix = [[]]

 

4-2 ) 시각

난이도 1 / 풀이시간 15분 / 시간 제한 2초 / 메모리제한 128 MB

 

# 4-2 시각
h = int(input())
count = 0
for i in range(h+1) :
  for j in range(60) :
    for k in range(60) :
      if '3' in str(i) + str(j) + str(k) :
        count += 1
print(count)

 

하루는 86,000 초이기 때문에 무식하게 완전 탐색을 한다고 했을 때 탐색해야 할 최대 데이터 수는 86000개이다. 이와 같이 탐색해야 할 전체 데이터 수가 100만개 이하일 때는 완전탐색을 해도 무방하다.

 

4-3) 왕실의 나이트

#4-3 왕실의 나이트
N = input()

dx = [-2,-2,2,2,-1,1,-1,1]
dy = [-1,1,-1,1,2,2,-2,-2]
count = 0
px = int(N[1:2])

map = ['a','b','c','d','e','f','g','h']
for i in range(len(map)) :
  if map[i] == N[0:1] :
    py = i+1

for i in range(8) :
  nx = px + dx[i]
  ny = py + dy[i]

  if nx < 1 or nx > 8 or ny < 1 or ny > 8 :
    continue
  else :
    count += 1
    
print(count)

#4-3
N = input()
row = int(N[1])
col = ord(N[0]) - ord('a') + 1

steps = [(-2,-1),(-2,1),(2,-1),(2,1),(-1,2),(1,2),(-1,-2),(1,-2)]
count = 0

for step in steps :
  nx = row + step[0]
  ny = col + step[1]
  if nx < 1 or nx > 8 or ny < 1 or ny > 8 :
    continue
  else :
    count += 1 

print(count)

- 위치가 숫자가 아니라 문자열로 주어질 때 : 슬라이싱을 통해서 문자열을 분리할 수 있다.

- 나는 배열을 만들어놓고 해당 문자의 인덱스를 가져오는 방식으로 문제를 풀었는데, 모범 답안에서는 아스키코드 값을 사용하여 숫자로 변환해주었다.

- 이동 방향을 세팅할 때, dx,dy 방식도 있지만 모범답안처럼 튜플형식으로 한 리스트에 지정하여 사용하는 방법도 있다!

 

#4-4 게임 개발

난이도 2 / 풀이시간 40분 / 시간제한 1초 / 메모리 제한 128MB

#4-4 게임 개발
n, m = map(int, input().split())
x, y, d = map(int, input().split())
maps = []
for _ in range(n) :
  maps.append(list(map(int, input().split())))

dx=[-1,0,1,0]
dy=[0,-1,0,1]
count = 1

maps[x][y] = 2
turn_time = 0

def turn_left() :
  global d
  d += 1
  if d == 4 :
    d = 0

while True :
  turn_left()
  nx = x + dx[d]
  ny = y + dy[d] 
  
  if maps[nx][ny] == 0 :
    x, y = nx, ny
    count += 1
    turn_time = 0
    maps[nx][ny] = 2
  else :
    turn_time +=1

  if turn_time == 4 :
    nx = x - dx[d]
    ny = y - dy[d]
    if maps[nx][ny] == 1 :
      break
    else :
      x, y = nx, ny
    turn_time = 0

print(count)

- 전역변수를 사용하는 예제

- 포기하지 말고 가능한 케이스를 모두 생각해보자