[Algorithm] 구현 - Implementation (Python)

📌 구현

코딩 테스트에서 구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정을 의미한다. 일반적으로 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 경우가 많다.

이것이 취업을 위한 코딩테스트다에서는 완전 탐색과 시뮬레이션을 모두 구현 유형으로 묶어서 다루고 있다.

완전 탐색은 모든 경우의 수를 주저 없이 다 계산 하는 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 유형을 의미한다.

구현 시 고려해야 할 사항

자료형
C/C++과 자바에서는 기본 int 자료형의 표현 범위가 -2,147,483,648 ~ 2,147,438,647이다. 따라서 더 큰 수를 표현하기 위해서는 long long 자료형이나 BigInteger 클래스를 이용해야 한다. 하지만 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없고, 매우 큰 수의 연산 또한 기본으로 지원하기 때문에 크게 고민할 필요가 없다.

리스트의 크기
대체로 코딩 테스트에서는 128 ~ 512MB로 메모리를 제한한다. 파이썬은 구현상의 복잡함이 적은 대신 데이터 처리량이 많은 경우에는 꼭 메모리 제한을 고려해야 한다.

상하좌우

다음 진행 방향에 대한 정보를 입력 받아서 이동한 후, 도착 좌표를 출력하는 문제다. 입력이 string 자료형으로 주어지기 때문에 dictionary 자료형을 사용하여 정수 형태로 변환해주었다.

내가 작성한 코드

import sys
input = sys.stdin.readline

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

# 위치 정보 정수 형태로 변환
dir = {
	"U": 0,
	"D": 1,
	"L": 2,
	"R": 3,
}

# 이동 방향 설정
dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]

# 공간 내의 좌표인지 체크
def in_range(x, y):
	return 0 < x < n and 0 < y < n

for val in order:
	idx = dir[val]

	nx, ny = x + dxs[idx], y + dys[idx]
	
	if in_range(nx, ny):
		x, y = nx, ny

print(x, y)

시각

00시 00분 00초부터 입력 받은 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함된 모든 경우의 수를 구하는 문제다.

내가 작성한 코드

n = int(input())

cnt = 0

for i in range(n + 1):
	for j in range(60):
		for k in range(60):
			time = str(i) + str(j) + str(k)

			if "3" in time:
				cnt += 1

print(cnt)

모든 시각의 경우의 수를 하나씩 세어도 86,400가지밖에 존재하지 않는다. 즉, 파이썬의 문자열 연산을 사용해도 시간 제한 2초 안에 문제를 풀 수 있기 때문에 완전 탐색의 방법으로 문제를 해결할 수 있다.

왕실의 나이트

입력 받은 위치 정보를 정수 형태로 변환하는 게 중요하다. a ~ h를 1 ~ 8이라고 생각하고 문제를 접근하면 쉽게 해결할 수 있다.

내가 작성한 코드

val = input()

# 열 위치 정수 형태로 변환
dir = {
	"a" : 1,
	"b" : 2,
	"c" : 3,
	"d" : 4,
	"e" : 5,
	"f" : 6,
	"g" : 7,
	"h" : 8,
}

x, y = int(val[1]), int(dir[val[0]])

cnt = 0

# 이동 가능한 위치인지 체크
def in_range(x, y):
	return 1 <= x < 9 and 1 <= y < 9

# 나이트의 이동 가능 방향
dxs, dys = [2, 2, -2, -2, 1, -1, 1, -1], [1, -1, 1, -1, 2, 2, -2, -2]

for dx, dy in zip(dxs, dys):
	nx, ny = x + dx, y + dy

	if in_range(nx, ny):
		cnt += 1

print(cnt)

예시 코드

val = input()
x, y = int(val[1]), int(ord(val[0])) - int(ord('a')) + 1

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

def in_range(x, y):
	return 1 <= x < 9 and 1 <= y < 9
    
cnt = 0
for step in steps:
	nx, ny = x + step[0], y + step[1]
    
    if in_range(nx, ny):
    	cnt += 1

printc(cnt)

열 정보를 정수로 변환하기 위해 dictionary 자료형을 사용한 것과 다르게 예시 코드에서는 아스키코드 변환 함수 ord()를 사용했다. 코드를 보다 간결하게 작성할 수 있기 때문에 사용에 익숙해지도록 하자.

또한, dxs, dys를 사용한 것이 아니라 steps 배열에 나이트의 이동 가능 위치를 모두 저장하고 반복문을 통해 접근했다. 큰 차이는 없지만 상황에 따라 적절한 방법을 사용하도록 하자.

게임 개발

