백준 17487 - 타자 연습
https://www.acmicpc.net/problem/17487
문제 요약
QWERTY 키보드에서 영문 문장을 입력할 때, 왼손과 오른손의 키 누름 횟수를 구하는 문제다.
핵심 규칙은 다음과 같다.
키 배정 — Y·G·B 까지가 왼손 영역이고, 그보다 오른쪽(U·H·N 이후)은 오른손 영역이다.
Shift / Space — 이 키들은 양손 어느 쪽으로든 누를 수 있어서, 양손의 누른 횟수 차이를 최소화하는 데 쓴다.
동률 시 왼손 우선 — 차이를 줄인 뒤에도 1이 남으면 왼손이 한 번 더 누른다.
키 분류
QWERTY 배열에서 각 행의 경계를 기준으로 좌우를 나누면 다음과 같다.
| 행 | 왼손 | 오른손 |
|---|---|---|
| 상단 | Q W E R T Y | U I O P |
| 중단 | A S D F G | H J K L |
| 하단 | Z X C V B | N M |
즉, 오른손에 해당하는 소문자 집합은 {u, i, o, p, h, j, k, l, n, m} 이 10개뿐이고, 나머지 16개 영문자는 전부 왼손이다.
풀이 전략
입력 분류
입력의 각 문자를 세 종류로 나눈다.
① 소문자 영문 — 해당 키의 좌/우를 판정해 카운트에 직접 반영한다.
② 대문자 영문 — 실제 키는 소문자와 같으므로 좌/우 판정은 동일하게 하되, Shift를 한 번 눌러야 하므로 "유동 키" 1회를 적립한다.
③ 스페이스 — 좌우 어느 손이든 누를 수 있으므로 "유동 키" 1회를 적립한다.
여기서 유동 키란 Shift와 Space처럼 양손 중 아무 쪽에나 배분 가능한 키 누름 횟수를 말한다.
유동 키 분배
소문자 기준으로 왼손 카운트 $L$, 오른손 카운트 $R$, 유동 키 총 횟수 $J$를 구했다면, $\delta = |L - R|$로 두 손의 차이를 계산한다.
Case 1. $J \ge \delta$ — 유동 키가 차이보다 크거나 같으면, 먼저 $\delta$개로 적은 쪽을 채워 양손을 같게 만든다. 남은 $J - \delta$개는 반으로 나눠 양손에 분배하고, 홀수이면 왼손에 1을 추가한다.
Case 2. $J < \delta$ — 유동 키가 부족하면, 전부 적은 쪽에 몰아 차이를 최대한 줄인다.
비트 연산으로 대소문자 통합
ASCII에서 대문자 A는 65(0x41), 소문자 a는 97(0x61)이다. 둘의 차이는 정확히 32(0x20)로, 6번째 비트 하나만 다르다. 따라서 대문자에 |32 (OR 연산)을 적용하면 해당 비트를 켜서 소문자로 변환할 수 있다. 이미 소문자인 경우에도 해당 비트가 이미 1이므로 값이 변하지 않아 안전하다. 덕분에 좌/우 판정을 소문자 집합 하나로 통일할 수 있다.
코드
import sys
data = sys.stdin.buffer.read().rstrip()
right = set(b'uiophjklnm')
flex = 0 # 유동 키 (Shift, Space)
cnt = [0, 0] # cnt[0]=왼손, cnt[1]=오른손
for c in data:
if c == 32: # 스페이스 → 유동
flex += 1
else:
if 64 < c < 91: # 대문자 → Shift 유동 + 소문자 변환
flex += 1
c |= 32
cnt[c in right] += 1 # 소문자 기준 좌/우 카운트
delta = cnt[0] - cnt[1] # 왼손 - 오른손
if flex >= abs(delta):
flex -= abs(delta) # 차이를 메움
base = max(cnt) + (flex >> 1) # 나머지 반씩 분배
print(base + (flex & 1), base) # 홀수면 왼손 +1
else:
cnt[delta > 0] += flex # 적은 쪽에 전부 투입
print(*cnt)코드 흐름 요약
cnt[c in right]는 c in right가 True(=1)이면 오른손, False(=0)이면 왼손을 증가시킨다. 마찬가지로 cnt[delta > 0]에서 delta > 0이면 왼손이 더 크다는 뜻이므로 오른손(인덱스 1)에 유동 키를 투입하고, 반대면 왼손(인덱스 0)에 투입한다.
비트 시프트 flex >> 1은 2로 나눈 몫, flex & 1은 홀짝 판정이다.
예제 검증
예제 1: Konkuk
입력
Konkuk출력
1 6소문자로 변환하면 k, o, n, k, u, k — 6글자 전부 오른손 영역이므로 $L=0$, $R=6$이다. 대문자 K를 위한 Shift 1회가 유동 키이므로 $J=1$. $\delta = |0-6| = 6$이고 $J < \delta$이므로, 유동 키 1개를 전부 적은 쪽(왼손)에 투입한다. 결과: 1 6.
예제 2: Hello World
입력
Hello World출력
7 6소문자 변환 후: h(R) e(L) l(R) l(R) o(R) w(L) o(R) r(L) l(R) d(L) → $L=4$, $R=6$. 유동 키: 대문자 H → 1, 대문자 W → 1, 스페이스 → 1 = $J=3$. $\delta=|4-6|=2$이고 $J \ge \delta$이므로, 먼저 2개로 차이를 메워 양손 모두 6으로 맞춘다. 남은 $J=1$은 홀수이므로 왼손에 +1 → 7 6.