12) 구현

피지컬로 승부하기

• 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'을 의미하며, 개발할 때 프로그래밍 언어 문법에 능숙하고 타자가 빠른 사람을 보고 '피지컬이 좋다'라고 이야기 한다.
• 구현 문제는 그러한 '피지컬을 요구하는' 문제이며, 완전탐색과 시뮬레이션 유형이 구현 유형에 해당한다.

방향 벡터 (in 2차원 공간)

x: 행 만큼(세로 크기) / y: 열 만큼(가로 크기)
*내 기존 생각과 반대 -> (x,y)로 쓰자 / 위로 가면 (-1,0)이고 아래면 (1,0)임을 기억하자 *

# 동,북,서,남
dx = [0,-1,0,1]
dy = [1,0,-1,0]

# 현재 위치
x,y = 2,2

# 다음 위치
for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    print(nx,ny)

 

ex) 상하좌우

→ 상하좌우 탐색 시 dx,dy배열을 만들어주고 탐색해보자.

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

# 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)

 

ex) 시각

→ in, not in 연산자의 결과는 bool 타입 (해당 데이터 존재 유무)  

다음 코드는 매 시각을 문자열로 바꾼 다음(03시 25분 35초 → '032535') 문자열에 '3'이 포함됐는지 검사한다.

n = int(input())
cnt = 0

for i in range(n+1): #2시->0~2
  for j in range(60): #0~59
    for k in range(60):
      if '3' in str(i)+str(j)+str(k):
        cnt+=1

print(cnt)

 

ex) 문자열 재정렬

• isalpha(): 문자열에 숫자/공백이 포함되어 있으면 False를 리턴함 (주의하자!)
• isdigit(): 문자열의 구성이 모두 숫자인지 확인 (마찬가지로 문자/공백이 포함되면 False)
• join함수: 매개변수로 들어온 리스트의 요소 하나하나를 합쳐서 하나의 문자열로 바꾸어 반환 
  • ''.join(리스트): ''.join(['a','b','c']) → 'abc'
  • '구분자'.join(리스트): '_'.join(['a','b','c']) → 'a_b_c'

data = input() #알파벳+숫자 문자열
result = []
value = 0

#문자열/숫자인지 어떻게 판별?
for x in data:
  #알파벳이면 별도의 리스트에 저장
  if x.isalpha():
    result.append(x)
  #숫자면 따로 합계 계산
  else:
    value += int(x) #문자로 받아와서 int로 변환

#리스트 오름차순 정렬
result.sort()

#숫자가 하나라도 존재하면 가장 뒤에 삽입
if value != 0:
  result.append(str(value)) #삽입시에는 str로 변환

print(''.join(result))

 

---

#1 왕실의 나이트

입력: 8x8 좌표에서 현재 나이트가 위치한 곳의 좌표

출력: 나이트가 이동할 수 있는 경우의 수

• ord(문자): 하나의 문자를 인자로 받고, 문자에 해당하는 유니코드 정수 반환 ex) ord('a') = 97
• chr(정수): 하나의 정수를 인자로 받고, 정수에 해당하는 유니코드 문자 반환 ex) chr(97) = 'a'

data = input() #a1,c3 (열행)
row = int(data[1])
column = int(ord(data[0])) - int(ord('a'))
# 이동할 수 있는 8개 방향 정의
steps= [(-2,-1),(-1,-2),(-1,2),(-2,1),(1,2),(2,1),(1,-2),(2,-1)]

result=0
for step in steps:
  next_row = steps[0]
  next_column = steps[1]

  if 1<=next_row<=8 and 1<=next_column<=8:
    result+=1

print(result)

 

#2 게임 개발 ⭐⭐⭐(어려움)

문제 정리

• 1. 현재 위치,방향 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
• 2. 바로 왼쪽 방향에 대해 조건문 처리
  • 왼쪽 방향에 가보지 않은 칸이 존재하면, 왼쪽으로 회전한 다음 한 칸을 전진
  • 왼쪽 방향에 가보지 않은 칸이 없으면, 왼쪽으로 회전만 하고 1단계로 돌아감.
• 3. 만약 네 방향 모두 가본 칸이거나 바다이면, 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아감.
  • 단, 뒤쪽 방향이 바다여서 뒤로 갈 수 없는 경우는 움직임을 멈춘다.

중요 테크닉: 방향 문제는 dx,dy의 리스트를 만드는 것이 효과적이다.

N,M = int(input().split()) #세로x가로
A,B,d = int(input().split()) #현재:(A,B), 방향:d
map = [list(map(int,input().split())) for _ in range(N)]