서론
이전에 구현에 대해 글을 작성해본 적이 있다.
https://velog.io/@yorangs/Python-알고리즘-구현
구현/시뮬레이션 문제는 문제 많이 풀어보고 구현을 직접해보는 것이 포인트이다.
유튜브에서 해당 영상을 참고하면서 공부하고 글을 작성하게 되었다.
https://www.youtube.com/watch?v=SwqsX8bb-gw
유형
- 시간 계산 시뮬레이션 시계 돌리기, 타이머, 주기변화 등 (예: 시간 → 분 변환)
- 보드 이동 격자 내 캐릭터 이동, 충돌, 회전 등
- 문자열 파싱 및 조작 특정 기준으로 분할, 특수 조건 추출, 자르고 바꾸기
- 명령어 처리 시뮬레이션 스택, 큐, 힙 같은 자료구조를 명령에 따라 조작
- 이벤트 스케줄링 시뮬레이션 우선순위/시간 조건대로 동작
🕑 시간 계산 시뮬레이션
✅ 개인정보 수집 유효기간
문제 조건
1. N개의 개인정보의 수집 일자와 해당 약관 종류를 파악해서 받아낸 today와 비교하여 파기해야 할 개인정보 번호들을 리스트로 반환한다.
2. 모든 달은 28일까지 있다고 가정한다.
3. 예를 들어, A라는 약관의 유효기간이 12 달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보다.정답
def solve(today, terms, privacy):
date, term = privacy.split(" ")
month = int(terms[term])
year = month // 12
month = month % 12
ty, tm, td = map(int, today.split("."))
py, pm, pd = map(int, date.split("."))
py += year; pm += month
if pm > 12:
pm -= 12; py += 1
pd -= 1
if pd == 0:
pm -= 1; pd = 28
if pm == 0:
py -= 1; pm = 12
return ty*10000 + tm*100 + td > py*10000 + pm*100 + pd
def solution(today, terms, privacies):
answer = []
# terms를 딕셔너리화 하기
terms_dict = {}
for term in terms:
t, m = term.split(" ")
terms_dict[t] = int(m)
# privacies 를 돌아가며 answer에 답 삽입
for idx, privacy in enumerate(privacies):
if solve(today, terms_dict, privacy):
answer.append(idx+1)
return answer기억할 점
datetime모듈을 쓸 수도 있지만 날짜를 총 일 수로 계산해서 비교할 수도 있다.
💬 문자열 파싱 및 조작
✅ 문자열 내림차순으로 배치하기
문제 조건
문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요.
s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다.정답
def solution(s):
arr = []
for i in s:
arr.append(i)
arr.sort(reverse=True)
answer = ""
for a in arr:
answer += a
return answer기억할 점
''.join(sorted(s, reverse=True))이런 식으로 짧게 짤 수 있다.- 글자 순서는 A-Za-z이다.
- 문자열인
s를 sorted로 감싸면 바로 한글자씩 추가된 정렬된 배열을 얻을 수 있다.
✅ 신규 아이디 추천 - 문자열 파싱
문제 조건
1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.정답
def solution(new_id):
new_id = new_id.lower()
new = ""
for s in new_id:
if s.isalnum() or s in ['-', '_', '.']:
new += s
new_id = new
while '..' in new_id:
new_id = new_id.replace('..', '.')
new_id = new_id.strip('.')
if not new_id:
new_id = "a"
new_id = new_id[:15]
new_id = new_id.rstrip('.')
while len(new_id) <= 2:
new_id += new_id[-1]
return new_id기억할 점
isalnum()만으로 숫자와 알파벳으로 이루어졌는지 확인이 가능하다.isdigit(),isalpha(),isalnum()
- … 같은 경우
replace()함수를 써서 .. 을 . 으로 치환한다 해도 여전히 .. 이되므로 처리된 것이 아니다.- 즉, while문으로 처리해야 함
- 양 끝 문자를 삭제하려면
strip()을 쓰면 된다.lstrip(),rstrip()도 있다.- 이거 모르면 이렇게 구현하게 된다…
if new_id[0] == '.': new_id = new_id[1:] if new_id[-1] == '.': new_id = new_id[:-1]
✅ 문자열 압축
문제조건
주어진 문자열을 1개부터 문자열 길이의 절반까지 가능한 모든 단위로 잘라 압축을 시도해야 합니다.
각 단위별로 연속으로 반복되는 부분을 '반복 횟수 + 단위' 형태로 압축한 뒤, 그 결과 문자열의 길이를 구합니다.
이 과정에서 나올 수 있는 가장 짧은 길이를 찾아 반환하는 것이 문제입니다.
"abcabcabcabcdededededede” → 14
문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.
"xababcdcdababcdcd” → 17
문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.
정답
def solution(s):
l = len(s)
m = 10000
for i in range(1, l//2 + 1):
res = ""
arr = []
for j in range(0, l, i):
arr.append(s[j:j+i])
comp = ""
cnt = 1
for j in range(len(arr)):
if comp == arr[j]:
cnt += 1
continue
if cnt > 1:
res += str(cnt)
res += comp
cnt = 1
comp = arr[j]
if cnt > 1:
res += str(cnt)
res += comp
m = min(m, len(res))
return m if len(s) > 1 else 1기억할 점
- 문자열은 +연산자를 통해 이을 수 있다.
- 문자열의 경우 초기와 맨 마지막을 잘 설정해야한다.
- 문제를 끝까지 잘 읽어야 한다.
✅ [1차] 다트 게임
문제 조건
다트 게임은 총 3번의 기회로 구성된다.
각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다.
옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.
0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.정답
def solution(dartResult):
# 각 점수들을 배열로 관리한다 (이전 점수는 현재 점수를 추가하기 전 [-1]로 접근해서 조작한다)
score = []
bonus = {"S":1, "D":2, "T":3}
# dartResult를 돌려서 점수 계산을 시작한다
string_length = len(dartResult)
number = 0
for i in range(string_length):
res = dartResult[i]
# 숫자 -> number에 숫자 할당 (만약 10이라면 0이 감지됐을 때 강제로 10으로 전환)
if res.isdigit():
number = int(res) if res != "0" else (10 if number == 1 else 0)
# S, D, T -> number에 제곱 계산
elif res in ["S", "D", "T"]:
number = number**bonus[res]
# *, # -> 이전 점수에 접근해서 2를 곱하거나 -1을 곱한다
elif res == "*":
number *= 2
if len(score) != 0:
score[-1] *= 2
elif res == "#":
number *= -1
# 다음 순서가 숫자이거나 없다면 score에 추가한다.
if i == string_length-1 or (dartResult[i+1].isdigit() and not res.isdigit()):
score.append(number)
return sum(score)기억할 점
- 숫자를 처리할 때 두 자리수가 들어온다면 조건을 잘 짜줘야한다.
- 정규표현식을 쓰는 라이브러리인
re를 쓰면 더욱 간단하게 해결할 수 있다.
✨ 이벤트 스케줄링 시뮬레이션
✅ 표 편집
문제 조건
"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
"D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
"C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
"Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
위 명령어를 수행한 뒤 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O,
삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성합니다.
5 ≤ n ≤ 1,000,000
0 ≤ k < n
1 ≤ cmd의 원소 개수 ≤ 200,000제출한 답
def solution(n, k, cmd):
cell = {}
for i in range(n):
cell[i] = "O"
index = k
memory = []
for c in cmd:
if len(c) > 1:
command, num = c.split(" ")
num = int(num)
while num > 0:
index += 1 if command == 'D' else -1
if cell[index] == "O":
num -= 1
elif c == "C":
cell[index] = "X"
memory.append(index)
while cell[index] == "X":
index += 1 if index != n - 1 else -1
else:
cell[memory[-1]] = "O"
del memory[-1]
answer = ""
for i in range(n):
answer += cell[i]
return answer이 방법은 시간초과가 나온다.
기억할 점
- 시간초과를 피하기 위해서는 while문 같은 반복문을 쓰는 것이 아닌 linked list 같은 자료구조를 써야한다.
- 연결 리스트를 쓸 때는 항상 처음 노드나 마지막 노드도 고려해서 None인지 아닌지 if문을 거치고 접근해야 한다.
✅ 키패드 누르기
문제 조건
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
- 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
- 왼쪽 열의 3개의 숫자
1,4,7을 입력할 때는 왼손 엄지손가락을 사용합니다. - 오른쪽 열의 3개의 숫자
3,6,9를 입력할 때는 오른손 엄지손가락을 사용합니다. - 가운데 열의 4개의 숫자
2,5,8,0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.
- numbers 배열의 크기는 1 이상 1,000 이하입니다.
- numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
- hand는
"left"또는"right"입니다."left"는 왼손잡이,"right"는 오른손잡이를 의미합니다.
- 왼손 엄지손가락을 사용한 경우는
L, 오른손 엄지손가락을 사용한 경우는R을 순서대로 이어붙여 문자열 형태로 return 해주세요.
정답
def solution(numbers, hand):
answer = ""
location = {1: [4,1], 2: [4,2], 3: [4,3],
4: [3,1], 5: [3,2], 6: [3,3],
7: [2,1], 8: [2,2], 9: [2,3],
"*":[1,1],0: [1,2],"#":[1,3]}
current = ["*", "#"]
for num in numbers:
if num in [1,4,7]:
answer += "L"
current[0] = num
elif num in [3,6,9]:
answer += "R"
current[1] = num
else:
l = location[current[0]]
r = location[current[1]]
c = location[num]
left = abs(l[0]-c[0]) + abs(l[1]-c[1])
right = abs(r[0]-c[0]) + abs(r[1]-c[1])
if left < right or (left == right and hand == "left"):
answer += "L"
current[0] = num
else:
answer += "R"
current[1] = num
return answer기억할 점
- 따로 딕셔너리를 통해 좌표값을 저장해서 푸는 방법이 효율적이고 보기 쉬울 때가 있다.
