[Algo] 구현/문자열 다시 보면 좋은 문제 모음집!

구현/문자열 50문제 풀기 도전! 오른쪽 목차를 참조해주세요.

1. 프로그래머스 - 모음사전

소요시간 : 20분

import itertools

def solution(word):
    word = [w for w in word]
    result = []
    for n in range(1,6):
        result += [list(item) for item in list(itertools.product((['A', 'E', 'I', 'O', 'U']), repeat=n))]
    result = sorted(result)
    return result.index(word) + 1

2. 프로그래머스 - 괄호 회전하기

소요시간 : 60분

• for문에서 배열 삭제후 break하는거 잊지 말자. 인덱스 에러 난다
• deepcopy 하자
• string도 s[i:] + s[:i] 로 조작 가능, 삭제 혹은 변경은 안됭
• list를 deque로 저장해서 rotate으로 문자열 회전 할 수 있음.
  - deque(s).rotate(1) : 오른쪽으로 한칸 움직이기
  • deque(s).rotate(-1) : 왼쪽으로 한칸 움직이기

def check(s):
    if s[0] == ')' or s[0] == ']' or s[0] == '}':
        return False
    if s[-1] == '(' or s[-1] == '[' or s[-1] == '{':
        return False
    return True

def is_vaild(s):
    dict = {'(': ')','[': ']','{': '}'}
    temp_s = [w for w in s]
    
    if not check(temp_s):
        return False

    for i in range(len(temp_s)):
        if temp_s[i] not in dict:
            if temp_s[i-1] in dict and temp_s[i] != dict[temp_s[i-1]]:
                return False
            
    while len(temp_s):
        if not check(temp_s):
            return False
        
        temp = dict[temp_s[0]]
        del temp_s[0]
        
        for i in range(len(temp_s)):
            if temp == temp_s[i]:
                del temp_s[i]
                break
    return True

def solution(s):
    answer = 0
    
    if len(s) % 2 != 0:
        return answer
    
    s = list(s)
    for i in range(len(s)):
        if is_vaild(s[i:] + s[:i]):
            answer += 1
        
    return answer

• 스택을 이용해서 풀어봄

def is_vaild(s):
    dict = {')':'(', ']':'[','}':'{'}
    temp_s = [w for w in s]
    stack = []

    while len(temp_s):
        if temp_s[0] in ['(','[','{']:
            stack.append(temp_s.pop(0))
        else:
            if len(stack):
                if dict[temp_s[0]] != stack[-1]:
                    return False
                stack.pop()
                del temp_s[0]
            else: #stack이 비었을때
                return False

    return True

def solution(s):
    answer = 0
    
    if len(s) % 2 != 0:
        return answer
    
    s = list(s)
    for i in range(len(s)):
        if is_vaild(s[i:] + s[:i]):
            answer += 1
        
    return answer

3. 프로그래머스 - 압축

소요시간: 50분

def solution(msg): 
    answer = []
    
    dict = {}
    for i in range(1,27):
        dict[chr(i+64)] = i
    
    n = 1
    while True:
        i = 1         
        while len(msg) >= i:
            if msg[:i]in dict and len(msg) == i:
                answer.append(dict[msg])
                return answer
            if msg[:i] not in dict:
                w = msg[:i-1]
                answer.append(dict[w])
                msg = msg[i-1:]
                break
            i += 1
        if len(msg) > 0:
            dict[w + msg[0]] = 26 + n
            n += 1
        else:
            break

4. 프로그래머스 - 튜플

s.sort(key=len) -> 길이를 기준으로 정렬해야하는 이유를 알아채지 못함

def solution(s):
    answer = []
    s = s[2:-2].split('},{')
    s = [w.split(',') for w in s]
    # print(s)
    s.sort(key=len)
    # print(s)
    for a in s:
        for w in a:
            if int(w) not in answer:
                answer.append(int(w))
    return answer

5. 프로그래머스 - 직업군 추천하기

소요시간: 40분
-> 이런 활용도 고려해볼만하다!
score_table = {lan : score for lan, score in zip(languages, preference)}
-> 훨씬 더 간단한 방법
dict(zip(languages, preference))

