9일차

게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 예제 1.4~1.9

내용 정리

9 면접 문제

1.4 회문 순열

주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.

예제

입력 : Tact Coa

출력 : True (순열: “taco cat”, “atco cta” 등)

def main(s):
    arr = list(s)
    new_arr = set(arr)
    if 2*len(new_arr) - len(arr) <= 1:
        return True
    else:
        return False

1.5 하나 빼기

문자열을 편집하는 방법에는 세 가지 종류가 있다. 문자 삽입, 문자 삭제, 문자 교체. 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수를 작성하라.

예제

pale, ple -> true

pales, pale -> true

pale, bale -> true

pale, bake -> false

def main(a,b): # a가 b보다 길이가 길다고 가정
    cnt = 0
    for i in range(len(a)):
        if a[i] not in b:
            cnt += 1
        if cnt > 1:
            return False
    return True

1.6 문자열 압축

반복되는 문자의 개수를 세는 방식의 기본적인 문자열 압축 메서드를 작성하라. 예를 들어 문자열 aabccccaaa를 압축하면 a2b1c5a3이 된다. 만약 ‘압축된’ 문자열의 길이가 기존 문자열의 길이보다 길다면 기존 문자열을 반환해야 한다. 문자열은 대소문자 알파벳(a~z)으로만 이루어져 있다.

def main(s):
    arr = list(s)
    new_arr = set(arr)
    new_arr = list(new_arr)
    ans = []
    for i in new_arr:
        tmp = arr.count(i)
        ans.append(i)
        ans.append(tmp)
    if len(ans) > len(arr):
        return s
    else:
        return str(ans)

1.7 행렬 회전

이미지를 표현하는 N x N 행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때, 이미지를 90도 회전시키는 메서드를 작성하라. 행렬을 추가로 사용하지 않고서도 할 수 있겠는가?

def main(board):
    n = len(board)
    k = n//2
    for a in range(k):
        for b in range(n):
            one = board[a][a+b]
            two = board[a+b][a+n-1]
            three = board[a+n-1][a+n-1-b]
            four = board[a+n-1-b][a]
            tmp = four
            four = three
            three = two
            two = one
            one = tmp

1.8 0 행렬

M x N 행렬의 한 원소가 0일 경우, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라.

def main(board,m,n):
    for i in range(m):
        for j in range(n):
            if not board[i][j]:
                board[i] = [0 for _ in range(n)]
                for k in range(m):
                    board[k][j] = 0

1.9 문자열 회전

한 단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌고, s2가 s1을 회전시킨 결과인지 판별하고자 한다(가령 ‘waterbottle’은 ‘erbootlewat’을 회전시켜 얻을 수 있는 문자열이다). isSubstring 메서드를 한 번만 호출해서 판별할 수 있는 코드를 작성하라.

def main(s1,s2):
    s1s1 = s1+s1
    if isSubstring(s1s1,s2):
        return True
    else:
        return False

waterbottle 을 wat + erbottle로 쪼갠후 회전하면 erbottlewat가 된다.

wat 을 a, erbottle 을 b라 하면 s1 = ab, s2 = ba이다.

s1s1 = abab이므로 항상 s2인 ba를 포함한다.

읽고 나서

VS코드에 입력할떄는 잘되는데 머리로만 생각하니 잘안된다..

자료구조(3) 배열과 문자열

예제 1.4부터

9일차