백준 알고리즘 랜덤 풀이

[1021] 회전하는 큐

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
pick = list(map(int, input().split()))

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

while len(pick)>0:
    if nums[0]==pick[0]:
        nums.popleft()
        pick.pop(0)
        continue

    idx = nums.index(pick[0])   # 뽑을 숫자의 index
    
    if idx<=len(nums)//2:
        nums.append(nums.popleft()) # 2번 수행
        cnt+=1
        #print(nums)
    else:
        nums.appendleft(nums.pop()) # 3번 수행
        cnt+=1
        #print(nums)
        
print(cnt)

 

큐 자료구조를 이용해 푼 문제이다. popleft, appendleft, pop, append를 사용하면 쉽게 풀 수 있다.

뽑으려는 숫자가 위치한 index가 앞쪽이면 2번을 수행하고, 뒷쪽이면 3번을 수행하는 것이

연산 횟수를 최소로 하는 방법이기 때문에 위처럼 작성했다.

 

pick = [2, 9, 5]

1 2 3 4 5 6 7 8 9 10

1번 째 수행) 2 3 4 5 6 7 8 9 10 1 -> 2뽑기

3 4 5 6 7 8 9 10 1

2번 째 수행) 1 3 4 5 6 7 8 9 10
3번 째 수행) 10 1 3 4 5 6 7 8 9
4번 째 수행) 9 10 1 3 4 5 6 7 8 -> 9 뽑기

10 1 3 4 5 6 7 8

5번 째 수행) 8 10 1 3 4 5 6 7
6번 째 수행) 7 8 10 1 3 4 5 6
7번 째 수행) 6 7 8 10 1 3 4 5
8번 째 수행) 5 6 7 8 10 1 3 4 -> 뽑기

 

---

[1051] 숫자 정사각형

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
square = [list(map(int, input().rstrip())) for _ in range(n)]