>>> keys = [1, 2, 3]
>>> values = ["A", "B", "C"]
>>> dict(zip(keys, values))
{1: 'A', 2: 'B', 3: 'C'}

def solution(table, languages, preference):
    answer = []
    table_dict = {}
    score_dict = {}
    index_to_score = [5,4,3,2,1]
    
    for t in table:
        t = t.split(' ')
        table_dict[t[0]] = t[1:]
        
    for key,values in table_dict.items():
        total = 0
        for i, lan in enumerate(languages):
            if lan in values:
                total += index_to_score[values.index(lan)] * preference[i]
        score_dict[key] = total
        
    max_score = max(score_dict.values())
    for k,v in score_dict.items():
        if v == max_score:
            answer.append(k)
    return sorted(answer)[0]

6. 프로그래머스 - 땅따먹기

소요시간: 한시간 고민 -> 결국엔 구글에 도움 요청 ㅎ

def solution(land):
    answer = 0
    tmp = land
    col = land[0].index(max(land[0]))
    for i in range(1,len(land)):
        for j in range(len(land[0])):
            # print(tmp[i-1][:j]+tmp[i-1][j+1:])
            tmp[i][j] += max(tmp[i-1][:j]+tmp[i-1][j+1:])
    return max(tmp[-1])

->틀린 버전

def solution(land):
    answer = 0
    tmp = land
    col = land[0].index(max(land[0]))
    for i in range(1,len(land)):
        for j in range(4):
            if col != j:
                tmp[i][j] += tmp[i-1][col]
        col = tmp[i].index(max(tmp[i][:col]+[0]+tmp[i][col+1:]))
        print(col)
            
    return max(tmp[-1])

7. 프로그래머스 - 행렬의 곱셈

-> 구조적으로 어떻게 for문을 돌려야 하나 먼저 생각해보자..!

행렬을 곱셉했을때, 결과는 (a x c)이다.
(a x b) * (b x c) = (a x c)

def solution(arr1, arr2):
    answer = [[0] * len(arr2[0]) for _ in range(len(arr1))]
    total = 0
    for a in range(len(arr1)):
        for c in range(len(arr2[0])):
            for b in range(len(arr2)):
                # print(a,b,b,c)
                total += arr1[a][b] * arr2[b][c]
            # print('---------------')
            answer[a][c] = total
            total = 0
    return answer

8. 프로그래머스 - 파일명 정렬

->정규 표현식에 대해서 공부하자.

def splict_str(s):
    for i,w in enumerate(s):
        if w.isdigit():
            return [s[:i], int(s[i:])]
def solution(files):
    answer = []
    files = [[f] for f in files]
    for i,file in enumerate(files):
        if '.' in file[0]:
            index = file[0].index('.')
            # file += [file[0][:index].lower()]
            file += splict_str(file[0][:index].lower())
        elif '-' in file[0]:
            index = file[0].index('-')
            index2 = file[0].index(' ')
            file += [file[0][:index+1].lower()]
            file += [int(file[0][index+1:index2])]
    # print(files)
    files = sorted(files, key = lambda x : (x[1], x[2]))
    # print(files)
    for f in files:
        answer.append(f[0])
    return answer

9. 프로그래머스 - 최소직사각형

소요시간: 15분
-> max값을 찾는 다양한 방법 알아두기
-> 람다식 익숙해 지기

def solution(sizes):
    sizes = [sorted(s) for s in sizes]
    m = max(sizes, key = lambda x: x[0])
    n = max(sizes, key = lambda x: x[1])
    return m[0] * n[1]

def solution(sizes):
    sizes = [sorted(s) for s in sizes]
    m = max(s[0] for s in sizes)
    n = max(s[1] for s in sizes)
    return m * n

10. 프로그래머스 - N개의 최소공배수

-> 라이브러리 이용해서 다시 풀어보자

from gcd import math

11. 프로드래머스 - 방금그곡

소요시간: 2시간 이상
-> 치환을 생각해 보거라!!!

from datetime import datetime

def check(m,n):
    if m in n:
        return True
    return False

