백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-1343 폴리오미노 편(python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/1343

반응형

---

솔루션 살펴보기!!

def cover_board(board):
    result = []  # 문자열 연결 시 리스트를 사용하여 성능 최적화
    i = 0
    n = len(board)
    
    while i < n:
        # 현재 위치가 '.'이면 그대로 추가하고 다음 칸으로 이동
        if board[i] == '.':
            result.append('.')
            i += 1
        else:
            count = 0
            # 연속된 'X'의 개수를 셉니다.
            while i < n and board[i] == 'X':
                count += 1
                i += 1

            # 'X'의 개수가 홀수면 덮을 수 없으므로 "-1" 반환
            if count % 2 != 0:
                return "-1"

            # 최대한 'AAAA'로 덮습니다.
            result.append('AAAA' * (count // 4))

            # 나머지 2개는 'BB'로 덮습니다.
            if count % 4 == 2:
                result.append('BB')
    
    # 리스트를 문자열로 변환하여 반환
    return ''.join(result)

# 입력 받기
import sys

def main():
    # 입력값을 읽어와서 양 끝 공백 제거
    board = sys.stdin.read().strip()
    # 보드를 덮은 결과 출력
    covered = cover_board(board)
    print(covered)

if __name__ == "__main__":
    main()

---

문제 풀이 전략

이 문제는 주어진 문자열 board에서 연속된 'X' 문자를 특정 패턴의 타일로 덮는 문제입니다. 타일은 두 가지 종류가 있으며, 각각 다음과 같은 규칙을 따릅니다:

• 타일 종류:
  • 'AAAA': 4개의 칸을 덮는 타일
  • 'BB': 2개의 칸을 덮는 타일

해결해야 할 문제

• 연속된 'X'를 모두 덮어야 하며, 덮을 수 없으면 "-1"을 반환합니다.
• 'X'의 개수에 따라 가능한 한 많은 'AAAA' 타일을 먼저 사용하고, 나머지를 'BB'로 덮어야 합니다.
• 'X'의 개수가 홀수이면 'BB'로도 덮을 수 없으므로 덮을 수 없는 상태입니다.

풀이 전략

1. 입력 처리 및 초기화:
   • 주어진 board 문자열을 입력받고, 빈 문자열 result (리스트 형태로 최적화)에 결과를 저장할 준비를 합니다.
   • 보드를 순회할 인덱스 i와 보드의 길이 n을 초기화합니다.
2. 보드 순회:
   • 보드를 처음부터 끝까지 순회하면서 두 가지 상황을 처리합니다:
     1. 현재 문자가 .이면 result에 그대로 추가하고, 다음 칸으로 이동합니다.
     2. 현재 문자가 X이면, 연속된 X의 개수를 셉니다. 이때, while 루프를 사용하여 i가 보드의 끝까지 가거나 X가 아닌 문자가 나올 때까지 반복해서 개수를 셉니다.
3. 연속된 'X' 덮기:
   • 연속된 X의 개수가 홀수인 경우, 2개 단위로 덮어야 하기 때문에 불가능하며, 이 경우 "-1"을 반환합니다.
   • 개수가 짝수인 경우, 가능한 한 많은 4개 단위(AAAA)로 덮습니다. 이를 위해 count // 4로 'AAAA' 타일을 배치합니다.
   • 남은 개수가 2이면 BB 타일로 덮습니다. count % 4 == 2인 경우 'BB'를 결과에 추가합니다.
4. 결과 반환:
   • 보드를 다 순회한 후, result 리스트에 저장된 내용을 하나의 문자열로 변환하여 최종 결과를 반환합니다.

문제 풀이의 핵심 포인트

• 연속된 'X' 처리: 문제에서 'X'의 개수를 세어 이를 덮을 수 있는지 판단하는 것이 중요합니다. 타일의 배치 규칙상, 'X'의 개수는 반드시 짝수여야 하며, 가능한 한 많은 'AAAA'로 덮고, 남은 2개는 'BB'로 덮는 것이 핵심입니다.
• 경우에 따른 처리:
  • 만약 연속된 'X'가 하나이거나 홀수일 경우, 타일로 덮을 수 없으므로 즉시 "-1"을 반환해야 합니다.
  • .은 타일을 배치할 필요가 없으므로 그대로 결과에 추가합니다.
• 최적화: Python에서 문자열 덧셈 연산은 비효율적일 수 있으므로 리스트에 결과를 저장하고 마지막에 문자열로 변환하여 성능을 향상시킵니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 **O(n)**입니다. n은 board의 길이이며, 보드를 한 번 순회하면서 모든 연속된 X를 처리하므로, 시간 복잡도는 입력 보드의 길이에 비례합니다.

---

코드 면접시 알아야할 주요 개념

1. 문자열 처리 (String Manipulation):

• 문자열 순회: 주어진 문자열을 탐색하는 기본적인 방식에 익숙해야 합니다. 이 문제에서는 문자열을 한 글자씩 순회하면서 특정 조건을 확인하고 결과를 생성합니다. 문자열을 탐색하고 처리하는 방식이 중요한 포인트입니다.
• 문자열 연결 (String Concatenation) 최적화: Python에서 문자열 연결(+=)은 비효율적일 수 있으므로, 성능 최적화를 위해 리스트를 사용하고 마지막에 ''.join()으로 변환하는 방법이 좋습니다. 이는 성능에 민감한 경우 특히 중요하며, 대용량 데이터 처리 시 효율적인 문자열 처리를 위한 방법으로 사용됩니다.

2. 그리디 알고리즘 (Greedy Algorithm):

• 이 문제에서 타일을 덮는 방식은 그리디 접근법을 사용합니다. 가능한 한 큰 단위부터 (4칸을 덮는 'AAAA') 타일을 사용하고, 남은 부분을 더 작은 단위 (2칸을 덮는 'BB')로 처리합니다. 그리디 알고리즘은 현재 상황에서 최적의 선택을 하여 전체 문제를 해결하는 전략을 취합니다.
• 면접 중 그리디 알고리즘을 선택한 이유를 설명하는 것이 중요합니다. 이 문제에서 그리디 접근이 유효한 이유는 연속된 'X'를 2칸 단위로 덮어야 하고, 가능한 한 큰 타일을 사용하여 최소한의 연산으로 문제를 해결할 수 있기 때문입니다.

3. 조건 처리 (Condition Handling):

• 연속된 'X'의 개수 판단: 문제에서 중요한 포인트는 연속된 'X'의 개수가 짝수인지 여부입니다. 'X'의 개수가 홀수일 경우 덮을 수 없기 때문에, 즉시 "-1"을 반환하는 로직이 필요합니다. 이 조건을 빠르게 판단하고 처리하는 능력이 중요합니다.
• 나머지 처리: count % 4를 사용해 남은 X의 개수에 따른 처리를 적절히 분기하는 능력도 필요합니다. 이는 반복문을 통해 문제를 해결하는 데 있어서 핵심적인 로직입니다.

4. 모듈러 연산 (Modular Arithmetic):

• count % 4 연산은 나머지를 구해 남은 타일을 처리하는 데 매우 유용합니다. 이러한 모듈러 연산을 사용하는 능력은 면접에서 자주 요구되는 수학적 사고 과정 중 하나입니다.
• 남은 'X'의 개수에 따라 타일을 적절히 배치하는 부분에서 모듈러 연산을 활용한 것이 이 문제의 중요한 포인트입니다.

5. 시간 복잡도 (Time Complexity):

• **O(n)**의 시간 복잡도: 보드를 한 번 순회하면서 연속된 'X'의 개수를 세고 처리하므로, 이 문제의 시간 복잡도는 **O(n)**입니다. 면접에서 알고리즘의 시간 복잡도를 설명하고, 왜 이 방식이 효율적인지 설명하는 것이 중요합니다.
• 최적화의 필요성 설명: 성능에 대한 우려나 큰 입력에 대한 효율적인 처리가 요구되는 상황에서, 문자열 연결 최적화(''.join(result) 사용)를 통해 성능을 개선할 수 있음을 설명하는 것이 좋습니다.

6. 테스트 케이스와 엣지 케이스:

• 면접에서 중요한 부분 중 하나는 다양한 테스트 케이스와 엣지 케이스에 대한 고려입니다. 면접관은 후보자가 다양한 경우에 대해 생각하는 능력을 평가할 수 있습니다.
• 대표적인 테스트 케이스:
  1. 모든 'X'가 짝수인 경우: "XXXX" → 'AAAA'
  2. 'X'가 홀수인 경우: "XXX" → "-1"
  3. '.'이 포함된 경우: "XX..XX" → 'BB..BB'
  4. 섞인 경우: "XXXX..XX..X" → "-1"
  5. 빈 문자열: "" → ""
• 이 문제에서 엣지 케이스를 고려하는 능력을 보여주는 것이 중요합니다. 예를 들어, board가 매우 짧거나 긴 경우, 혹은 주어진 문자열이 모두 .로 이루어진 경우 등 다양한 케이스를 설명할 수 있어야 합니다.

7. 코드 설명 및 주석:

• 면접에서는 코드가 단순히 작동하는 것뿐만 아니라, 코드가 왜 이렇게 작성되었는지에 대한 설명이 중요합니다. 코드의 주요 흐름을 설명할 수 있어야 하고, 특히 조건 처리, 그리디 전략, 문자열 처리 등 핵심 부분에 대해 상세히 설명하는 것이 좋습니다.
• 주석을 적절히 사용하여 코드의 흐름을 명확히 하거나, 면접 과정에서 논리적인 사고를 강조할 수 있습니다.

8. 에러 처리 (Error Handling):

• 이 문제에서는 연속된 'X'의 개수가 홀수일 경우 "-1"을 반환해야 합니다. 이 부분에서 예외 처리가 필요한 상황을 어떻게 다루는지 설명할 수 있습니다.
• 면접에서 에러 처리 방식이나 잘못된 입력에 대한 고려도 중요한 평가 요소가 될 수 있습니다.

면접 질문에 대한 추가 팁:

• 대안 제시: 만약 입력 보드의 크기가 매우 커지거나 성능이 더 중요해진다면 어떻게 최적화할 수 있을지 묻는 질문에 대비해야 합니다. 이를 통해 추가적인 최적화 가능성을 탐구할 수 있습니다.
• 유사 문제: 이 문제와 유사한 타일 배치 문제 또는 그리디 알고리즘을 사용하는 문제에 대한 경험을 언급할 수 있습니다.