문제 개요
문자열 S가 주어졌을 때, 이 문자열의 글자들을 왼쪽에서 오른쪽 방향으로 한 줄씩 작성한다고 가정해 봅시다. 각 줄의 최대 너비는 100 단위이며, 어떤 글자를 작성했을 때 해당 줄의 너비가 100 단위를 초과하게 된다면, 그 글자는 다음 줄로 넘어가 작성됩니다.
또한 배열 widths가 함께 주어집니다. 여기서 widths[0]은 글자 'a'의 너비, widths[1]은 'b'의 너비를 의미하며, 이후 글자들도 같은 방식으로 대응됩니다.
구해야 할 답
- 문자열 S의 글자가 하나라도 포함된 줄은 총 몇 줄인가?
- 마지막 줄에서 실제로 사용된 너비는 몇 단위인가?
결과는 길이 2의 정수 리스트 형태로 반환합니다.
예시
입력이 다음과 같다고 가정해 보겠습니다.
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
이때 출력은 [2, 4]가 됩니다. 그 이유는 다음과 같습니다.
- 'a'를 제외한 모든 글자의 너비는 10입니다.
- "bbbcccdddaa"까지 작성하면 9 × 10 + 2 × 4 = 98 단위를 차지합니다.
- 마지막 'a'는 첫 번째 줄에 남은 공간이 2단위뿐이므로 두 번째 줄에 작성됩니다.
따라서 총 2줄이 필요하고, 두 번째 줄의 사용 너비는 4단위입니다.
풀이 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- line := 1, count := 0 으로 초기화합니다.
- S의 각 문자 i에 대해 다음을 반복합니다.
- count := count + widths[(i의 아스키 코드) − 97]
- 만약 count > 100이라면
- line := line + 1
- count := widths[(i의 아스키 코드) − 97]
- [line, count]를 반환합니다.
여기서 −97을 빼는 이유는 소문자 'a'의 아스키 코드가 97이므로, 각 문자를 widths 배열의 인덱스(0~25)로 변환하기 위함입니다.
구현 예제
class Solution:
def numberOfLines(self, widths, S):
line = 1
count = 0
for i in S:
count += widths[ord(str(i)) - 97]
if count > 100:
line += 1
count = widths[ord(str(i)) - 97]
return [line, count]
ob = Solution()
print(ob.numberOfLines([4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], "bbbcccdddaaa"))
입력
[4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], "bbbcccdddaaa"
출력
[2, 4]
정리
이 문제의 핵심은 문자열을 순회하면서 누적 너비(count)를 추적하고, 너비가 100 단위를 초과하는 순간 새로운 줄로 넘어가는 것입니다. 시간 복잡도는 문자열의 길이에 비례하여 O(n)이며, 추가 메모리 사용 없이 O(1) 공간으로 해결할 수 있는 효율적인 시뮬레이션 문제입니다.