코딩테스트 문자열 유형 정리

leehyuna·2023년 7월 24일

코딩테스트

목록 보기

8/8

회문(Palindrome)

문자열 뒤집기

조건에 맞게 재정렬

특정 단어 추출

애너그램 (anagrams) : 문자를 재배열해 다른뜻을 가진 단어로 바꾸는것

가장 긴 팰린드롬 찾기

1. 회문 (Palindrome)

회문, 즉 팰린드롬이란 앞뒤가 똑같은 단어나 문장을 의미한다. 이때 대소문자를 구분하지 않으며 글자와 숫자만 따지면 된다. ex_ '가나다다나가' 'Madam, I'm Adam'

문제로는 "앞뒤가 같은 단어를 찾아라.", "회문인 것을 찾아라." 등으로 출제되며, 최근 코딩 테스트는 영어로 코딩 테스트가 출제되고 있는데, "Palindrome"이라는 단어나 직접적으로 나올 수 있으니 단어도 눈에 익혀두길 바란다. 파이썬으로 이해해 보면 아래와 같다.

풀이 1 : 슬라이싱과 re를 이용한 풀이

	import re 
    
	def isPalindrome(str) :
    	# 전처리
    	str = str.lower()
        str = re.sub('[^a-z0-9]', '', str)
        
        # 팰린드롬 확인
        if str == str[::-1] :
        	print('palindrome이다.')
        else :
        	print('palindrome이 아니다.')

풀이 2 : deque을 이용한 풀이

	import collections
    
    def isPalindrome(str) :
    	deq = collections.deque()
        for c in str :
        	if c.isalnum():
            	deq.append(c.lower())
                
        while len(deq) > 1 :
        	if deq.popleft() != deq.pop() :
            	print('회문이 아닙니다.')
            	return
            print('회문입니다.')

2. 문자열 뒤집기

이 유형은 리스트 내부에 있는 문자열을 뒤집는 방법을 물어보는 것이다. 예를 들면 ['a', 'b', 'c']를 ['c', 'b', 'a']로 변환하는 방식을 물어보는 것이다.

풀이 1 : reverse 이용

	def reverseString(str) :
    	str.reverse()
        print(str)

풀이 2 : 슬라이싱

	def reverseString(str) :
    	print(str[::-1])

만약 코딩 테스트 시에 a=a[::-1]가 오류가 뜬다면, 시스템 내부적으로 변수 할당에 제약을 걸어놨을 가능성이 있으므로 a[:]=a[::-1]로 변경하여 작성하자.

풀이 3 : 투 포인터

투 포인터를 이용한 방법에 대해 알아보자. 아래의 코드처럼 처음과 끝은 인덱스를 변수로 지정한 후에 변수를 +1이나 -1 하여 인덱스를 이동시켜 조작하는 방식이다. 포인터를 활용한 방식은 나중에 정렬을 배울 때도 유용하게 사용되므로 이해하고 넘어가자.

	def reverseString(str) :
    	left_idx, right_idx = 0, len(str)-1
        
        while left_idx < right_idx :
        	str[left_idx], str[right_idx] = str[right_idx], str[left_idx]
            left_idx += 1
            right_idx -= 1
            
        print(str)

3. 조건에 맞게 재정렬

data = ['1 A', '1 B', '6 A', '2 D', '4 B']

data.sort(key= lambda x: (x.split()[1], x.split()[0]))

4. 특정 단어 추출

문제 : Hit를 제외한 단어중 가장 많이 등장하는 단어를 뽑는 코드를 작성하라
단 대소문자는 구분하지 않고, 구두점은 무시한다.

import re
from collections import Counter

banned = 'hit'
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit"

words_list = re.sub('[\w]', ' ', paragraph).lower().split()
words_list = [w for w in words_list if w not in banned]
cnt = Counter(words_list)

print(cnt.most_common()[0][0])

5. 애너그램 (Anagram)

애너그램이란 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다. 아래와 같이 입력값을 넣었을 때, 알파벳 순서를 바꾸면 같은 값이 되는 것들끼리 묶어서 출력되는 알고리즘을 작성해 보자. (출력 값에서 그룹의 순서는 정답에 영향을 끼치지 않는다.)

입력값 : ["eat","tea","tan","ate","nat","bat"]
출력값 : [["bat"],["nat","tan"],["ate","eat","tea"]]

풀이

from collections import defaultdict

data = ["eat","tea","tan","ate","nat","bat"]
sort_data = defaultdict(list)
for word in data :
	sort_data[''.join(sorted(word))].append(word)
    
print(sort_data.values())

6. 가장 긴 펠린드롬 찾기

주어진 문자열에 존재하는 많은 팰린드롬 중에 가장 긴 팰린드롬을 찾는 방법을 생각해 보자. 앞에서 우리는 [::-1]을 통해 팰린드롬을 찾아본 적이 있다.

인덱스를 0부터 끝까지 하나씩 위치를 이동해가면서 팰린드롬을 확인하는 방법이 최선이다.


def palindrome(n, left, right) :
	while right < len(data) and left > 0 and data[left] == data[right-1] : 
    	left -= 1
        right += 1
    return data[left+1:right-1]

data = 'ewqpbewqbfjabcdefedcbaienqnfkndkl'
res = ''

if data == data[::-1] or len(data) < 2 :
	print(data)
else :
	for i in range(len(data)-1):
    	res = max(res, palindrome(len(data), i, i+1), palindrome(len(data),i, i+2), key=len)
    print(res)

이전 포스트

코딩테스트 문자열 유형 정리