def get_new_m(arr):
    tmp = []
    for w in arr:
        if w == '#':
            tmp[-1] += '#'
            continue
        tmp.append(w)
    for i in range(len(tmp)):
        if tmp[i][-1] == '#':
            tmp[i] = tmp[i][0].lower()
    return tmp

def get_music(music):
    t = []
    for mu in music:
        if mu == '#':
            t[-1] = t[-1].lower()
            continue
        t.append(mu)
    return ''.join(t)

def solution(music, musicinfos):
    answer = []
    pre_diff_sec = 0
    music = get_music(music)
    for m in musicinfos:
        m = m.split(',')
        diff_sec = (datetime.strptime(m[1],"%H:%M") - datetime.strptime(m[0],"%H:%M")).seconds // 60
        entire_music = get_new_m(m[3])
        
        n = ''.join((entire_music * diff_sec)[:diff_sec])
        if check(music,n) and diff_sec > pre_diff_sec:
            pre_diff_sec = diff_sec
            answer = [m[2],diff_sec]
    if answer:
        return answer[0]
    return '(None)'

12. 프로그래머스 - 방문 길이

소요시간 : 20분

def solution(dirs):
    move = {'U':[0,1],'D':[0,-1],'R':[1,0],'L':[-1,0]}
    answer = []
    x,y = 0,0
    for dir in dirs:
        xx,yy = x + move[dir][0], y + move[dir][1]
        if xx < -5 or xx > 5 or yy < -5 or yy > 5:
            continue
        if [str(x)+str(y), str(xx)+str(yy)] not in answer:
            answer.append([str(x)+str(y), str(xx)+str(yy)])
            answer.append([str(xx)+str(yy), str(x)+str(y)])
        x, y = xx, yy
    return len(answer) // 2

• 좀 더 깔끔하게 : str로 변환하지 않아도 비교가능
  ex) [1,2,3,4] == [4,3,2,1] // false

def solution(dirs):
    move = {'U':[0,1],'D':[0,-1],'R':[1,0],'L':[-1,0]}
    answer = []
    x,y = 0,0
    for dir in dirs:
        xx,yy = x + move[dir][0], y + move[dir][1]
        if xx < -5 or xx > 5 or yy < -5 or yy > 5:
            continue
        if [x,y,xx,yy] not in answer:
            answer.append([x,y,xx,yy])
            answer.append([xx,yy,x,y])
        x, y = xx, yy
    return len(answer) // 2

13. 프로그래머스 - 입실 퇴실

소요시간: 2시간 하지만 모든 테케 실패. 3시간이상 후 성공
-> collections.counter 알아보기
-> 배열에 길이에 초과하는 인덱스로 슬라이싱을 시도하면 []으로 나타난다

#get: 퇴실이 끝나지 않은 사람 수 구하기. 즉, 아직까지는 입실만 찍힌 사람 
def get(arr):
    return len(arr) - 2 * (len(arr) - len(set(arr)))#중복으로 나타나지 않은 요소 찾기

# def get(arr): # 같은 의미이지만 시간초과..!
#     arr = [a for a in arr if arr.count(a) == 1]
#     return len(arr)

def solution(enter, leave):
    answer = [0] * len(leave)
    tmp = []
    #입실 퇴실 모든 과정을 tmp에 저장한다
    for l in leave:
        if l not in tmp:
            tmp += enter[:enter.index(l)+1] # 첫번째로 퇴실하는 사람이 입실할때까지 
            enter = enter[enter.index(l)+1:] #입실한 사람들 제거
        tmp.append(l)
    #모든 입실 퇴실 과정을 바탕으로  
    for i in range(1,len(leave)+1):
        start_index = tmp.index(i,0)
        end_index = tmp.index(i,start_index+1)
        if end_index - start_index == 1: #입실 퇴실이 연속으로 일어났을때
            answer[i-1] += get(tmp[:start_index])
        else:
            arr_set = list(set(tmp[start_index+1:end_index]))
            answer[i-1] += len(arr_set) #입실과 퇴실 사이에 들어온 사람
            arr = [a for a in tmp[:start_index] if a not in arr_set]
            answer[i-1] += get(arr) #입실 전에 들어와있던 사람
    return answer

