구현 예제

ggulgood 2022. 4. 21. 22:37

구현 관련 코딩 테스트 예제이다.

예제 4-1. 상하좌우

입력 조건:
첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)
둘째 줄에 여행가 A가 이동할 계획서 내용이 주어딘다. (1 <= 이동 횟수 <= 100)

출력 조건:
첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

* 문제 해설

이동 횟수가 N번인 경우, 시간 복잡도는 O(N) 이다.

시뮬레이션 유형에 속한다.

이동할 계획서를 plans 로 입력 받았기 때문에

plans = input().split() # 이동할 계획서 입력

for문에서 for _ in range() 대신 for _ in plans 로 작성한다.

* 코드

n = int(input())
data = ['L', 'R', 'U', 'D'] # 상하좌우 이동 문자
x, y = 1, 1 # 초기 위치
plans = input().split() # 이동할 계획서 입력

dx = [0, 0, -1, 1] # 상하좌우 이동 시 y 고려
dy = [-1, 1, 0, 0] # 상하좌우 이동 시 x 고려

for plan in plans: # 이동 계획

    # 이동 후 좌표 구하기
    for i in range(len(data)):
        if plan == data[i]:
            nx = x + dx[i]
            ny = y + dy[i]
            
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    y = ny
    x = nx

print(x, y)

예제 4-2. 시각

00시 00분 00초부터 N시 59분 59초까지

예를 들어 1을 입력했을 때 : 1시 59분 59초까지

입력 조건:
첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)

출력 조건:
00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

* 문제 해설

완전 탐색 유형으로 분류된다.

매 시각을 문자열로 바꾼 다음에 문자열에 '3'이 포함됐는지 검사한다.

1초씩 늘리며 시, 분, 초를 문자열 자료형으로 변환하여 합친다.

예를 들어 03시 20분 35초일 때를 확인한다면, 이를 '032035'로 만들어 '3'이 포함되어 있는지를 체크하는 방식을 이용한다.

* 코드

n = int(input())  #0 <= N <= 23

count = 0
for i in range(n + 1):
    for j in range(60):
        for k in range(60):
            # 문자열로 만들어 매 시각 안에 '3'이 포함되어 있다면 카운트로 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

예제. 왕실의 나이트

8X8 좌표 평면상에서 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.

이 때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.

입력 조건:
첫째 줄에 8 X 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다.
입력 문자는 a1처럼 열과 행으로 이뤄진다.

출력 조건:
첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

* 문제 해설

열 문자열을 받는 부분이 잘 이해가 가지 않았다.

n_move = input() # 나이트의 좌표를 입력받음

column = int(ord(n_move[0])) - int(ord('a')) + 1 # 열 문자열
row = int(n_move[1]) # 행 문자열을 얻음, 배열의 두번 째 자리

깃헙 참조 https://github.com/ndb796/python-for-coding-test/issues/71

ord()는 하나의 문자에 대한 아스키 코드(ASCII Code) 정수 값을 반환한다.

열(column) 변수는 체스판의 가로축 인덱스를 의미한다.

가로축은 a부터 h까지 존재하므로, 인덱스값을 계산하기 위해 'a'의 아스키코드 값만큼 빼주게 된다.

다만 이 문제에서는 인덱스가 1부터 출발하므로 추가적으로 1을 더해준다.

상하좌우 문제에서는 dx, dy 리스트를 선언하여 이동할 방향을 기록할 수 있도록 하였으나

왕실의 나이트 예제에서는 steps 변수가 dx와 dy 변수의 기능을 대신하여 수행한다.

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

* 코드

n_move = input() # 나이트의 좌표를 입력받음

column = int(ord(n_move[0])) - int(ord('a')) + 1 # 열 문자열
row = int(n_move[1]) # 행 문자열을 얻음, 배열의 두번 째 자리

# 나이트(말) L자 형태로만 이동
# 1. 수평으로 두 칸 이동 뒤에 수직으로 한칸 이동하기
# 2. 수직으로 두 칸 이동 뒤에 수평으로 한칸 이동하기
# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if 1 <= next_row <= 8 and 1 <= next_column <= 8:
        result += 1

print(result)

예제. 게임 개발 ***

1. 현재 위치에서 현재 방향을 기준으로 왼쪽방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.

2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어있는 칸의 경우에는, 바라보는 방향을 유지한 채로 한 칸 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

입력 조건:
첫째 줄에 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3 <= N, M <= 50)

둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다.
방향 d의 값으로는 다음과 같이 4가지가 존재한다.
- 0: 북쪽
- 1: 동쪽
- 2: 남쪽
- 3: 서쪽

셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어 있다.
- 0: 육지
- 1: 바다

처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

출력 조건:
첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

* 문제 해설

전형적인 시뮬레이션 문제.

삼성전자 공채 코딩 테스트에서 자주 출제되는 대표적인 유형.

별도의 알고리즘이 필요하기보다는 문제에서 요구하는 내용을 오류없이 성실하게 구현만 할 수 있다면 풀 수 있다는 특징.

** tips:

일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다.

예를 들어 현재 캐릭터가 북쪽을 바라보고 있을 때는 북쪽으로 이동하기 위해 x와 y 좌표를 각각 dx[0], dy[0]만큼 더한다.

현재 위치에서 (-1, 0)만큼 이동시키는 것.

반복문을 이용하여 모든 방향을 차례대로 확인할 수 있다.

리스트 초기화 방법,

# N x M 크기의 2차원 리스트 초기화
n = 3
m = 4
array = [[0] * m for _ in range(n)]
print(array)

결과: [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

* 코드

n, m = map(int, input().split()) # 열 n, 행 m 입력 받음 m X n

# 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어짐
# 방향 d의 값으로는 0: 북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽

d =[[0] * m for _ in range(n)] # 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
x, y, direction = map(int, input().split()) # 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
d[x][y] = 1  # 현재 좌표 방문 처리

# 맵이 육지인지 바다인지에 대한 정보가 주어짐 0: 육지, 1: 바다
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

# 반시계 방향이니, 북 -> 동 -> 남 -> 서 로 방향 정의
dx = [-1, 0, 1, 0] # y축만 고려
dy = [0, 1, 0, -1]

# 왼쪽으로 회전하는 함수
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)

어렵다.. *

출처: [이것이 취업을 위한 코딩 테스트다 with 파이썬] 서적

저작자표시 (새창열림)