[Python] 코딩테스트 문제 리스트 (with 풀면서 배운점)

문자열 문제

단어에서 사용된 알파벳 순서 출력하기

- 배운점: ord를 이용해서 아스키코드끼리 빼서 범위를 구할 때는 그 범위에 +1을 해줘야함

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

10809번: 알파벳 찾기

import sys
S = sys.stdin.readline().rstrip('\n')
dic = {}
for i in range(ord('z')-ord('a') + 1):
    dic[chr(ord('a')+i)] = -1
    
for j in range(len(S)):
    if(dic[S[j]] == -1):
        dic[S[j]] = j
for i in list(dic.values()):
    print(i,end=' ')

 

가장많이 나온 알파벳 찾기

- 배운점: values(), keys() 적절히 사용하면 편함

딕셔너리 [] 대괄호 안에는 key만 들어갈 수 있음 -> value 도출

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

1157번: 단어 공부

import sys
S = sys.stdin.readline().strip('\n')
dic = {}
list1 = []
for i in range(ord('Z')-ord('A') + 1):
    dic[chr(ord('A')+i)] = 0
for i in range(len(S)):
    dic[str(S[i].upper())] += 1
max_num = max(dic.values())
for i in dic:
    if max_num == dic[i]:
        list1.append(i)
if len(list1) > 1:
    print('?')
else:
    print(list1[0])

 

구현문제

왕실의 나이트 문제

이코테(나동빈님)

1) 8x8 체스판에서 x축은 a,b,c,d,e,f,g,h / y축은 1,2,3,4,5,6,7,8

2) 나이트가 갈수 있는 모든 자리의 수를 구하는 문제

- 배운점: 갈 수 있는 방향을 리스트 안에 다 넣어서 구하면 빠르다

*이동 문제들은 방향 리스트와 현재 좌표를 더해서 nx, ny 처럼 이동된 좌표를 구하고 이 값들이 범위에 포함되는지 if문 걸어줘야함

import sys
X = sys.stdin.readline()
count = 0
x,y = int(ord(X[0])-ord('a')+1),int(X[1])
print(x,y)
list1 = [[1,2],[2,1],[-1,-2],[-2,-1],[-1,2],[2,-1],[-2,1],[1,-2]]
for i in range(len(list1)):
    nx = int(x + list1[i][0])
    ny = int(y + list1[i][1])
    print(list[i],nx,ny)
    if( 0 < nx < 9 and 0< ny < 8):
        count +=1
print(count)

c4에서 갈 수 있는 모든 자리의 수: 8

콘솔 입력 및 출력

---

Stack

문자열 제거하기

- 배운점: 시간 제한을 생각하고 풀어야함, 시간복잡도를 체크하자

*문자열 문제인 줄 알았지만, 알고보니 Stack을 이용하여 풀어야하는 문제

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

9935번: 문자열 폭발

//Stack 사용 소스
import sys
S = sys.stdin.readline().rstrip()
M = sys.stdin.readline().rstrip()
stack = []

for i in range(len(S)):
    stack.append(S[i])
    if ''.join(stack[-len(M):]) == M:	//stack 뒤에서 M의 길이부터 마지막까지 문자를 M과 비교
        for _ in range(len(M)):	//같다면 M의 길이만큼 pop 시킴(뒤에서 부터 제거)
            stack.pop()

if stack:
    print(''.join(stack))	//''.join 으로 List 값들을 이어진 문자열로 출력
else:
    print('FRULA')

replace로 해결하려고 했지만 시간초과 된 소스..

(이해도 잘못함 M에 들어간 문자를 전부 없애는게 아니라 M 문자열을 없애야하는 문제)

//시간초과된 내 소스

import sys
N = sys.stdin.readline().strip('\n')
M = sys.stdin.readline().strip('\n')
result = str(N)
for i in range(len(str(M))):
    result = result.replace(str(M[i]),"")
    if result == "":
        result= 'FRULA'
        break
print(result)

 

 

---

최대공약수, 최대공배수 (유클리드 호제법)

- 배운점: 재귀를 활용하자

