AndroidTeacher

https://www.acmicpc.net/problem/3190

문제 설명

뱀 꼬리물기 문제이다. 뱀이 사과를 먹으면 점점 꼬리를 늘려가게 되며

뱀의 머리가 꼬리에 닿거나 벽에 닿으면 끝나는 게임이다.

뱀의 꼬리를 이동시키는 부분을 큐로 구현하는 부분이 핵심이다.

풀이 과정

이 문제는 큐를 이용한 구현 문제로 다음과 같이 접근하였다.

① 먼저 그래프(맵)을 모두 0으로 채워준다.

② 사과 위치는 모두 2로 채워준다.

③ 앞으로 뱀이 차지하고 있는 부분은 1로 채워줄 것이다.

④ 뱀이 이동할 때 마다 머리와 꼬리는 한 칸씩 전진한다. (즉, 몸의 길이는 그대로이다.)

⑤ 이동했을 때 사과를 먹으면 머리는 전진하지만 꼬리는 그대로이다. (즉, 몸의 길이가 한 칸 늘어난다.)

⑥ 방향 전환을 해야 하는 타이밍에 맞춰 L이면 왼쪽, D이면 오른쪽으로 방향전환을 한다.

이렇게 무엇을 구현해야 할 지를 정리한 후에 이를 하나씩 차례차례 구현해주면 된다.

①②③ 은 그대로 구현을 하면 되기 때문에 따로 설명은 하지 않고

④의 경우에는 처음 시작 할 때, [0, 0]을 큐에 넣어 몸길이 1 뱀의 초기 위치 상태를 저장하고,

오른쪽으로 한 칸 이동하여 [0, 0]을 큐에서 pop하고

[0, 1]을 큐에 push하여 뱀의 위치 상태를 변경한다.

이런 식으로 뱀을 전진시키면 된다. ( 큐를 뱀의 몸을 나타낸다고 생각하면 된다. )

⑤의 경우는 graph[x][y] = 2일 때 이다. 머리만 전진하면 되므로 큐에서 pop을 하지 않고,

큐에 현재 머리 위치만 push함으로써 뱀의 몸 길이를 늘려준다.

⑥의 경우에는 현재 시간이 방향전환을 해야 하는 시간이면, 입력한 방향에 맞게 전환을 해주면 된다.

(딕셔너리를 이용해 시간을 키값으로, 방향을 밸류값으로 입력받았다.)

이를 코드로 나타내면 다음과 같다.

from collections import deque

n = int(input())
k = int(input())

graph = [[0] * n for _ in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

for i in range(k):
    a, b = map(int, input().split())
    graph[a - 1][b - 1] = 2

l = int(input())
dirDict = dict()
queue = deque()
queue.append((0, 0))

for i in range(l):
    x, c = input().split()
    dirDict[int(x)] = c

x, y = 0, 0
graph[x][y] = 1
cnt = 0
direction = 0

def turn(alpha):
    global direction
    if alpha == 'L':
        direction = (direction - 1) % 4
    else:
        direction = (direction + 1) % 4


while True:
    cnt += 1
    x += dx[direction]
    y += dy[direction]

    if x < 0 or x >= n or y < 0 or y >= n:
        break

    if graph[x][y] == 2:
        graph[x][y] = 1
        queue.append((x, y))
        if cnt in dirDict:
            turn(dirDict[cnt])

    elif graph[x][y] == 0:
        graph[x][y] = 1
        queue.append((x, y))
        tx, ty = queue.popleft()
        graph[tx][ty] = 0
        if cnt in dirDict:
            turn(dirDict[cnt])

    else:
        break

print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/2504

문제 설명

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

풀이 과정

열린 괄호를 만나면 스택에 넣어주고 닫힌 괄호를 만나면 스택의 TOP을 꺼내 쌍을 맞춰주자.

이 때, 쌍이 맞지 않으면 잘못된 괄호 입력이다.

'( ( [ ] ) )' 라는 입력이 들어왔다면,

스택에 ' ( ( [ ' 가 있는 상태로 ]를 만나 스택의 TOP인 '['를 꺼내 쌍을 이루고

다음으로 ')'를 만나 TOP인 '('를 꺼내 쌍을 이루기 때문에 올바른 쌍을 이룬다.

하지만 '( [ ) ]' 라는 입력이 들어왔다면,

스택에 ' ( [ '가 있는 상태로 ')'를 만나 스택의 TOP인 '['를 꺼낸다면