• 다른 사람 풀이. 로직이 아주 깔꿈.

def solution(enter, leave):
    answer = [0] * len(enter)
    room = []
    e_idx = 0
    for l in leave:
        while l not in room: # 퇴실할 사람이 방에 들어올때까지 입실
            room.append(enter[e_idx])
            e_idx += 1
        room.remove(l) # 퇴실할 사람이 방에 들어온다면 해당 사람을 퇴실시킨다.
        for p in room: 
            answer[p - 1] += 1 # 현재 방에 있는 사람들이 만난 사람 수에 1씩 더해준다.
        answer[l - 1] += len(room) # 퇴실한 사람의 만난 사람 수에 현재 방 인원수를 더해준다.
    return answer

14.프로그래머스 - 쿼드압축 후 개수 세기

소요시간: 해결 못함
-> 함수 안에 함수
-> 블럭 별로 함수를 불러보장

def solution(arr):
    answer = [0,0]
    l = len(arr)
    def check(a,b,n):
        target = arr[a][b]
        for i in range(a,a+n):
            for j in range(b,b+n):
                if target != arr[i][j]:
                    n = n // 2
                    check(a,b,n)
                    check(a,b+n,n)
                    check(a+n,b,n)
                    check(a+n,b+n,n)
                    return
        answer[target] += 1
    check(0,0,l)
    return answer

15. 프로그래머스 - n진수 게임

소요시간: 20분

import string

def convert(num, base):
    tmp = string.digits+string.ascii_uppercase
    q, r = divmod(num, base)
    if q == 0 :
        return tmp[r] 
    else :
        return convert(q, base) + tmp[r]
    
def solution(n, t, m, p):
    tmp = ''
    answer = ''
    
    num = 0
    while len(tmp) < m * t:
        tmp += str(convert(num, n))
        num += 1
        
    for i in range(t):
        answer += tmp[p-1 + m * i] 
    
    return answer

16. 프로그래머스 - 점프와 순간 이동

소요시간: 40분이내에 못 품..
절반으로 줄여볼 생각은 했는데 홀수일때, -1하고 이어 갈 생각을 못했네..

def solution(n):
    ans = 0
    while n != 0:
        if n % 2 == 0:
            n = n // 2
        else:
            n -= 1
            ans += 1
    return ans

17. 프로그래머스 - 예산

소요시간: 5분 , 레벨1이었습니다

def solution(d, budget):
    answer = 0
    d = sorted(d)
    
    for m in d:
        if budget == 0:
            return answer
        if budget - m >= 0:
            budget -= m
            answer += 1
    return answer

18. 프로그래머스 - 스티커 모으기(2)

- 해결 못함

소요시간: 1시간 반 이상, 레벨3
기본 테케만 정답..dp를 이용했어야 했다..

def odd_index(arr):
    return [arr[i] for i in range(len(arr)) if i % 2 !=0]

def even_index(arr):
    return [arr[i] for i in range(len(arr)) if i % 2 == 0]

def compare_arr(arr):
    a = sum([arr[i] for i in range(len(arr)) if i % 2 !=0])
    b = sum([arr[i] for i in range(len(arr)) if i % 2 == 0])
    return max(a,b)
    
def solution(sticker):
    answer = 0
    if len(sticker) == 1:
        return sticker[0]
    
    if len(sticker) % 2 == 0:
        return compare_arr(sticker)
    else:
        a = sum(odd_index(sticker))
        b1 = sticker[0] + compare_arr(sticker[2:-1])
        b2 = sticker[-1] + compare_arr(sticker[1:-2])
        return max(a, b1, b2)

19. 프로그래머스 - 멀쩡한 사각형

-> 다시 풀어보자
최대공약수,,,가끔씩 튀어나오는 해결법

import math

def solution(w,h):
    return w * h - (w + h - math.gcd(w,h))

20. 프로그래머스 - 기지국 설치

소요시간 : 30-40분(시간초과 제외)
시간초과해서 해결못합. O(n)으로 해결해야 한다.