size = n
while True:
    for x in range(n):
        for y in range(m):
            nx = x+size-1
            ny = y+size-1
            
            if 0<=nx<n and 0<=ny<m:	# 직사각형 범위를 벗어나지 않는 경우
           		# 모든 꼭짓접이 일치하는 경우
                if square[x][y] == square[x][ny] ==square[nx][y] == square[nx][ny:
                    print(size**2)
                    sys.exit()
                    
    size-=1

 

(0,0), (0,1), (0,2) ~ (n-1, m-1)까지 하나하나 탐색하면서 꼭짓점을 비교한다. (완전탐색)

참고로 (x, y), (x, y+size-1), (x+size-1, y), (x+size-1, y+size-1)가 정사각형의 꼭짓점을 의미한다.

모든 꼭짓점이 일치하는 경우 바로 정사각형의 크기를 리턴하고 프로그램을 종료시켜준다.

 

---

[1138] 한 줄로 서기

import sys
input = sys.stdin.readline

def dfs(n, lst):
    if n==N:
        if len(lst)==N:
            check = True    # 카운트 체크
            for i in range(N):
                cnt = 0
                for j in lst[:i]:   # 왼쪽에 있는 키 비교
                    if j>lst[i]:    # 본인보다 큰 경우 cnt 증가
                        cnt+=1

                if cnt!=height[lst[i]-1]:   # 정보가 일치하지 않는 경우
                    check = False
                    
            if check:   # 정보가 모두 일치하는 경우
                print(' '.join(map(str, lst)))
            return
    
    for i in range(1, N+1):
        if i not in lst:
            lst.append(i)
            dfs(n+1, lst)
            lst.pop()
            
N = int(input())
height = list(map(int, input().split()))


dfs(0, [])   # 백트래킹

 

---

[10819] 차이를 최대로

import sys
input = sys.stdin.readline

def dfs(n, lst, index):
    global answer
    
    if n==N:
        if len(lst)==N:
            total = 0
            for i in range(N-1):
                total += abs(lst[i]-lst[i+1])
            answer = max(answer, total)
        return
    
    for i in range(N):
        if not index[i]:	# 해당 인덱스를 사용하지 않은 경우
            lst.append(nums[i])
            index[i] = True
            dfs(n+1, lst, index)
            lst.pop()
            index[i] = False
            
            
N = int(input())
nums = list(map(int, input().split()))
answer = 0
index = [False]*N	# 인덱스 체크 여부
dfs(0, [], index)	# 백트래킹

print(answer)

 

백트래킹 알고리즘으로 풀었다.

숫자가 중복될 수도 있기 때문에 nums의 인덱스를 통해 해당 인덱스 포함 여부를 판단했다.

---

[15663] N과 M(9)

import sys
input = sys.stdin.readline

def dfs(n, lst, index):
    if len(lst)==M:
        answer.add(tuple(lst[:]))   # 리스트 복사(or lst.copy())
        return

    for i in range(N):
        if not index[i]:	# index에 해당하는 숫자 사용 여부
            lst.append(nums[i])
            index[i] = True
            dfs(n+1, lst, index)
            lst.pop()
            index[i] = False

N, M = map(int, input().split())
nums = list(map(int, input().split()))
answer = set()
index = [False]*N

dfs(0, [], index)

answer = list(answer)
answer.sort()

for i in answer:
    for j in i:
        print(j, end=' ')
    print()

 

백트래킹 문제였다. 조금 엥? 했던 부분이 dfs 함수 내에 종료 조건 if문에서

answer.append(lst)를 해줬는데도 append는 되는데 lst가 빈 값으로 들어가게 됐다.

 

리스트는 가변 객체로 다른 변수에 할당할 때 참조가 전달되는데, 이는 리스트의 원본과 복사본이 동일한 리스트를 가리키게 됨을 의미한다.

 

리스트는 가변 객체(수정 가능한 객체)로 다른 변수에 할당할 때 참조가 전달된다.

메모리에 리스트가 저장되고, 변수는 그 리스트를 가리키는 참조를 가지고 있게 된다는 뜻!

따라서 리스트의 복사본을 집어넣어줘야 한다. 복사 방법은 lst[:] 또는 lst.copy()를 사용하면 된다.

 

문제에서 중복 값을 허용하지 않는다고 했으니 answer을 set 자료형으로 설정하고, tuple 형태로 add 해줬다.

(리스트 자체는 해시 가능한(hashable) 객체가 아니기 때문에 tuple 형태로 바꿔준 후 add해주면 된다.)

 

---

[2477] 참외밭

import sys
input = sys.stdin.readline

n = int(input())
info = [[] for _ in range(5)]	# 방향에 따른 길이 정보
d = []	# 방향 입력 순서

for i in range(6):
    direction, length = map(int, input().split())
    d.append(direction)
    info[direction].append(length)
    
# 큰 직사각형 넓이 구하기
square1 = 1	
for i in info:
    if len(i)==1:
        square1 *= i[0]

# 작은 직사각형 넓이 구하기
d = d*2	# 방향 2번 반복
square2 = 1
for i in range(len(d)*2-5):
    if d[i:i+2] == d[i+2:i+4]:
        if d[:i+1].count(d[i])==1:
            square2 *= info[d[i]][1]
        else:
            square2 *= info[d[i]][0]
        
        if d[:i+1].count(d[i+1])==1:    
            square2 *= info[d[i+1]][1]
        else:
            square2 *= info[d[i+1]][0]
        break

# 참외밭 넓이 * 참외 개수
print((square1-square2)*n)

 

방향 별 입력 순서가 정해져있는 것이 아니기 때문에 작은 직사각형의 넓이를 구하는 경우를 생각하는 과정에서

시간이 다소 걸렸다. 쉬울 줄 알았는데 의외로 오래 걸려서 풀이를 자세히 써보려고 한다.

 

1) input (문제 예시)

7
4 50
2 160
3 30
1 60
3 20
1 100

 

입력될 수 있는 방향의 순서는 아래와 같다 (6가지)

색칠 된 부분이 작은 직사각형의 가로, 세로를 의미한다.

 

4 2 3 1 3 1

2 3 1 3 1 4

3 1 3 1 4 2

1 3 1 4 2 3

3 1 4 2 3 1

1 4 2 3 1 3

 

처음에는 3131에서 가운데 13이 작은 직사각형의 가로, 세로가 되는 것을 알게 되었고,

