[이것이 코딩 테스트다] 구현 - 시뮬레이션과 완전 탐색

 

 

구현문제

- 구현문제

: 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정

: 풀이를 떠오르는 것은 쉽지만, 소스코드로 옮기기 어려운 문제

 

- 문제 유형

: 실수 연산, 특정 소수점 출력 문제

: 코드가 길어지는 문제

: 문자열 끊어서 처리하는 문제

: 라이브러리 찾아서 사용해야 하는 문제

 

 

 

상하좌우 문제

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1, 1) 이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1) 입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다.

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있습니다. 각 문자의 의미는 다음과 같습니다.
- L : 왼쪽으로 한 칸 이동
- R : 오른쪽으로 한 칸 이동
- U : 위로 한 칸 이동
- D : 아래로 한 칸 이동

이 때 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시됩니다.

[아이디어]

- 2차원 공간(행렬) 이용

- 시뮬레이션 및 완전 탐색 문제에서의 2차원 공간 → 방향 벡터 사용

 

[코드]

• 내 코드

import sys
input = sys.stdin.readline

N = int(input())  # 정사각형 공간 크기 입력받기
move = input().rstrip()  # 이동방향 입력받기

x, y = 1, 1  # 시작좌표

for i in range(0, len(move)):  # 이동방향 반복문으로 하나씩 확인
  if move[i] == "L":
    if y == 1:  # 정사각형 공간 벗어날 경우
      continue
    else:
      y -= 1
  elif move[i] == "R":
    if y == N:  # 정사각형 공간 벗어날 경우
      continue
    else:
      y += 1
  elif move[i] == "U":
    if x == 1:  # 정사각형 공간 벗어날 경우
      continue
    else:
      x -= 1
  else:
    if x == N:  # 정사각형 공간 벗어날 경우
      continue
    else:
      x += 1

print(f"{x} {y}")  # 최종 좌표 f-string으로 출력

 

• 답안

n = int(input())  # n 입력받기
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)

- 방향 벡터를 이렇게 사용한다는 것을 처음 알게 되었다.

- 공간을 벗어나는 경우에 대해서 한 번에 처리하니까 코드량이 확실히 줄어드는 것도 확인할 수 있었다.

 

 

 

시각 문제

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요.

- 가능한 경우의 수 모두 검색 = 완전탐색 유형

 

[코드]

import sys
input = sys.stdin.readline

N = int(input())  # 시(몇시인지) 입력 받기
count = 0  # 3이 포함되는 갯수

for i in range(N+1):  # 시 (0~N)
  for j in range(60):  # 분 (0~59)
    for k in range(60):  # 초 (0~59)
      # 시분초를 문자열로 다 나열하고 → 3이 있다면 count 1씩 증가
      if '3' in str(i) + str(j) + str(k):
        count += 1
        
print(count)

- for문 3개를 써야 한다는 것까지는 생각했으나, 3을 확인하는 방법에 대해서 아이디어를 떠올리지 못했다.

 

 

 

왕실의 나이트

행복 왕국의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면입니다. 왕실 정원의 특정한 한 칸에 나이트가 서있습니다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마합니다.
나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없습니다.

나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있습니다.
1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

이처럼 8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하세요. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현합니다.

[아이디어]

- 2차원 공간(행렬) 이용

- 시뮬레이션 및 완전 탐색 문제에서의 2차원 공간 → 방향 벡터 사용

 

[코드]

input_data = input()  # 나이트의 현위치 입력받기

row = int(input_data[1])
# ord()함수를 통해 아스키코드를 숫자로 변경하여 알파벳이 아닌 숫자로 접근
column = int(ord(input_data[0])) - int(ord('a')) + 1 

# 이동할 수 있는 8가지 방향 리스트로 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

result = 0

for step in steps:  # 8가지 방향에 대해서 이동할 수 있는지 여부 확인
  next_row = row + step[0]
  newt_column = column + step[1]
  
  # 해당 위치로 이동이 가능하다면 result 1씩 증가
  if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
    result += 1
    
print(result)

- 알파벳에 대해서 아스키코드로 접근해서 풀면 된다는 것을 알게 되었다.

- 구현 첫 번째 문제인 '상하좌우 문제'와 어느 정도 비슷한 형태라는 것을 느꼈다.

 

 

 

문자열 재정렬

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.

[코드]

• 내 코드

import sys
input = sys.stdin.readline

words = input().rstrip()  # 알파벳+숫자로 구성된 문자열 입력받기

eng = []  # 문자(알파벳)만 모아둘 리스트 선언
num = []  # 숫자만 모아둘 리스트 선언

# 알파벳 대문자(A~Z)
alpha = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

for i in range(len(words)):  # 입력받은 문자열 하나씩 확인하기
  if words[i] in alpha:
    eng.append(words[i])
  else:
    num.append(int(words[i]))

# eng와 num을 오름차순으로 정렬
eng.sort()
num.sort()

# 리스트 형태를 join()으로 문자열로 변환, 리스트 num의 총합을 sum()으로 구하여 출력
print(f"{''.join(eng)}{sum(num)}")

• 답안

data = input()  # 문자열 입력받기
result = []  # 결과 저장할 리스트
value = 0  # 숫자들의 총합

for x in data:  # 문자를 하나씩 확인
  if x.isalpha():  # 알파벳인 경우 결과 리스트에 삽입
    result.append(x)
  else:  # 숫자는 따로 더하기
    value += int(x)
    
result.sort()  # 알파벳을 오름차순으로 정렬

if value != 0:  # 숫자가 하나라도 있을 경우, result의 가장 뒤에 삽입
  result.append(str(value))
  
  print(''.join(result))  # 최종 결과 출력

- .isalpha() 함수가 있는지 몰랐었다. 앞으로 알파벳/숫자 확인하는 과정에서 유용하게 활용할 수 있을 것 같다.