그냥 코딩하는 사람의 블로그

풀이 과정

0. 문자열을 소문자로 변환

1. 문자열의 왼쪽에서부터 숫자를 만날때까지 탐색(HEAD)

2. 숫자 만난 시점에서부터 숫자를 만나지 않는 시점까지 탐색(NUMBER)

3. [HEAD, NUMBER, 원래 문자열, 인덱스] 순으로 임시로 저장

4. HEAD, NUMBER, 인덱스 순으로 정렬(인덱스 순으로 정렬하는 이유는 원래 입력에 주어진 순서를 유지해야 하기 때문)

5. 순차적으로 원래 문자열을 정답 리스트에 저장

import re

def get_str(name):
    s = ""
    pos = 0
    for i in range(len(name)):
        if name[i].isdigit():
            pos = i
            break
        s += name[i]

    return (s, pos)

def get_num(name, start):
    pos = 0
    for i in range(start, len(name)):
        if not name[i].isdigit():
            pos = i
            break

    if pos == 0:
        pos = len(name)

    return pos

def solution(files):
    answer = []
    filelist = []
    for idx, file in enumerate(files):
        fileorg = file
        file = file.lower()
        head, src = get_str(file)
        dest = get_num(file, src)
        number = file[src:dest]
        filelist.append([head, number, fileorg, idx])

    filelist.sort(key=lambda x:(x[0], int(x[1]), x[3]))

    for f in filelist:
        answer.append(f[2])

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 현재 문자 기준으로 오른쪽으로 문자 한개씩 늘려가며 슬라이싱 후 딕셔너리에서 찾아 봄.

2. 가장 길게 매칭되어야 하므로 딕셔너리에서 찾지 못할때까지 한개씩 늘려감.

3. 찾지 못한다면 [현재 시점 ~ 찾지 못한 시점] 까지의 문자열을 딕셔너리에 넣어준 후, 찾지 못한 시점으로 점프해주면 된다. 단, 여기서 찾지 못한 시점을 찾을수 없는 경우(현재~끝까지 매칭됨) 딕셔너리에 넣어준 후 종료한다.

4. 위 과정을 전체 문자열에 적용한다.

def solution(msg):
    words = {chr(i):idx+1 for idx, i in enumerate(range(ord('A'), ord('Z')+1))}
    posfrom = 0
    nextidx = 27
    answer = []
    nextpos = 0

    while True:
        check = False
        for i in range(posfrom+1, len(msg)+1):
            if words.get(msg[posfrom:i]) == None:
                check = True
                words[msg[posfrom:i]] = nextidx
                nextpos = i-1
                nextidx += 1
                break

        if check:
            answer.append(words[msg[posfrom:nextpos]])
        else:
            answer.append(words[msg[posfrom:]])
            break

        posfrom = nextpos          

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 문자열을 순차적으로 접근

2. (를 만나면 스택에 넣음.

3. )를 만나면 스택에서 뺌, 이 때, 스택이 비어있다면 잘못된 괄호 문자열