import sys
def GCD(a, b):
    print('a = {} / b = {}'.format(a, b))
    if b == 0:
        print('최대 공약수는 {} 입니다.'.format(a))
        return a
    else:
        return GCD(b, a % b)

a, b = map(int, input().split())
c = GCD(a, b)
print('최대 공배수는 {}'.format(a * b // c))

---

백준 일곱난쟁이(브루트포스)

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

- 배운점: 9명중 7명을 찾지말고, 9명중 2명을 빼자(1명이 선택된 상태에서 2번째 for문의 시작은 i+1로 시작)

while문에 try, except문 쓰면 if문에 break 쓴거랑 똑같음 while: True loop문에도 써도될 듯 함

2309번: 일곱 난쟁이

numbers = []
while len(numbers) < 9:
    try:
        numbers.append(int(input()))
    except ValueError:
        print("오류")
        continue
def select(list1):
    for i in range(len(list1)-1):
        for j in range(i+1,len(list1)):
            if((sum(list1) - list1[i] - list1[j]) ==100):
                list1.remove(list1[i]) 		#del list1[i]
                list1.remove(list1[j-1])	#del list1[j-1]
                list1.sort()
                return list1
            else:
                continue
for item in select(numbers):
    print(item)

사탕 게임(브루트포스)

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

- 배운점: 비교할 때 for문을 어떻게 활용할지 생각하기, range(N)는 0 ~ N-1까지(0포함 N개) 들어감 N은 안들어감

부모 for문 안에 각각 다른 자식 for문을 2개 넣어서 부모for문의 i와 자식 for문 j를 다르게 활용하면 행과 열을 동시에 탐색할 수 있다는 점을 배움 (시간복잡도는 O(N(N+N)) 이니까 O(2N^2)인가?)

3085번: 사탕 게임

def check(arr):
    N = len(arr)
    answer = 1
    for i in range(N):
        count = 1
        for j in range(N-1):
            
            if arr[i][j] == arr[i][j+1]:
                count += 1
            else:
                count = 1
            if answer < count:
                answer = count
        count = 1
        for j in range(N-1):
            if arr[j][i] == arr[j+1][i]:
                count += 1
            else:
                count = 1
            if answer < count:
                answer = count
    return answer
            
N=int(input())
a = [list(input()) for i in range(N)]
answer = 0
for i in range(N):
    for j in range(N):
        if j+1 <N:
            a[i][j],a[i][j+1] = a[i][j+1],a[i][j]
            temp = check(a)
            if answer < temp:
                answer = temp
            a[i][j+1],a[i][j] = a[i][j],a[i][j+1]
        if i+1 <N:
            a[i][j],a[i+1][j] = a[i+1][j],a[i][j]
            temp = check(a)
            if answer < temp:
                answer = temp
            a[i+1][j],a[i][j] = a[i][j],a[i+1][j]

print(answer)

---

준규나라 날짜 계산(브루트포스)

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

- 배운점: Mod를 활용하여 10진수가 아닌 값을 비교할 수 있어야함

예를 들면 16진수면 E%15, 29진수면 S%28, 20진수면 M%19 처럼 하나뺀 숫자를 Modulo 해주면됨,

다른 진수끼리의 나머지만 알수 있을 때 이 숫자가 서로 같은 숫자라면 결과값을 의미하는 변수하나를 두고 각각의 진수에 나머지값을 뺀다음 하나작은 숫자로 Mod 해주고 하나씩 ++ 해주면서 loop문으로 같은 값을 찾으면 됨

1476번: 날짜 계산

import sys
E,S,M = map(int,sys.stdin.readline().split())
# 1 ≤ E ≤ 15
# 1 ≤ S ≤ 28
# 1 ≤ M ≤ 19
result = 1
while True:
    if(((result - E)%15 ==0) and ((result - S)%28 ==0) and ((result - M)%19 ==0)):
        print(result)
        break
    result += 1

---

Dictionary 활용 문제 (해쉬 테이블이랑 비슷함)

달리기 경주

https://school.programmers.co.kr/learn/courses/30/lessons/178871

- 배운점: Dictionary형은 Dictionary[key] 로만 Value를 얻을 수 있다. 대괄호에 꼭 Key값이 들어가야함(중요)

리스트로 풀었더니 시간초과남 -> 딕셔너리로 풀어보자

for문에서 딕셔너리를 loop돌릴때 enumerate를 사용하면 index, key 2가지 값을 이용할 수 있음

이 문제 생각보다 머리 좀 굴려야함 (player list 랑 plater_rank dictionary 2개 사이를 왔다 갔다하는 알고리즘)

1) callings의 item을 player_rank 대괄호에 넣어서 value 를 얻음 즉, 순위 index를 temp에 넣고,

2) 이렇게 얻은 temp를 또 players의 대괄호에 넣어서 이전 index의 item과 순서를 바꿔줌