#시간초과
def solution(n, stations, w):
    answer = 0
    s = []
    for station in stations:
        s += [num for num in range(station-w,station+w+1) if 1 <= num <= n]
    s.append(n+1)

    tmp = 0
    for index in range(1, n+2):
        if index not in s:
            tmp += 1
        elif tmp > 0:
            answer += tmp // (w * 2 + 1)
            if tmp % (w * 2 + 1) != 0:
                answer += 1
            tmp = 0
    return answer

21. 프로그래머스 - 숫자 게임

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    
    i = 0
    for j in range(len(B)):
        if A[i] < B[j]:
            i += 1
            j += 1
            answer += 1
        else:
            j += 1
            
    
    return answer

22. 프로그래머스 - 행렬 테두리 회전하기

소요시간: 몇일..?ㅋㅋ
방향벡터를 이용해서 회전.
나중에 다시 풀어보기!!

def solution(rows, columns, queries):
    answer = []
    arr = [[0] * columns for _ in range(rows)]
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    
    num = 1
    for i in range(rows):
        for j in range(columns):
            arr[i][j] = num
            num += 1
    
    for a,b,c,d in queries:
        a,b,c,d = a-1,b-1,c-1,d-1
        x,y = a,b
        cur = arr[x+1][y]
        minValue = cur
        n = (c - a + 1) * 2 + (d - b + 1 - 2) * 2
        direction = 0

        for i in range(n):
            tmp = arr[x][y]
            arr[x][y] = cur
            cur = tmp
            minValue = min(cur,minValue)
            x += dx[direction]
            y += dy[direction]
            
            if not (b <= y <= d and a <= x <= c):
                x -= dx[direction]
                y -= dy[direction]
                direction = (direction + 1) % 4
                x += dx[direction]
                y += dy[direction]
        answer.append(minValue)

    return answer

23. 프로그래머스 - 삼각 달팽이

def solution(n):
    answer = []
    maxLen = [num for num in range(1,n+1)]
    tmp = [[0] * n for _ in range(n)]
    dr = [1,0,-1,1]
    dc = [0,1,0,-1]
    
    target = 0
    for num in range(1, n+1):
        target += num
    r,c = 0,0
    num = 1
    direction = 0
    while num <= target:
        tmp[r][c] = num
        r += dr[direction] 
        c += dc[direction] 
        if not (0 <= r < n and 0 <= c < n) or tmp[r][c] != 0 or n - tmp[r].count(0) >= maxLen[r]:
            r -= dr[direction] 
            c -= dc[direction]
            direction = (direction + 1) % 4
            if direction == 0:
                direction += 1
            r += dr[direction] 
            c += dc[direction]
        num += 1

    for t in tmp:
        for i in t:
            if i == 0:
                continue
            answer.append(i)
    return answer    

24. Hacker rank - Simple Text Editor

S = ''
Q = int(input())
tmp = []
for i in range(Q):
    ops = input().split(' ')
    if ops[0] == '1':
        tmp.append(S)
        S += ops[1]
    elif ops[0] == '2':
        tmp.append(S)        
        S = S[:-int(ops[1])]
    elif ops[0] == '3':
        print(S[int(ops[1]) - 1])
    elif ops[0] == '4':
        S = tmp.pop()

25. 프로그래머스 - n*2 배열 자르기

• 생각지도 못한 풀이법....ㅜ
• divmod(i,n)
  - 튜플 형태로 반환, unpacking하고 싶다면 *divmod(i,n)
• i//n, i%n

def solution(n, left, right):
    answer = []
    
    for i in range(left, right+1):
        # print(divmod(i, n))
        answer.append(max(divmod(i, n)) + 1)
    # print(answer)
    return answer

26. 프로그래머스 - 스킬트리

def solution(skill, skill_trees):
    answer = 0
    for skills in skill_trees:
        tmp = []
        flag = True
        tmp_skill = list(skill)
        for s in skills:
            if s in skill:
                if s != tmp_skill.pop(0):
                    flag = False
                    break
        #         tmp.append(skill.index(s))
        # if flag and sorted(tmp) == tmp:
        #     answer += 1
        else:
            answer += 1
    return answer