'['와 ')'은 쌍을 이루지 않기 때문에 잘못된 입력이므로 0을 출력한다.

그리고 '( )' 소괄호의 값은 2이며 '[ ]' 대괄호의 값은 3이고

괄호 안에 또 괄호가 존재하면 값을 곱해나가는 방식이다.

그래서 '(' 괄호가 열리면 2를 곱해주고 '[' 괄호가 열리면 3을 곱해준다.

그리고 괄호를 닫은 경우는 계산한 값을 저장한 후에 누적 계산은 다시 나누기 2나 3을 해주어 원래대로 값을 돌린다.

여기서!

한 가지 주의해야 할 점은 꺼낸 괄호가 닫는 괄호일 때,

괄호 입력 배열에서의 그 괄호의 바로 직전의 괄호가 쌍이 맞는 경우에만 곱하기를 한다.

( stack이 아닌 bracket 배열의 인덱스 )

즉, ' [ ( ) ] ' 처럼 마지막 ' ] ' 의 바로 직전의 괄호가 ' [ ' 가 아닌 ' ) ' 이기 때문에

값을 더해가지 않는다.

여기서 우리가 계산해야 할 것은 3 x 2 = 6인데

앞에서 곱하기 3은 이미 계산을 했기 때문에 뒤에서 더 계산을 하면 안되기 때문이다.

이를 파이썬으로 나타낸 코드는 다음과 같다.

bracket = list(input())

stack = []
answer = 0
tmp = 1

for i in range(len(bracket)):

    if bracket[i] == "(":
        stack.append(bracket[i])
        tmp *= 2

    elif bracket[i] == "[":
        stack.append(bracket[i])
        tmp *= 3

    elif bracket[i] == ")":
        if not stack or stack[-1] == "[":
            answer = 0
            break
        if bracket[i-1] == "(":
            answer += tmp
        stack.pop()
        tmp //= 2

    else:
        if not stack or stack[-1] == "(":
            answer = 0
            break
        if bracket[i-1] == "[":
            answer += tmp

        stack.pop()
        tmp //= 3

if stack:
    print(0)
else:
    print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

programmers.co.kr/learn/courses/30/lessons/12936

문제 설명

입력으로 n과 k를 입력받는다.

1번부터 n번까지 n명의 사람들이 줄을 서 있다.

이 n명의 사람이 줄을 서는 방법에는 여러가지가 있는데, 방법을 사전 순으로 정렬하였을 때 제일 첫 방법을 1번째 방법,

마지막 방법을 n번째 방법이라 하자.

이 때, k번째 방법을 구하면 된다.

풀이 과정

처음 배열(answer)는 1부터 n번까지 차례대로 [1,2,3,...,n]으로 정렬되어 있다.

예시로, n = 4, k = 7이라고 하자. 즉 [1,2,3,4]배열이 이루는 모든 경우의 수에서 7번째 방법을 구하면 된다.

1번째 방법은 [1,2,3,4]

2번째 방법은 [1,2,4,3]

3번째 방법은 [1,3,2,4]... 이런식으로 나타나게 되는데,

각각의 자릿수에 들어가는 숫자는 규칙을 가지고 있다.

가장 앞자리가 1이 되는 경우는 1~6번 방법 까지이다.

왜냐하면 1을 제외한 2,3,4 세개의 숫자가 번갈아가면서 정렬을 하기 때문에 3! = 6이 되는 것이다.

그렇다면 앞자리가 2가 되는 경우는 7~12번 방법 까지일 것이다.

이렇게 앞자리를 결정하고 나면, 결정해야 할 숫자의 수는 하나씩 줄어들게 된다.

위의 n=4, k=7일때를 예로 들면, 처음에는 4! = 24 가지 중에 한 가지로 추려졌지만

이제는 3! = 6 가지 중에 한 가지로 추릴 수가 있는 것이다.

이렇게 줄여나가다 보면 내가 원하는 답을 찾게 된다.

import math


def solution(n, k):
    answer = [i for i in range(1, n + 1)]
    stack = []
    k = k-1


    while answer:
        # k / (n-1)! 을 했을 때의 몫이 맨 첫번째 자리
        a = k // math.factorial(n - 1)
        stack.append(answer[a])
        del answer[a]

        # k를 줄여야함.
        k = k % math.factorial(n - 1)
        n -= 1


    return stack

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

programmers.co.kr/learn/courses/30/lessons/60058

문제 설명

잘못된 괄호를 올바른 괄호 형식으로 바꾸는 문제입니다.