3) 그리고 이렇게 만들어진 players[temp], players[temp-1]를 가지고 player_rank의 [] 대괄호에 key값으로 넣어서 value 값끼리 바꿔줌
(바뀐 players에서 temp랑 temp-1 끼리 바꿔줬어도 다시 temp랑 temp-1 또 바꿔도 같으니까, temp는 어차피 처음 index라서 그럼)

프로그래머스

import sys
def solution(players,callings):
    player_rank = {player:index for index,player in enumerate(players)}
    print(player_rank)
    for call_name in callings:
        temp = player_rank[call_name]  #temp는 call한 key의 index
        players[temp],players[temp-1] = players[temp-1],players[temp]   
        #players list에서 call된 item과 temp-1 index를 갖는 item과 스왑
        player_rank[players[temp]],player_rank[players[temp-1]] = player_rank[players[temp-1]],player_rank[players[temp]]
        #dictionary에는 [] 대괄호에 key가 필요하기 때문에 players[temp]를 이용하여 key를 얻고 이를 [] 다시 대괄호에 넣어 value 접근하여 서로 스왑함
        print(player_rank)
        print(players)
    return print(players)
    
players = ['A','B','C','D']
callings = ['B','A','C','D']
solution(players,callings)

추억 점수

https://school.programmers.co.kr/learn/courses/30/lessons/176963

위 달리기 경주랑 비슷함

값 in list 혹은 값 in dictionary을 써서 리스트나 딕셔너리에 값이 있는지 확인할 수 있음

프로그래머스

def solution(name, yearning, photo):
    answer = []
    score = {nickName:yearning[i] for i,nickName in enumerate(name)}
    for i in range(len(photo)):
        score_sum = 0
        for j in range(len(photo[i])):
            if(photo[i][j] in score):
                score_sum += score[photo[i][j]]
        answer.append(score_sum)
    return answer

---

동서남북 이동

- 위치 이동문제:NxN 만큼 배열의 크기가 정해지고 M에서 R,L,U,D 를 통해 이동 명령한다. 현재위치(1,1)에서 M을 통해 이동된 최종 위치를 출력하자(단, NxN의 범위를 벗어나는 이동 명령은 무시한다.)

- 배운점: X축(동,서), Y축(남,북) 을 따로 dx, dy로 구현하고 더해줘야 X,Y축끼리 서로 영향을 안줌

동,서,남,북을 의미하는 4개의 문자를 dx,dy 값과 index를 매칭하여 List에 넣어서 for문 안에 if문을 만들어서 매칭될 때 더하는 if문을 구현하고 이를 4번 돌려서 이동된 nx, ny축을 구함 그리고 nx,ny는 새로운 x,y축이 됨

(i=0 일때 R 즉, x축에 1을 더함, i=1일때 L 즉, x축에 -1을 더함
 i=2 일때 D 즉, y축에 1을 더함, i=3 일때 U 즉, y축에 -1을 더함)

import sys
N = int(sys.stdin.readline())   #NxN 만큼의 배열이 생김
M = list(sys.stdin.readline().split()) #M은 R,L,U,D 를 공백으로 구분하며 현위치에서 문자대로 동서남북으로 이동함
x,y = 1,1   #현재위치를 (1,1) 이라고 지정
nx,xy = 0,0
print(x,y)

