Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 28215
- 삼성코테기출
- 백준
- mcp사용법
- Python
- 3dgs
- 토스유튜브
- mcp튜토리얼
- 미지의 공간탈출
- mcp란
- 그래프
- 20006
- 시계토끼제니쌤
- 구현
- 너비우선탐색
- 시뮬레이션
- DP
- 토익스피킹
- 20922
- 수학
- 토스만능문장
- 토스
- 그리디알고리즘
- 최단거리추적
- 코테
- BFS
- tinycudann
- 그래프탐색
- 그리디
- 토스독학
Archives
- Today
- Total
Victory in my life
Baekjoon 1343 | 폴리오미노 (Python) 본문
📌문제
SILVER5 / 구현 / 그리디 알고리즘
https://www.acmicpc.net/problem/1343
📌문제 분석 및 설계
문제를 봤을 때,
X뭉터기랑 .뭉터기를 분리하는게 이 핵심이라고 생각했다.
따라서 아래와 같은 요소들로 설계를 했다.
1. split를 통해서 분리
2. 나누기로 A,B삽입
3. 반례로 .만 있을때 케이스 분리(자꾸 틀려서 그제야 반례찾으면서 알게 됨)
하지만... replace를 쓴다면 굉장히 간단하게 끝난다..하핳
📌알게된 팁
문자열에 +연산을 계속하면, 문자열은 불변(immutable) 이라서 O(N^2) 성능이 될 수 있다
👉 리스트에 append() 해서 나중에 "".join()으로 합치는 게 더 효율적!!
📌소스 코드
처음코드는 아래와 같고
original=input()
polyomino=original.split('.')
A='AAAA'
B='BB'
def replace_polyomino():
result=[]
for i,p in enumerate(polyomino):
if 'X' in p:
length=len(p)
if length%2==1:
return -1
else:
a,b=divmod(length,4)
b=b//2
result.append(A * a + B * b)
if i!=len(polyomino)-1:
result+='.'
else:
if i!=len(polyomino)-1:
result+='.'
return result
if 'X' not in original:
print(original)
else:
result=replace_polyomino()
print(''.join(result) if result != -1 else -1)
맞춘후 더 나은 코드를 알고자 GPT에게 물어봤더니 아래와 같이 수정해줬다. 훨 간단한 코드다..
original = input()
polyomino = original.split('.')
A = 'AAAA'
B = 'BB'
def replace_polyomino():
result = []
for i, p in enumerate(polyomino):
if p: # 빈 문자열이 아니면 (즉, 'X' 포함)
length = len(p)
if length % 2 == 1:
return -1 # 홀수면 불가능
a, b = divmod(length, 4)
b //= 2
result.append(A * a + B * b)
result.append('.') # 각 구간 사이에 '.' 추가
return "".join(result[:-1]) # 마지막 '.' 제거 후 문자열 변환
# 전부 '.'이면 그대로 출력
if 'X' not in original:
print(original)
else:
result = replace_polyomino()
print(''.join(result) if result != -1 else -1)
그리고 replace를 쓰면 아래와 같이 너무너무너무너무 간단해진다....
S = input()
S = S.replace("XXXX", "AAAA")
S = S.replace("XX", "BB")
print(S if "X" in S else -1)
'CodingTest > Baekjoon' 카테고리의 다른 글
Baekjoon 1463 | 1로 만들기 (Python) (0) | 2025.02.27 |
---|---|
Baekjoon 11724 | 연결요소의 개수 (Python) (0) | 2025.02.26 |
Baekjoon 14940 | 쉬운 최단거리 (Python) (0) | 2025.02.26 |
Baekjoon 2178 | 미로 탐색(Python) (0) | 2025.02.25 |
Baekjoon 1138 | 한 줄로 서기(Python) (0) | 2025.02.25 |