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

풀이 과정

1. 참가자들이 어디에 있는지 위치를 모두 저장

2. 각각의 참가자 기준으로 bfs를 진행

   • 현재 위치 기준 거리 2 이내에 사람이 있는지 검사.
   • 칸막이가 있다면 그방향은 방문 x

3. 참가자들중 한명이라도 실패하면 0, 모두 성공하면 1 저장

from collections import deque

def check(place, x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    queue = deque()
    queue.append([x, y, 0])
    visited = set()
    visited.add(tuple([x, y]))
    while queue:
        a, b, c = queue.popleft()
        if c == 2:
            continue
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx >= 0 and nx <= len(place)-1 and ny >= 0 and ny <= len(place[0])-1:
                if tuple([nx, ny]) not in visited:
                    visited.add(tuple([nx, ny]))
                    if place[nx][ny] == 'P':
                        return False
                    if place[nx][ny] == 'X':
                        continue
                    queue.append([nx, ny, c+1])

    return True


def solution(places):
    answer = []

    for place in places:
        people = []
        for i in range(len(place)):
            for j in range(len(place[0])):
                if place[i][j] == 'P':
                    people.append([i, j])

        flag = True
        for x, y in people:
            if not check(place, x, y):
                flag = False
                break

        if flag:
            answer.append(1)
        else:
            answer.append(0)


    return answer

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

문제 설명

풀이 과정

1. 현재 값의 2진수 변환한 결과의 1의 개수를 구함.

2. 현재 값 + 1 ~ 1000000까지의 수를 순차적으로 방문하면서 2진수 변환 및 2진수 개수 비교

3. 같으면 바로 종료 

def getonecount(n):
    result = 0
    while(n > 0):
        if n%2 == 1:
            result += 1
        n = n // 2
    return result

def solution(n):
    answer = 0
    oc = getonecount(n)
    for i in range(n+1, 1000000):
        if oc == getonecount(i):
            answer = i
            break
    
    return answer

풀이 과정

1. 진법 변환을 할때 2진법~16진법까지 가능하므로 매칭되는 배열을 만들어줌. [0] = 0, ... [10] = A, [11] = B, ... , [15] = F

2. 나누었을 때 나머지들만 붙여서 진법 변환

3. 최대 인원이 100명이고, 튜브가 구할 숫자의 최대 갯수는 1000개이므로 여유있게 10만개정도의 숫자 진법 변환

4. 이후 튜브의 순서에 맞추어서 값들을 하나씩 꺼내오면 된다.

def convert(num, scale):
    match = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
            'A', 'B', 'C', 'D', 'E', 'F']

    if num == 0:
        return '0'

    result = ''
    while num > 0:
        result = match[num % scale] + result
        num = num // scale

    return result

def solution(n, t, m, p):
    answer = ''
    temp = ' '
    for i in range(0, 100000): # 여유있게 10만개정도 변환해서 붙여둠
        temp += convert(i, n)

    for i in range(p, len(temp), m): # 문자열 붙임
        answer = answer + temp[i]
        if len(answer) == t:
            break

    return answer

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

풀이 과정

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