dx = [1,-1,0,0] #X축에 해당하는 R, L
dy = [0,0,1,-1] # Y축에 해당하는 D, U
move = ['R','L','D','U'] #

for item in M:
    for i in range(len(move)):
        if(item == move[i]):
            nx = x + dx[i]  #i가 증가하더라도 dx[i]에 X축에 해당하는 R,L만 더해짐 D,U가 0이기 때문
            ny = y + dy[i]  #dx,dy에 x축,y축을 0의 값으로 구분하였기 때문에 x,y축 둘중 하나만 더해짐
    if nx < 1 or nx > N or ny > N or ny < 1:    #nx,ny가 범위를 넘어가면 continue 이동안함
        continue
    x,y = nx,ny
print(x,y)

---

DFS 문제

기초 구현문제

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

1260번: DFS와 BFS

 

- 배운점: 그냥 외워야함 이건 (DFS, BFS 기본 와꾸를 알아야 다른 문제도 풀 수 있기 때문에 무조건 이해하고 넘어가기)
graph 입력 받는 것도 생각 잘해야함

노드, 엣지가 어떤건지 개념도 파악하고, 왜 visited는 N+1 만큼이고, graph는 (N+1)*(N+1) 만큼 리스트를 만드는지 이해해야함

from collections import deque #BFS를 구현하기 위해 deque 사용
import sys
#그래프 저장: int[][]
#방문여부 bool[][]
#결과값 int[]
#N: 정점(Node)
#M: 간선(Edge)
#V: 시작점
N,M,V = map(int,sys.stdin.readline().split())
graph = [[False] * (N+1) for _ in range(N+1)] #(N+1)x(N+1) 크기의 그래프 표현 배열
#N 크기만큼 만들어진 list는 0부터 시작하기 때문에
#보통 1부터 시작하는 정점을 List[i]로 표현하기 위해 
# N+1로 생성해서 index를 1부터 사용함
for _ in range(M):
    a,b = map(int,sys.stdin.readline().split())
    graph[a][b] = True #방향이 없기 때문에 둘다 True처리
    graph[b][a] = True #간선으로 이어진 정점을 True 처리해줌

visited_DFS = [False] * (N+1) #DFS용 방문리스트
visited_BFS = [False] * (N+1) #BFS용 방문리스트
result_DFS = []
result_BFS = []

def DFS(V):
    visited_DFS[V] = True #정점 V 방문처리
    #print(V, end=' ') 이걸로 하나씩 찍어도됨
    result_DFS.append(V)
    for i in range(1,N+1): 
        #1부터 N까지 돌리기 위해 1,N+1로 범위를 정함
        if not visited_DFS[i] and graph[V][i]: 
            #i 정점에 방문하지않았지만, 정점 V와 i가 간선으로 연결되어있다면
            DFS(i)  # i를 방문처리하고 i와 연결된 또다른 노드를 찾기 위해 재귀호출(깊이 들어감)
DFS(V)
print(" ".join(map(str,result_DFS))) #result안에 int형이라 ' '.join이 안먹어서 str로 바꿔주려고 map을 씀

def BFS(V): #BFS에 시작 정점을 넣음
  q = deque()   #collections의 deque를 이용하여 큐를 만듦
  q.append(V)   #큐에 시작 정점을 삽입함       
  visited_BFS[V] = True #방문 표시함
  while len(q) != 0:    #while문 돌입 큐에 더이상 들어갈 정점이 없을 때까지
    V = q.popleft() #왼쪽에 있는 정점을 pop시킴(선입선출)
    result_BFS.append(V)  #pop된 정점을 출력함  
    for i in range(1, N + 1):   #1부터 N까지 범위 설정
      if not visited_BFS[i] and graph[V][i]:    #아직 방문하지않았고, V와 이어져있는 i정점이라면
        q.append(i) #큐에 i를 넣음
        visited_BFS[i] = True  #i를 방문표시함
BFS(V)
print(" ".join(map(str,result_BFS)))