4, 5, 6번째는 3131이 나오지 않으니까 아래처럼 리스트를 한 번 더 이어 붙이는 아이디어를 생각해냈다. (d = d*2)

 

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

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

 

* 오답 코드!!!!!!

import sys
input = sys.stdin.readline

n = int(input())
info = [[] for _ in range(5)]
d = []
for i in range(6):
    direction, length = map(int, input().split())
    d.append(direction)
    info[direction].append(length)

square1 = 1
for i in info:
    if len(i)==1:
        square1 *= i[0]
        
d = d*2
square2 = 0
for i in range(len(d)*2-5):
    if d[i:i+2] == d[i+2:i+4]:
        square2 = info[d[i]][1] * info[d[i+1]][0]
        break

print((square1-square2)*n)

 

3131에서 가운데 13이 가로, 세로가 되기 때문에 방향 3은 두 번째로 추가된 값,

방향 1은 첫 번째로 추가된 값이 정답이라고 생각했다. 실제로 테스트케이스도 통과했다. 하지만 실패ㅠ

 

ㄱ, ㄴ ㄱ반대, ㄴ반대 모양 별로 또 인덱스가 달라지기 때문에 실패가 떴다.

그래서 생각한 것은 연속된 3131을 발견한 경우 그 전까지의 리스트 중에서 3과 1의 카운트를 구해서

알맞은 인덱스를 부여해주는 방법이다.

 

d[:i+1].count(d[i])과 d[:i+1].count(d[i+1])을 통해 앞에서 언급된 횟수를 구하고

1번 언급된 경우에는 2번째로 추가된 인덱스로 접근하고,

0번 또는 2번 언급된 경우에는 첫 번째로 추가된 인덱스로 접근하게 된다.

 

 

2) input (ㄱ 반대)

7
1 15
4 80
2 70
3 60
1 55
3 20

d = [1, 4, 2, 3, 1, 3]

d = [1, 4, 2, 3, 1, 3, 1, 4, 2, 3, 1, 3]

 

i가 3일 때, d[3:5] == d[5:7]이 성립된다.

 

d[:4] = [1,4,2,3]

d[i] = d[3] = 3, 1개 존재

d[i+1] = d[4] = 1. 1개 존재

 

둘 다 1개씩 존재하기 때문에 길이 정보가 담긴 info에서 1, 3번 방향의 1번째 요소를 꺼내면 된다

info[d[i]][1], info[d[i+1]][1] = 20, 55

 

---

[11048] 이동하기

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
candy = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + candy[i-1][j-1]

print(dp[n][m])

 

dfs, bfs같은 dp 문제였다. (처음엔 bfs로 풀었음)

max 함수 안에서 dp 인덱스 에러가 뜰 줄 알고 처음엔 if 문을 이것 저것 작성해줬는데

Python의 단축 평가(Short-circuit Evaluation) 방식에 의해 범위를 벗어나는 값은 무시되기 때문에

에러가 발생하지 않는다고 한다. (max, min, all, any 등도 같은 방식으로 동작!)

 

 

---

[15666] N과 M(12)

 

* 오답!!!

import sys
input = sys.stdin.readline

def dfs(n, lst):
    if len(lst)==M:
        temp = lst[:]
        temp.sort()
        if temp not in answer:
            print(' '.join(map(str, temp)))
        answer.append(temp)
        return
    
    for i in range(N):
        lst.append(nums[i])
        dfs(n+1, lst)
        lst.pop()
            
N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()

answer = []
dfs(0, [])

 

이렇게 풀면 리스트 sort를 해줘야 하기 때문에 시간 초과가 발생한다.

 

 

정답

import sys
input = sys.stdin.readline

def dfs(n, start):
    if n == M:
        print(' '.join(map(str, answer)))
        return

    check = [False] * N
    temp = 0
    for i in range(start, N):
        if not check[i] and temp != nums[i]:
            check[i] = True
            answer.append(nums[i])
            temp = nums[i]
            dfs(n+1, i)
            check[i] = False
            answer.pop()

N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
answer = []
dfs(0, 0)

 

start : 선택할 숫자의 시작 인덱스
n : 현재까지 선택한 숫자 개수

check : 선택한 숫자 사용 여부
temp : 현재 숫자 임시 저장, 중복 방지