알고리즘 - 구현

*참고 저서 <이것이 취업을 위한 코딩테스트다>

 

구현이라는 카테고리는 사실 기존의 알고리즘 커리큘럼에선 찾아보기 힘든 카테고리다.

모든 알고리즘이 특정 기능을 구현한다고 볼 수 있기 때문이다.

여기서 구현이란 좀 더 좁은 의미로,

'특정한 접근방법없이 요구사항을 한 줄씩 구현하면 되는 문제유형'이다.

굳이 이러한 특정을 하는 이유는 기업 코딩테스트에서 이러한 유형이 꾸준히 출제되고 있기 때문이다.

 

구현 문제는 특정 알고리즘에 대한 이해보다는 문제에 대한 독해력, 사용 언어에 대한 숙련도, 코드 작성 속도

등이 중요한 문제라고 볼 수 있다.

 

<예제>

여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나 누어져 있다. 가장 왼쪽 위 좌표는 (1, 1 )이며, 가장 오른쪽 아래 좌표는 (N, 비 에 해당한다. 여행 가 A는 상，하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행 가 A가 이동할 계획이 적힌 계획서가 놓여 있다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다.

• L ： 왼쪽으로 한 칸 이동

• R : 오 른 쪽 으 로 한 칸 이 동

• U ： 위 로 한 칸 이 동

• D ： 아 래 로 한 칸 이 동

이때 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1) 의 위치에서 L 혹은 U를 만나면 무시된다. 다음은 N = 5인 지도와 계획서이다. R - R - R - U — D — D  

이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1. 3 ), (1, 4 ), (1, 4 ), (2, 4 ), (3, 4 )이므로，최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4 )이다. 다 시 말해 3행 4열의 위치에 해당하므로 (3, 4 )라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종 적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

 

보이는 바와 같이 지문의 길이가 상당히 길며 요구사항이 단계별로 제시되는 문제가 많다.

앞서 말했 듯 별다른 접근방법은 업기에 정답 코드만 올리도록 하겠다.

 

# N을 입력받기
n = int(inputO) 
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향 
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0] 
move_types = ['L' , 'R' , 'U', 'D']

# 이동 계획을 하나씩 확인 
for plan in plans：
  # 이동 후 좌표 구하기
  for i in range(len(move_types))： 
    if plan == move_types[i]： 
      nx = x + dx[i] 
      ny = y + dy[i]
  # 공간을 벗어나는 경우 무시
  if nx < 1 or ny < 1 or nx > n or ny > n： 
	continue
  # 이동 수행
  x, y = nx, ny

print(x, y)