실제 카카오 코딩테스트 기출문제 답게 문제가 상당히 길어서 위 링크를 꼭 확인하시길 바랍니다.

문제에 대한 설명이 위 링크에 자세히 나옵니다!

풀이 과정

스택을 이용한 단순 구현 문제입니다.

해당 설명에 따라서 그대로 구현만 해주시면 특별히 어려움은 없을거에요.

코드에 대해 궁금하신 사항이 있으시면 댓글 남겨주세요!

def step2(p):
    count = 0
    for i in range(len(p)):
        if p[i] == "(":
            count += 1
        else:
            count -= 1
        if count == 0:
            return p[:i+1], p[i+1:]

def step3(u):
    stack = []
    for i in u:
        if i == "(":
            stack.append(i)
        else:
            if not stack:
                return False
            stack.pop()
    return True


def solution(p):
    answer = ''
    #step1
    if not p:
        return ''

    #step2
    u, v = step2(p)

    #step3
    if step3(u):
        return u+solution(v)

    #step4
    #4-1
    answer += "("

    #4-2
    answer += solution(v)

    #4-3
    answer += ")"

    #4-4
    for i in u[1:-1]:
        if i == "(":
            answer += ")"
        else:
            answer += "("
    #4-5
    return answer

print(solution("(()())()"))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/5430

문제 설명

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다.

AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다.

배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다.

예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

풀이 과정

이 문제는 입력을 특이하게 괄호와 쉼표를 모두 포함하여 받는다

즉 "[1,2,3,4]" 이렇게 큰 따옴표 안에 있는 것을 모두 입력 받는다.

하지만 처리는 정수(1,2,3,4)만 해야 하므로 쉼표로 구분을 해줘야 하고, 대괄호는 지워줘야 하기 때문에

[1:-1]범위의 부분만 가져와서 deque를 만들어준다.

하지만 이 때, "[]"라고 입력을 받아도 deque의 길이는 1이 되기 때문에

길이가 0인 부분에 대해서는 예외사항으로 빈 큐로 초기화를 해줘야 한다.

풀이과정은 다음과 같다.

내가 처음 작성한 코드는 1번 코드와 같은데 이 코드는 시간초과 문제가 발생하였다.

Reverse를 해야 할 때마다, 매번 deque를 뒤집어 주었기 때문이다.

그래서 Reverse를 매번 실행하지 않고, 뒤집는 횟수를 기억해두었다가

뒤집는 횟수가 홀수 번 일때만 뒤집도록 수정하였다.

짝수번을 뒤집게 되면 안뒤집는 상황이랑 똑같기 때문이다.

최종적인 코드는 2번 코드와 같다.

1번 코드

import sys
from collections import deque

t = int(input())

for i in range(t):
    p = sys.stdin.readline().rstrip()
    n = int(input())
    arr = deque(sys.stdin.readline().rstrip()[1:-1].split(","))

    if n == 0:
        arr = deque()

    flag = 0
    for j in p:
        if j == 'R':
            arr.reverse()
        elif j == 'D':
            if arr:
                arr.popleft()
            else:
                print("error")
                flag = 1
                break
    if flag == 0:
        print("["+",".join(arr)+"]")

2번 코드

import sys
from collections import deque

t = int(input())

for i in range(t):
    p = sys.stdin.readline().rstrip()
    n = int(input())
    arr = sys.stdin.readline().rstrip()[1:-1].split(",")
    queue = deque(arr)

    rev, front, back = 0, 0, len(queue)-1
    flag = 0
    if n == 0:
        queue = []
        front = 0
        back = 0

    for j in p:
        if j == 'R':
            rev += 1
        elif j == 'D':
            if len(queue) < 1:
                flag = 1
                print("error")
                break
            else:
                if rev % 2 == 0:
                    queue.popleft()
                else:
                    queue.pop()
    if flag == 0:
        if rev % 2 == 0:
            print("[" + ",".join(queue) + "]")
        else:
            queue.reverse()
            print("[" + ",".join(queue) + "]")

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

풀이 과정

처음 문제를 보고 잘못 이해했던 점이, 자신이 뽑으려는 수가 아니더라도 1번을 이용해 큐를 줄여갈 수 있는 줄 알았다. 하지만 자신이 뽑으려는 수가 첫 번째 원소일 때만 1번을 사용하여 원소를 뽑아낼 수 있다.

pick 리스트에는 자신이 뽑고자 하는 원소들의 최초 위치가 들어있다.

