꼭 알아야하는 코딩 테스트 유형: 5) #String

• 이번에는 코딩 테스트에서 중요한 유형인 'String(문자열)'에 대해 알아보겠습니다. 문자열은 프로그래밍에서 매우 중요한 데이터 타입으로, 문자들의 시퀀스로 구성됩니다. 문자열은 다양한 문제 유형에서 활용되며, 문자열 조작과 관련된 알고리즘을 효율적으로 구현하는 것이 중요합니다.

 

코딩 테스트에서의 문자열 문제 접근법

 

1. 문제 이해와 제약 사항 파악: 주어진 문제를 정확하게 이해하고, 입력 조건과 제약 사항을 파악해야 합니다.
2. 문자열 조작과 분리: 주어진 문자열을 조작하거나 필요한 부분으로 분리하여 처리할 수 있습니다.
3. 패턴 매칭과 검색: 원하는 패턴이나 부분 문자열을 찾기 위해 패턴 매칭 알고리즘을 활용할 수 있습니다.
4. 정렬과 비교: 정렬된 순서로 문자열을 처리하거나 비교하여 원하는 결과를 얻을 수 있습니다.
5. 특수한 데이터 구조 활용: 스택(Stack), 큐(Queue), 해시(Hash) 등의 특수한 데이터 구조를 활용하여 문자열 문제를 해결할 수 있습니다.
6. 정규식(Regular Expression): 복잡한 패턴 매칭이 필요한 경우 정규식을 사용하여 간단하게 처리할 수 있습니다.
7. 시간 복잡도 분석과 최적화: 대부분의 경우 입력 크기와 관련하여 시간 복잡도가 중요합니다. 최적화 기법을 적용하여 성능 개선에 신경써야 합니다.

 

1120번: 문자열

  문제  
 

• 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.
• 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

 

• 이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

 
  해결 방법  
 

• 이 문제는 두 문자열 A와 B가 주어졌을 때, A의 길이를 늘이거나 줄여서 B와 같게 만드는 최소 변경 횟수를 구하는 문제입니다.
• A가 B보다 짧다면 A를 왼쪽 혹은 오른쪽으로 움직여서 가장 차이가 적게 나도록 맞추면 됩니다. 그 후에 각 위치별로 서로 다른 글자의 개수를 세서 그 중 최솟값을 구하면 됩니다.

a, b = input().split()
min_diff = len(b)

for i in range(len(b)-len(a)+1):
    diff = sum([a[j] != b[i+j] for j in range(len(a))])
    min_diff = min(min_diff,diff)
    
print(min_diff)

 

1254번: 팰린드롬 만들기

  문제  
 

• 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.
• 동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.
• 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

 
  해결 방법  
 

• 이 문제는 주어진 문자열에 몇 개의 문자를 더하여 팰린드롬(앞으로 읽으나 뒤로 읽으나 동일한 문자열)을 만드는 문제입니다.
• 팰린드롬을 만들기 위해 추가해야 하는 문자의 최소 개수를 구하기 위해서는, 주어진 문자열에서 가장 긴 팰린드롬의 시작 위치를 찾으면 됩니다. 그 이유는 가장 긴 팰린드롬이 시작하는 위치 이전의 문자들만 뒤에 추가하면 전체 문자열이 팰린드롬이 되기 때문입니다.
• 따라서, 주어진 문자열의 각 위치에서 시작하는 부분문자열이 팰린드롬인지 확인하고, 그 중 가장 짧은 것을 찾아 그 길이를 출력합니다. 여기서는 Python의 슬라이싱 기능과 [::-1] 연산자를 사용하여 역순 문자열을 쉽게 얻어낼 수 있습니다.

s = input()
n = len(s)

def is_palindrome(string):
    if string == string[::-1]: return True
    else: return False

for i in range(n):
    if is_palindrome(s[i:]):
        print(n+i)
        break

• 문자열은 프로그래밍 문제에서 흔히 등장하는 유형으로, 다양한 방법으로 조작하거나 분석할 수 있습니다. 디버깅도 비교적 쉽고 직관적인 접근 방식 때문에 입문자에게 추천되는 유형 중 하나입니다.
• 하지만 실제 코딩 테스트에서는 복잡한 로직을 요구하는 경우가 많으므로, 다양한 알고리즘과 자료구조에 대한 이해가 필요합니다. 파이썬과 같은 고급 언어들은 특히 다양한 내장 함수와 연산자를 제공하므로 이러한 기능들을 잘 활용할 줄 알아야 합니다.