링크 : https://www.acmicpc.net/problem/2493 문제소요시간: 40분 10초(부분 실패)설계하기(접근방법) 1. 입력받기타워의 높이를 입력받는다 2. 구현하기처음에는 탑의 위치를 지정해가면서 순회했으나 시간초과가 났다.방법이 떠오르지 않아 카테고리를 확인했고, 스택을 쓰는 문제였다는 것을 확인할 수 있었다 따라서 스택으로 코드를 구현했다자기보다 작은 높이가 스택에 있는 경우, 자기보다 큰 높이가 나올때 까지 pop해준다즉 큰 높이를 마주했을 때가 레이저를 마주했을 때와 같다.그 후 자신의 높이를 stack에 append 해준다. stack이 비어있거나, 자신보다 큰 높이를 찾지 못한 경우, 0을 저장해주고자신을 스택으로 append한다 3. 출력하기저장한 laser의 위치를 ..
링크 : https://www.acmicpc.net/problem/1759 문제소요시간: 10분 53초설계하기(접근방법) 1. 입력받기가능한 문자 리스트를 입력받는다 2. 구현하기문제의 조건은 모음 1개이상과 자음 2개 이상을 사용한 단어를 만들어야한다는 것이다 모음과 자음으로 나누고 그 중에서 가능한 경우의 수를 뽑아 정렬할까 고민했지만, 그냥 가능한 모든 경우의 수를 만든 후에,모음cnt와 자음cnt로 각 단어의 자음모음 개수를 세서조건에 부합하는 경우에만 가능한 문자 조합을 먼저 추출했다 그 후에, 각 조합을 알파벳순으로 정렬한후,가능한 문자 조합 전체 리스트를 정렬해서 출력한다. 3. 출력하기가능한 문자를 ''.join을 통해 출력한다 코드(출력)from itertools import permu..
링크 : https://www.acmicpc.net/problem/10026 문제소요시간: 32분 30초설계하기(접근방법) 1. 입력받기list 함수를 통해 문자열을 분할해주자 2. 구현하기bfs를 2개 구현하면 된다. 1개는 정상적인 bfs 1개는 색약일때, RG를 함께 탐색하는 BFS를 제작하면 된다 3. 출력하기각각 탐색 횟수를 count하여 출력한다. 코드(출력)from collections import dequen = int(input())grid = []visited = [[0 for _ in range(n)] for _ in range(n)]visited_x = [[0 for _ in range(n)] for _ in range(n)]o_cnt = 0x_cnt = 0dx = [-1, 1,..
링크 : https://www.acmicpc.net/problem/1148 문제소요시간: 75분 30초설계하기(접근방법) 1. 입력받기20만개 정도가 입력되니 sys를 통해서 입력받자문자열이니 rstrip을 통해 개행문자를 제거해준다 2. 구현하기아이디에이션에 상당히 애를 먹었다. 먼저 20만개의 단어를 검증하려니 딕셔너리가 생각이 났다.먼저 딕셔너리에 모든 단어를 넣어준다 그 다음 주어진 퍼즐의 문자의 조합과 순열로20만개의 딕셔너리를 검증할 수 있는지 계산해보았다. 서로다른 알파벳 9개의 경우 9!이니 시간초과가 나지 않는다.8개의 경우 9개 중에 8개를 뽑은 후, 8개의 순열을 계산하니 또한 9!으로 시간초과가 나지 않는다. 이처럼조합 및 순열 알파벳 4개부터 9개까지 itertools의 comb..
링크 : https://www.acmicpc.net/problem/2467 문제소요시간: 34분 19초설계하기(접근방법) 1. 입력받기입력에는 큰 문제가 없다 2. 구현하기포인터의 위치를 어디에 둘지 생각하다 시간은 좀 썼다. 모든 수가 양수일때는 가장 앞의 2개의 수모든 수가 음수일 때는 가장 뒤의 2개의 수 를 출력하면 된다 나머지의 경우에는 다음과 같은 방식으로 포인터를 조절할 수 있다중간에 둘의 합이 0인 경우에는 바로 break하면 된다 -7 -5 -3 -2 -1 0 4 8일 때, 처음에는 양 끝에서 출발한다 1 단계)o o-7 -5 -3 -2 -1 0 4 8 둘의 합은 1, 즉 양수이니 양수의 크기를 줄여준다면 절대값이 작아지는 것을 기대할 수..
링크 : https://www.acmicpc.net/problem/14940 문제소요시간: 34분 11초설계하기(접근방법) 1. 입력받기 배열을 입력받는다 2. 구현하기지도와 visited 배열을 선언해준다 for문을 통해 시작지점(2)를 찾아주어 저장한다 bfs를 순횐하면서 벽(0)인 경우 continue아니라면 visited에 가중치를 저장해나간다 이동 가능 공간이지만, 벽에 가로막혀서 이동하지 못한경우map과 visited를 비교하여 -1로 저장해준다 3. 출력하기출력해준다 코드(출력)import sysfrom collections import dequeinput = sys.stdin.readlinen, m = map(int, input().split())mapp = []visited = [[..
링크 : https://www.acmicpc.net/problem/1389 문제소요시간: 47분 13초설계하기(접근방법) 1. 입력받기양방향 그래프니, 그래프를 초기화 할 때 양쪽을 초기화 해준다 2. 구현하기시작지점이 고정된 BFS와 달리 모든 시작점에서 BFS를 순회해야하니, for문을 통해 각 BFS를 실행해주어야 한다. 최단거리 BFS를 구현한 후에 for문을 통해 1번부터 N번까지 실행하면서,거리의 합을 bacon_map list에 저장한다 3. 출력하기bacon_map list의 sum 최소값 중에서 가장 작은 사람의 수를 출력한다 코드(출력)from collections import dequen , m = map(int, input().split())graph = [[] for _ in ..
링크 : https://www.acmicpc.net/problem/18352 문제소요시간: 40분 20초 설계하기(접근방법) 1. 입력받기도시를 입력받아 그래프에 넣는다 2. 구현하기q에 넣어서 그래프를 순회한다.시작시점이 초기화되지 않도록 조건을 걸어준다 3. 출력하기오름차순으로 최단거리 도시 목록을 출력한다 코드(출력)from collections import dequeimport sysinput = sys.stdin.readlinecity, road, distance, start = map(int, input().split())city_list = []graph = [[] for _ in range(city + 1)] # [[],[2,3],[3,4],[],[]]visited = [0 for i..