4. 과정이 모두 끝났을때 스택이 비어있지 않다면 (가 더 많이 나온것이므로 잘못된 괄호 문자열

from collections import deque

def solution(s):
    queue = deque()
    for c in s:
        if c == '(':
            queue.append('(')
        else:
            if len(queue) == 0:
                return False
            queue.popleft()

    if queue:
        return False

    return True

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 행이 10만개나 가능하므로 탐색문제로 해결하면 시간초과

2. 따라서 dp를 활용하여 문제를 해결함.

3. i행 j열의 경우, 이전 행에서 j열을 제외한 나머지 열중 최댓값 + i행 j열의 값으로 대체

import copy
def solution(land):
    dp = copy.deepcopy(land)

    for i in range(1, len(land)):
        for j in range(len(land[0])):
            for k in range(len(land[0])):
                if k == j:
                    continue
                dp[i][j] = max(dp[i][j], dp[i-1][k] + land[i][j])

    return max(dp[len(land)-1])

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 시간을 분단위로 변환 / 정규 표현식 활용하여 악보를 요소 하나하나씩 담긴 리스트로 변환

2. 정렬(분단위로 변환하였으니 종료시간 - 시작시간으로 내림차순, 시작시간으로 오름차순)

3. m도 정규 표현식 활용하여 리스트 변환 / 순차적으로 접근하면서 비교

import re
def solution(m, musicinfos):
    answer = ''

    infos = []

    # 시간 분단위로 변환 
    for musicinfo in musicinfos:
        info = musicinfo.split(',')
        stmin = 60 * int(info[0][0:2]) + int(info[0][3:5])
        fimin = 60 * int(info[1][0:2]) + int(info[1][3:5])
        title = re.findall('A#|C#|D#|F#|G#|[A|B|G|F|E|D|C]', info[3])
        it = (fimin - stmin) // len(title)
        k = (fimin - stmin) % len(title)
        infos.append([stmin, fimin, info[2], title * it + title[:k]])

    # 재생시간, 시작시간 순 정렬
    infos.sort(key=lambda x:(-(x[1]-x[0]), x[0]))
    m = re.findall('A#|C#|D#|F#|G#|[A|B|G|F|E|D|C]', m)
    length = len(m)

    # 문자열 비교 파트
    for i in range(len(infos)):
        for j in range(len(infos[i][3]) - length + 1):
            count = 0
            for k in range(len(m)):
                if m[k] == infos[i][3][j+k]:
                    count += 1

            if count == length:
                answer = infos[i][2]
                break

        if answer != '':
            break


    if answer == '':
        answer = '(None)'

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 방법

1. recursion을 사용하게 되면 n이 100000 이하이므로 불가능

2. 따라서 a, b, c를 두어, c는 a+b, a는 b, b는 c 이런식으로 진행하여 계산량 최소화

3. 마지막에 1234567로 나눈 나머지 수를 리턴해주면 된다.

def solution(n):
    answer = 0
    a = 0
    b = 1
    c = 1
    if n == 1:
        return 1

    for i in range(2, n+1):
        c = a + b
        a = b
        b = c

    answer = c % 1234567
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 최대 길이가 -55이므로.. 현재 위치를 (5,5)로 두고 010으로 제한한다.

2. 방문 체크를 위해 set을 사용. set에는 리스트를 넣을수 없어서 Tuple로 변환하여 set에 넣어준다.

=> (현재x, 현재y, 이동x, 이동y)

=> (이동x, 이동y, 현재x, 현재y)

* 처음 걸어본 길의 길이이므로 이동한 길을 통해 반대에서 이곳으로 돌아오는 케이스도 있기 때문에 두가지 케이스를 넣어준다.

3. 길이 막혀있는지, 막혀있지 않다면 방문한 길인지를 체크하면서 처음 걸어본 길의 길이를 1씩 증가시킨다.

def solution(dirs):
    answer = 0

    path = set()
    pos = [5, 5]
    for d in dirs:
        if d == 'U' and pos[0] > 0:
            if tuple([pos[0], pos[1], pos[0]-1, pos[1]]) not in path:
                path.add(tuple([pos[0], pos[1], pos[0]-1, pos[1]]))
                path.add(tuple([pos[0]-1, pos[1], pos[0], pos[1]]))
                answer += 1
            pos[0] -= 1
        elif d == 'L' and pos[1] > 0:
            if tuple([pos[0], pos[1], pos[0], pos[1]-1]) not in path:
                path.add(tuple([pos[0], pos[1], pos[0], pos[1]-1]))
                path.add(tuple([pos[0], pos[1]-1, pos[0], pos[1]]))
                answer += 1
            pos[1] -= 1
        elif d == 'R' and pos[1] < 10:
            if tuple([pos[0], pos[1], pos[0], pos[1]+1]) not in path:
                path.add(tuple([pos[0], pos[1], pos[0], pos[1]+1]))
                path.add(tuple([pos[0], pos[1]+1, pos[0], pos[1]]))
                answer += 1
            pos[1] += 1
        elif d == 'D' and pos[0] < 10: 
            if tuple([pos[0], pos[1], pos[0]+1, pos[1]]) not in path:
                path.add(tuple([pos[0], pos[1], pos[0]+1, pos[1]]))
                path.add(tuple([pos[0]+1, pos[1], pos[0], pos[1]]))
                answer += 1
            pos[0] += 1
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 현재 검사하려는 영역을 검사한다.

2. 현재 검사하려는 영역이 압축이 되지 않는다면 영역을 왼쪽위, 왼쪽아래, 오른쪽아래, 오른쪽 위로 4개 분할하여 재귀함수를 호출한다.

3. 영역의 크기가 1x1인 경우에는 하나의 영역으로 간주하고 종료

4. 영역이 압축이 된다면 무슨 영역인지 카운팅 해주고 종료

import sys

count = [0, 0]

sys.setrecursionlimit(10**6)

def check(arr, x1, y1, x2, y2):
    t = arr[x1][y1]
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            if arr[i][j] != t:
                return False

    return True

def f(arr, x1, y1, x2, y2):
    if check(arr, x1, y1, x2, y2):
        t1 = arr[x1][y1]
        count[t1] += 1
        return

    if x1 == x2 and y1 == y2:
        count[arr[x1][y1]] += 1
        return

    midX = (x1 + x2) // 2
    midY = (y1 + y2) // 2

    f(arr, x1, y1, midX, midY) # 왼위
    f(arr, midX+1, y1, x2, midY) # 왼아
    f(arr, midX+1, midY+1, x2, y2) # 오아
    f(arr, x1, midY+1, midX, y2) # 오위

def solution(arr):
    answer = []
    t = len(arr)
    f(arr, 0, 0, t-1, t-1)
    return count

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. 각각의 케이스마다 선행 스킬 순서(skill)을 queue로 만들어 준다.

2. 각 스킬트리를 문자 순서대로 진행하면서 해당 문자가 선행 스킬 순서 내에 있는지, 있다면 queue의 맨 앞에 있는지를 검사한다.

3. queue의 맨 앞에 없다면, 먼저 나와야 하는 스킬이 아니므로 잘못된 것이므로 break

4. queue의 맨 앞에 있다면, 먼저 나와야 하는 스킬이 맞으므로 queue에서 빼준 다음 다음 문자에 대해 계속 진행한다.

5. 만족하는 스킬 트리의 개수를 리턴하면 된다.

from collections import deque

def solution(skill, skill_trees):
    answer = 0
    for sk in skill_trees:
        queue = deque(skill)
        flag = True
        for s in sk:
            if s in queue:
                if queue[0] == s: # 선행스킬이면 큐에서 빼줌
                    queue.popleft()
                else: # 선행스킬이 아니라면 잘못된 것이므로 false
                    flag = False
                    break

        if flag:
            answer += 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이과정

1. 1의 개수를 카운트해준다. 이 때 0의 개수도 같이 카운팅

2. 1의 개수의 길이를 bin 함수를 사용하여 2진수 형태로 변환

3. 해당 결과값이 1일때까지 반복.

4. 몇번 진행하였는지, 몇개의 0을 제거하였는지 리턴

def convert(s):
    return bin(s)[2:]

def solution(s):
    answer = []
    zero = 0
    step = 0
    while True:
        temp = []
        for n in s:
            if n == '0':
                zero += 1
            else:
                temp.append(n)

        t = convert(len(temp))
        step += 1
        s = t
        if s == '1':
            break

    answer = [step, zero]
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges