[백준] 15501번 부당한 퍼즐

[백준] 15501번 부당한 퍼즐

출처: [백준] 15501번 부당한 퍼즐


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 1224 493 313 43.961%

문제

현욱은 퍼즐 게임을 굉장히 좋아한다. 어느 날 현욱은 친구로부터 간단한 플래시 퍼즐 게임을 하나 추천 받았는데, 이 퍼즐 게임은 다음과 같은 규칙을 갖고 있다.

  1. 플레이어는 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열을 하나 가지고 시작한다.
  2. 또 다른 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열이 주어졌을 때, 처음 수열을 적절히 변형해서 처음 받은 수열을 이 수열과 동일한 수열로 만들어야 한다.
  3. 이때, 플레이어가 수열에 대해서 할 수 있는 동작은 다음 두 가지가 있다. 동작은 몇 번이라도 수행할 수 있다.
    • 뒤집기 : 현재 수열을 거꾸로 뒤집는다. ex) 1 2 3 4 5 -> 5 4 3 2 1
    • 밀기 : 현재 수열을 왼쪽 혹은 오른쪽으로 한 칸 민다. ex) 1 2 3 4 5 -> 5 1 2 3 4

퍼즐을 풀던 현욱은 분명히 엄청 쉬운 규칙인데도 불구하고 문제가 안 풀려서, 한참을 고민하다가 다시 잘 비교해보니 정답 수열을 주어진 동작만으로는 절대 만들 수가 없는 문제였다!

화가 난 현욱은 퍼즐 제작자에게 따지기 위해 주어진 문제가 올바른 문제인지 아닌지 확인하는 프로그램을 만들기로 결심했다. 현욱을 도와 괘씸한 퍼즐 제작자를 응징해주자.


입력

첫째 줄에 n이 주어진다(1 ≤ n ≤ 1,000,000).

둘째 줄에 1에서 n까지의 수가 한 번만 나타나는 수열이 순서대로 주어진다.

셋째 줄에 주어진 두 연산을 수행해서 구성할 수 있는지 확인할 1에서 n까지 수가 한 번만 나타나는 수열이 순서대로 주어진다.


출력

주어진 두 가지 연산만을 가지고 처음 수열을 결과 수열로 만들 수 있다면 good puzzle, 아니면 bad puzzle을 출력한다.


예제 입력 1

1
2
3
5
1 2 3 4 5
4 3 2 1 5

예제 출력 1

1
good puzzle

예제 입력 2

1
2
3
5
1 2 3 4 5
1 2 4 3 5

예제 출력 2

1
bad puzzle

출처


알고리즘 분류


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys

input = sys.stdin.readline

N = int(input())
sequence = list(map(int, input().split()))
compare = list(map(int, input().split()))

# 순방향
first_idx = compare.index(sequence[0]) # 기준점
new_list1 = compare[first_idx:] + compare[:first_idx]

# 역방향
compare = compare[::-1]
first_idx = compare.index(sequence[0]) # 기준점
new_list2 = compare[first_idx:] + compare[:first_idx]

# 둘 중 하나 맞으면 good puzzle
if sequence == new_list1 or sequence == new_list2:
print("good puzzle")
else:
print("bad puzzle")

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import sys

input = sys.stdin.readline

N = int(input())
sequence = list(map(int, input().split()))
compare = list(map(int, input().split()))

new_list1 = []
new_list2 = []

first_idx = compare.index(sequence[0]) # 기준점

# 순방향인 경우
start = first_idx - N
end = first_idx

for i in range(start, end):
new_list1.append(compare[i])

# 역방향인 경우
start = first_idx
end = first_idx - N

for i in range(start, end, -1):
new_list2.append(compare[i])

# 둘 중 하나 맞으면 good puzzle
if sequence == new_list1 or sequence == new_list2:
print("good puzzle")
else:
print("bad puzzle")

'''
5
1 2 3 4 5
3 4 5 1 2

6
1 2 3 4 5 6
3 2 1 6 5 4
4 5 6 1 2 3

11
11 10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10 11

'''

[백준] 3190번 뱀

[백준] 3190번 뱀

출처: [백준] 3190번 뱀


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 36404 14381 9512 37.674%

문제

‘Dummy’ 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.


입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 ‘L’) 또는 오른쪽(C가 ‘D’)로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.


출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력 1

1
9

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

예제 출력 2

1
21

예제 입력 3

1
2
3
4
5
6
7
8
9
10
11
12
10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

예제 출력 3

1
13

출처


알고리즘 분류


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
board = [[0] * (N) for _ in range(N)] # NxN 보드 생성

K = int(input()) # 사과 개수
for _ in range(K): # 사과 위치 지정 0:없음, 1:있음
y, x = map(int, input().split())
board[y - 1][x - 1] = 2

# 우, 하, 좌, 상 // 시계방향
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

L = int(input()) # 방향 전환 횟수
times = deque()
directions = deque()
for _ in range(L):
time, dire = input().rstrip().split()
times.append(int(time))
directions.append(dire)

count = 0
direction = 0
nx, ny = 0, 0 # 초기위치
visited = deque([[ny, nx]])

while True:
count += 1
# 칸 이동
nx += dx[direction]
ny += dy[direction]
if 0 <= nx < N and 0 <= ny < N and board[ny][nx] != 1: # 보드 체크
# 사과가 있으면 그냥 추가, 없으면 꼬리 제거하고 추가
if board[ny][nx] == 0: # 사과가 없으면
temp_y, temp_x = visited.popleft()
board[temp_y][temp_x] = 0 # 꼬리 줄어듬
board[ny][nx] = 1
visited.append([ny, nx])

else:
print(count)
exit(0)

if count in times:
dire = directions.popleft()
if dire == 'D':
direction += 1
if direction > 3:
direction = 0
else:
direction -= 1
if direction < 0:
direction = 3

[백준] 1021번 회전하는 큐

[백준] 1021번 회전하는 큐

출처: [백준] 1021번 회전하는 큐


문제

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

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

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

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


입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.


출력

첫째 줄에 문제의 정답을 출력한다.


예제 입력 1

1
2
10 3
1 2 3

예제 출력 1

1
0

예제 입력 2

1
2
10 3
2 9 5

예제 출력 2

1
8

예제 입력 3

1
2
32 6
27 16 30 11 6 23

예제 출력 3

1
59

예제 입력 4

1
2
10 10
1 6 3 2 7 9 8 4 10 5

예제 출력 4

1
14

힌트


출처


알고리즘 분류


시간 제한


풀이


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
pick_list = list(map(int, input().split()))
count = 0

num_list = deque([x for x in range(1, N + 1)])

for i in range(M):
num_len = len(num_list)
num_index = num_list.index(pick_list[i])

if num_index < num_len - num_index: # 왼쪽에 가까우면
while True:
if num_list[0] == pick_list[i]:
num_list.popleft()
break
else:
num_list.rotate(-1)
count += 1
else: # 오른쪽에 가까우면
while True:
if num_list[0] == pick_list[i]:
num_list.popleft()
break
else:
num_list.rotate(1)
count += 1

print(count)

[백준] 5430번 AC

[백준] 5430번 AC

출처: [백준] 5430번 AC


문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, “AB”는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, “RDD”는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다.

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


입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,…,xn]과 같은 형태로 배열에 들어있는 수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.


출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

예제 출력 1

1
2
3
4
[2,1]
error
[1,2,3,5,8]
error

힌트


출처


알고리즘 분류


시간 제한


풀이


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import sys
from collections import deque

T = int(input())

for _ in range(T):
comm = input()
N = int(sys.stdin.readline())

temp = input()[1:-1]
if ',' not in temp and temp != "":
num_list = deque([int(temp)])
elif temp != "":
num_list = deque(map(int, temp.split(',')))
else:
num_list = deque()

flag = True
cnt = 0 # Reverse의 개수

for i in range(len(comm)):
if comm[i] == "R":
cnt += 1
else:
if len(num_list) == 0:
flag = 0
break

if cnt % 2 == 0:
num_list.popleft()
else:
num_list.pop()

if cnt % 2 == 1:
num_list.reverse()

if flag:
print("[", end="")
for i in range(len(num_list)):
if i == len(num_list) - 1:
print(num_list[i], end="")
else:
print(str(num_list[i]) + ",", end="")
print("]")
else:
print('error')

[백준] 1966번 프린터 큐

[백준] 1966번 프린터 큐

출처: [백준] 1966번 프린터 큐


문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

  1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
  2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.


입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.


출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.


예제 입력 1

1
2
3
4
5
6
7
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

예제 출력 1

1
2
3
1
2
5

힌트


출처


링크


알고리즘 분류


시간 제한


풀이


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
N, M = map(int, input().split())
priority_list = list(map(int, input().split()))
docs_list = list(range(len(priority_list)))
docs_list[M] = 'target'

order = 0

while True:
num = priority_list[0]
if num == max(priority_list):
order += 1

if docs_list[0] == 'target':
print(order)
break
else:
priority_list.pop(0)
docs_list.pop(0)
else:
priority_list.append(priority_list.pop(0))
docs_list.append(docs_list.pop(0))

[백준] 10866번 덱

[백준] 10866번 덱

출처: [백준] 10866번 덱


문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

  • push_front X: 정수 X를 덱의 앞에 넣는다.
  • push_back X: 정수 X를 덱의 뒤에 넣는다.
  • pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 덱에 들어있는 정수의 개수를 출력한다.
  • empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
  • front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.


출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

예제 출력 1

1
2
3
4
5
6
7
8
9
10
11
12
2
1
2
0
2
1
-1
0
1
-1
0
3

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
22
front
back
pop_front
pop_back
push_front 1
front
pop_back
push_back 2
back
pop_front
push_front 10
push_front 333
front
back
pop_back
pop_back
push_back 20
push_back 1234
front
back
pop_back
pop_back

예제 출력 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-1
-1
-1
-1
1
1
2
2
333
10
10
333
20
1234
1234
20

힌트


출처


알고리즘 분류


시간 제한


풀이


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
queue = deque([])

for _ in range(N):
comm = input().split()

if comm[0] == 'push_front':
queue.appendleft(comm[1])
elif comm[0] == 'push_back':
queue.append(comm[1])
elif comm[0] == 'pop_front':
if not queue:
print(-1)
else:
print(queue.popleft())
elif comm[0] == 'pop_back':
if not queue:
print(-1)
else:
print(queue.pop())
elif comm[0] == 'size':
print(len(queue))
elif comm[0] == 'empty':
if not queue:
print(1)
else:
print(0)
elif comm[0] == 'front':
if not queue:
print(-1)
else:
print(queue[0])
elif comm[0] == 'back':
if not queue:
print(-1)
else:
print(queue[-1])