큐에는 1부터 N까지의 원소들이 들어있다.

입력한 순서대로 원소를 뽑아내야 하므로 pick[0]이 현재 뽑아내야 할 원소의 최초 위치이다.

그래서 큐의 첫 번째 원소와 pick의 첫 번째 원소가 일치하면 1번 과정을 통해 원소를 뽑아내게 되는 것이다.

그 외의 경우에는 2, 3번의 연산을 반복해야 하는데, 최소한의 연산을 해야하므로

현재 뽑고자 하는 원소가 왼쪽에 더 가까운지 오른쪽에 더 가까운지를 파악하여

2, 3 과정을 선택하여 수행하면 된다. 과정 수행 후에는 횟수를 하나씩 늘려간다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
pick = list(map(int, sys.stdin.readline().split()))

queue = deque([i for i in range(1, n+1)])
cnt = 0


while pick:
    if queue[0] == pick[0]:
        queue.popleft()
        del pick[0]
    else:
        if queue.index(pick[0]) > len(queue) / 2:
            while queue[0] != pick[0]:
                queue.appendleft(queue.pop())
                cnt += 1
        else:
            while queue[0] != pick[0]:
                queue.append(queue.popleft())
                cnt += 1

print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1966

문제 설명

프린터는 FIFO(First In First Out) 즉 선입 선출의 구조로 문서를 출력하게 된다.

하지만 문제의 프린터에는 조건이 있다. 문서마다 중요도가 기록되어 있는데, 자신보다 중요도가 높은 문서가 하나라도 자신의 뒤에 있으면 자신은 맨 뒤로 밀려나게 된다.

예를 들어, A B C D 라는 4개의 문서의 중요도가 2 1 4 3이라면

2가 밀려나고 1이 밀려나고 4가 제일 먼저 출력되어 3 2 1 로 큐가 변경이 되며

여기서 또 3이 출력되고, 2가 출력되고 1이 출력된다.

문제의 각 케이스마다 자신이 설정한 문서가 몇 번째로 출력되는지를 구하면 된다.

풀이 과정

나의 숫자가 남은 큐 중에서 가장 큰 수가 될 때 까지 검사를 실시하면 된다.

그리고 자신의 문서의 인덱스를 m을 통해 변화를 주게 되며,

count를 통해 몇 번째로 빠져나갔는지 카운트하면 된다.

from collections import deque
import sys

t = int(input())

for i in range(t):
    n, m = map(int, input().split())
    queue = deque(list(map(int, sys.stdin.readline().split())))
    count = 0
    while queue:
        best = max(queue)  #현재의 최댓값이 가장 먼저 배출되므로 최댓값을 저장
        front = queue.popleft() # 큐의 front를 뽑았으므로
        m -= 1 # 내 위치가 한 칸 당겨진다.

        if best == front: # 뽑은 숫자가 제일 큰 숫자일 때
            count += 1 # 하나가 영원히 배출되므로 순번 하나 추가
            if m < 0: # m이 0이라는 것은 뽑은 숫자가 내 숫자라는 뜻.
                print(count)
                break

        else:   # 뽑은 숫자가 제일 큰 숫자가 아니면
            queue.append(front) # 제일 뒤로 밀려나게 됨
            if m < 0 :  # 제일 앞에서 뽑히면
                m = len(queue) - 1 # 제일 뒤로 이동

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/11866

문제 설명

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

풀이 과정

N = 7, K = 3 이라면 1번부터 7번까지의 사람들 중 1번을 시작으로 3번째 순서에 있는 사람이 제거가 된다.

즉 3번이 먼저 제거가 되는 것이다.

그 다음은 4부터 시작하여 다시 3번째 사람이 제거가 된다. 즉 6이 제거가 된다.

이 문제는 큐 자료구조로 해결할 수 있다.

K-1번째 까지의 사람들이 앞에서 부터 제거가 된 후 다시 큐의 뒤로 돌아오며

K번째 사람은 완전히 제거가 되는 것이다.

그래서 popleft를 통해 앞에서 부터 제거를 한 후 뒤에 다시 append를 해주면 된다.

from collections import deque

queue = deque()
answer = []

n, k = map(int, input().split())

for i in range(1, n+1):
    queue.append(i)

while queue:
    for i in range(k-1):
        queue.append(queue.popleft())
    answer.append(queue.popleft())

print("<",end='')
for i in range(len(answer)-1):
    print("%d, "%answer[i], end='')
print(answer[-1], end='')
print(">")

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !