[이것이 코딩테스트다] 구현

1. 구현

구현 문제 : 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

                  ex) 코드가 길어지는 문제, 특정 소수점까지 출력하는 문제, 문자열이 입력으로 주어졌을 때 파싱해야하는 문제 등

                -> 문법적인 문제나 라이브러리 사용 경험이 부족하다면 어려운 문제들

 

나처럼 알고리즘 문제 풀이 경험이 적은 사람이 전형적으로 어려워하는 문제들이다....

 

2. 실습

   2.1 상하좌우

나의코드

n = int(input())
plan = list(input().split())

row=[0,0,-1,1]
col=[-1,1,0,0]

x,y=1,1

for p in plan:
  if p == 'L':
    if 1<= x + row[0] <= n:
      x = x + row[0]
 
  elif p == 'R':
    if 1<= x + row[1] <= n:
      x = x + row[1]
  
  elif p == 'U':
    if 1<= y + col[2] <= n:
      y = y + col[2]
      
  elif p=='D':
    if 1<= y + col[3] <= n:
      y = y + col[3]
  
print(x,y)

row, col 리스트에 방향에 대한 x,y의 변화량을 미리 저장하고 이를 호출, 하지만 해당 문제에서는 굳이 그렇게 하지 않아도...?

 

정답 코드

n= int(input())
x,y = 1, 1
plans = input().split()

dx=[0,0,-1,1]
dy=[-1,1,0,0]
move_type=['L','R','U','D']

for plan in plans:
    for i in range(len(move_type)):
        if plan == move_type[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    if nx<1 or ny<1 or nx>n or nx>n:
        continue

    x, y = nx, ny

print(x, y)

dx,dy를 리스트로 저장하고 이를 move_type 리스트와 연결지어서 찾아 직관적으로 표현이 가능!

 

   2.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)

3을 문자로 바꿔 숫자간의 비교가 아니라 해당 문자열 안에 문자가 존재하는지의 문제로 바꿔 해결

-> 코드가 더욱 간격해지고 직관적으로 이해 가능.

 

   2.3 왕실의 나이트

나의코드

data=input()
col=['a','b','c','d','e','f','g','h']
plans=[(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]

# input 좌표 구하기
for i in range(len(col)):
  if data[0]==col[i]:
    x=i+1
y=int(data[1])

# 가능한 방향의 개수 구하기
count=0
for p in plans:
  nx= x + p[0]
  ny = y + p[1]

  if 0 < nx < 9 and 0 < ny < 9:
    count+=1

print(count)

col의 문자를 for문을 돌려 숫자로 대입 -> 비효율적인 연산 증가

 

정답코드

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0]))- int(ord('a')) +1

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

count=0
for step in steps:
  nx= row + step[0]
  ny = column + step[1]

  if 0 < row < 9 and 0 < column < 9:
    count+=1

print(count)

ord()를 사용하여 문자를 숫자로 바로 바꿈

 

ord(char) : 문자의 유니코드 값을 돌려주는 함수

chr(num) : 해당 유니코드에 해당하는 문자 반환  

   2.3 게임 개발

나의 코드

c,r=map(int,input().split())
x,y,watch=map(int,input().split())
gamepad=[]
for i in range(c):
  arr=list(map(int,input().split()))
  gamepad.append(arr)

count=0
watch_count=0
direct=[0,1,2,3] #북/동/남/서

col=[-1,0,1,0]
row=[0,1,0,-1]

gamepad[x][y]-=1
while True:
  # 모든 4방향 확인
  while watch_count<=3:
    watch=direct[watch%4]
    dx = x + row[watch]
    dy = y + col[watch]
    # 육지라면 이동
    if 0<=dx<r and 0<=dy<c and gamepad[dx][dy] == 0:
      x=dx
      y=dy
      gamepad[x][y]-=1
      watch_count=0
      count+=1 
      break 
    watch-=1
    watch_count+=1

  dx=x-row[watch]
  dy=y-col[watch]
  # 뒤로로 이동이 가능한지 확인
  if r<=dx or dx<0 or dy<0 or dy>=c or gamepad[dx][dy]==1:
    break
  else:
    x=dx
    y=dy

print(count)

for문을 통해 4가지 방향이 모두 가능한지 확인, 나머지 연산을 통해 방향을 구함.

 

정답코드

n, m = map(int,input().split())

#방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0]*m for _ in range(n)]

x,y,direction=map(int,input().split())
d[x][y] = 1

# 전체 맵 정보 입력받기
array = []
for i in range(n):
    array.append(map(int,input().split()))

# 북, 동, 남, 서 방향 정의
dx = [0,1,0,1]
dy = [-1,0,1,0]

# 왼쪽으로 회전
def turn_left():
    global direction
    direction -=1
    if direction == -1:
        direction = 3

# 시뮬레이션 시작
count = 1
turn_time = 0 
while True:
    # 왼쪽으로 회전
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]

    # 정면에 가보지 않은 칸이면 이동
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    # 바다인 경우
    else:
        turn_time +=1

    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        if array[nx][ny] == 0:
            x = nx
            y = ny
        # 뒤가 바다인 경우
        else:
            break
        turn_time = 0

print(count)

정말 전형적인 시뮬레이션 구현 문제였습니다. 알고리즘 문제 느낌이라기보다는 프로그램을 작성해보시오. 이런 느낌의 문제였습니다.