dx, dy를 사용하여 좌표평면에서 회전을 하고, 방문한 적이 있는 장소라면 1을, 방문한 적이 없는 장소라면 0을 할당하여 구분한다.

예시 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a, b, d = map(int, input().split())

game = [list(map(int, input().split())) for _ in range(n)]
temp = [([0] * m) for _ in range(n)]
temp[b][a] = 1

dxs, dys = [0, 1, 0, -1], [-1, 0, 1, 0]

def turn_left():
	global d

	d -= 1
	if d == -1:
		d = 3

cnt = 1
turn = 0
while True:
	turn_left()
	nx, ny = a + dxs[d], b + dys[d]
	
	if game[ny][nx] == 0 and temp[ny][nx] == 0:
		temp[ny][nx] = 1
		a, b = nx, ny
		cnt += 1
		turn = 0
		continue
	
	else:
		turn += 1

	if turn == 4:
		nx, ny = a - dxs[d], b - dys[d]

		if game[ny][nx] == 0:
			a, b = nx, ny
		
		else:
			break

		turn = 0
	
print(cnt)

네 방향을 모두 확인한 경우, 왔던 곳으로 돌아가는 로직을 구현하지 못했다. turn 변수를 생성하고 갈 수 없는 곳을 만날 때마다 1을 더해준다. turn이 4가 된다면 모든 방향을 확인했다는 의미이므로 이 때 왔던 곳으로 돌아가면 된다.

추가로, 예시 코드에서는 temp 배열을 새로 생성해서 방문 여부를 확인했다. 이 때 방문한 장소라면 2를 할당하여 기존의 배열 내에서도 방문 여부를 구분할 수 있다고 판단했다. 상황에 맞게 적절히 사용하도록 하자.

럭키 스트레이트

입력값을 문자열로 받은 뒤 좌우측 문자열을 int 자료형으로 변환해서 비교해주면 된다.

n = input()

m = len(n) // 2

if sum(map(int, n[:m])) == sum(map(int, n[m::])):
	print("LUCKY")
else:
	print("READY")

몫 연산자 //를 활용하여 중간 인덱스를 찾았고, map() 함수를 이용하여 문자열로 받은 입력값을 정수 자료형으로 변환해주었다.

문자열 재정렬

입력값이 문자인지 숫자인지 여부에 따라 구분하고 필요한 연산을 처리해준 뒤 다시 합쳐준다.

n = input()

_str = ""
_int = 0

for i in n:
	if i.isalpha():
		_str += i
	
	else:
		_int += int(i)

print("".join(sorted(_str)) + str(_int))

빈 문자열 _str과 _int를 생성했다. 그리고 isalpha() 메서드를 활용하여 입력값의 데이터가 알파벳인지 아닌지 판별했다. 알파벳이라면 _str 문자열에 더해주었고, 알파벳이 아니라면 int 자료형으로 변환하여 _int에 더해주었다.

마지막으로 _str 문자열을 sorted() 메서드로 정렬한 뒤 join() 메서드로 문자열화 시켜서 _int와 함께 출력했다.

문자열 압축

이중 반복문을 활용하여 step을 설정할 필요가 있다. 이 때, step은 최대 문자열 s의 절반을 넘지 않는다. 절반을 넘게 되면 중복된 문자열 조합이 나올 수 없기 때문이다. 그리고 step을 결정하는 반복문이 종료될 때마다 생성된 문자열의 길이를 비교하여 더 짧은 것으로 갱신해준다.

내가 작성한 코드

s = input()

n = len(s) // 2
result = 1e9

if len(s) == 1:
	result = 1

for i in range(1, n+1):
	temp = ""
	cnt = 1

	for j in range(0, len(s), i):
		if s[j:j+i] == s[j+i:j+2*i]:
			cnt += 1
			continue

		else:
			temp += str(cnt) + s[j:j+i] if cnt >= 2 else s[j:j+i]
			cnt = 1
		
	result = min(result, len(temp))

print(result)

처음엔 temp를 배열로 설정하여 값을 append() 해주었다. 그랬더니 문자열의 길이를 구할 때 "".join() 메서드를 사용해야 하는 수고가 생겨버려서 temp를 빈 문자열로 설정했다.

해당 코드를 프로그래머스에서 실행시켰을 때, 5번 테스트케이스에서 오류가 발생했다. 알고 봤더니 처음 입력 받은 문자열의 길이가 1일 때 발생하는 오류였다. 그래서 len(s) == 1일 경우 1을 출력할 수 있도록 코드를 수정해주었다.

--

참고 도서

🙇🏻‍♂️ 나 동빈, 이것이 취업을 위한 코딩테스트다