위 문제로 DFS, BFS 그래프 탐색을 이해했고 아래 바이러스 문제를 풀어보면됨

(탐색 속도를 위해 BFS로 풀었음)

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

2606번: 바이러스

from collections import deque
import sys

N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())
V = 1
result = []
graph = [[False] * (N + 1) for _ in range(N+1)] 
visited = [False] * (N + 1)
for _ in range(M):
  a, b = map(int, sys.stdin.readline().split())
  graph[a][b] = True
  graph[b][a] = True


def BFS(V):
  q = deque()
  q.append(V)
  visited[V] = True
  while len(q) != 0:
    V = q.popleft()
    result.append(V)
    for i in range(1, N + 1):
      if not visited[i] and graph[V][i]:
        q.append(i)
        visited[i] = True


BFS(V)
#print(result)
print(len(result)-1)

 

BFS문제

미로 탐색 문제 -> 최소경로 -> DFS가 아닌 BFS 이용하기

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

2178번: 미로 탐색

- 배운점:

1) 붙어있는 문자열을 List에 넣을 때 ' '.join() 과 split()을 사용하자

2) 동서남북으로 이동을 해야할 때는 dx,dy = [0,0,1,-1], [1,-1,0,0] 을 이용하고 4번을 for문 돌려서 상하좌우 탐색하여 기존 x,y와 더해서 새로운 nx,ny를 도출 해내고 graph[nx][ny] 안에 있는 값을 이용하자

3) 0부터 시작할 때는 N-1, M-1 까지가 범위 임

4) q에 2개 이상 값이 들어갈때는 deque.append([x,y]) 처럼 리스트나 deque.append((x,y)) 튜플을 이용하기

5) 이동한 graph[nx][ny]에 기존 graph[x][y] 값에 +1 을 해주면서 counting 역할을 graph가 해줌으로써 마지막 graph[N-1][M-1] 값이 최단 경로가 됨

 

import sys
from collections import deque
N,M = map(int,sys.stdin.readline().split())
graph = [list(map(int,' '.join(sys.stdin.readline().split()))) for i in range(N)]
print(graph)
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def BFS(x,y):
    q = deque()
    q.append([x,y])
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <= N-1 and 0 <= ny <= M-1 and graph[nx][ny] == 1:
                q.append([nx,ny])
                graph[nx][ny] = graph[x][y] + 1
    return graph[N-1][M-1]
print(BFS(0,0))

 

 

네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

import sys  # sys 모듈 임포트

from collections import deque  # deque 모듈 임포트

## 입력받는 것들
# Node: 정점
# Edge: 간선(노드간의 연결)
# V: 시작점

n = 3  # 노드의 개수
computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]  # 컴퓨터들 간의 연결 상태를 나타내는 이차원 리스트

# 주어진 컴퓨터 네트워크에서 서로 다른 네트워크의 개수를 반환하는 함수
def solution(n, computers):
    answer = 0  # 서로 다른 네트워크의 개수를 저장할 변수
    visited = [False] * n  # 노드의 방문 여부를 저장할 리스트
    
    # 모든 노드를 순회하면서 방문하지 않은 노드를 찾고, 이를 시작점으로 하는 네트워크를 찾음
    for i in range(0, n):
        if visited[i] == False:
            answer += 1  # 서로 다른 네트워크의 개수 증가
            q = deque()  # 큐 생성
            q.append(i)  # 현재 노드를 큐에 추가
            visited[i] = True  # 현재 노드 방문 처리
            while q:  # 큐가 비어있지 않은 동안 반복
                V = q.popleft()  # 큐에서 노드를 하나 꺼냄
                for i in range(n):  # 모든 노드에 대해 반복
                    if not visited[i] and computers[V][i] == 1:  # 방문하지 않았고, 현재 노드와 연결된 노드인 경우
                        visited[i] = True  # 해당 노드 방문 처리
                        q.append(i)  # 해당 노드를 큐에 추가
    
    return answer  # 서로 다른 네트워크의 개수 반환

solution(n, computers)  # 함수 호출 및 실행