풀스택챌린지

※ 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다. 문제일직선 위에 N개의 서로 다른 탑을 왼쪽부터 오른쪽으로 세운다.해당 탑의 꼭대기에 있는 레이저는 왼쪽 방향으로 발사하고 발사한 신호는 가장 먼저 만나는 자신보다 큰 탑에서 수신한다. 탑의 높이가 주어졌을 때 해당 탑에서 발사한 신호가 어떤 탑에서 수신하는지 알아보자.  입력첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다.둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다.탑들의 높이는 1 이상 100,000,000 이하의 정수이다. 출력첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하..

※ 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.  문제N개의 빌딩이 있으며 빌딩은 1번부터 N번까지의 번호가 있다.빌딩이 X 좌표 상에 위치해 있으며 i 좌표에 있는 빌딩은 Hi 만큼의 높이를 갖고있다.만약 i 각 좌표에 빌딩의 높이가 주어졌을 때 가장 가까이 보이는 빌딩을 찾아보자. 입력첫 번째 줄에 N이 입력되며이어서 N개의 줄에 빌딩의 높이가 입력된다. 출력총 N개의 줄에 빌딩의 위치를 출력한다.접근N이 100,000 이하로 입력되기 때문에 이중 for문 이상으로는 해결할 수 없다. 따라서 한 개의 for문으로 어떻게 풀어야하는지 생각한다.이번 문제에서 끝에 있는 빌딩부터 탐색을 진행한다. 끝에 있는 빌딩을 스택에 넣고 탐색을 진행하면서 스택의 top이 현..

※ 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.  문제소들이 다른 소들의 머리 모양을 얼마나 알 수 있는지 알아본다.각 소들은 동쪽을 바로보고 있으며 각각 키를 갖고있다. 소들은 자신보다 키가 작은 소들의 머리만 볼 수 있다.모든 소들을 대상으로 각각 볼 수 있는 소의 수를 모두 더한 값을 구하라. 입력첫째 줄에 소의 수인 N이 입력된다. (N은 1이상 80,00이하)이어서 소들의 키가 N개 한 줄로 입력된다. 출력각각의 소들이 볼 수 있는 소의 머리 모양의 총합을 출력한다.접근N이 최대 80,000인 것을 통해 이중 for문으로 풀 수 없다고 판단하였다. 그래서 한 개의 for문으로 해를 구하는 방법을 생각해보았다.문제의 예시에서 각 소들이 3+0+1+0+1+..

https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 접근 리스트와 딕셔너리를 활용하여 해를 구한다. 구현 - 먼저 장르를 key로 하여 (노래의 번호, 재생횟수)를 리스트에 저장한다. - genre_play_idx의 딕셔너리에는 장르별로 리스트를 item으로 갖고 해당 리스트에는 (노래번호, 재생횟수)가 원소로 저장되어 있다. for idx in range(N): genre = genres[idx] play =..

https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 접근 (0, 0)에서 출발하여 (N-1, M-1)까지 BFS를 실행하여 최단거리를 찾는다. 구현 - 2차원 리스트인 dist에 거리를 저장한다. - (N-1, M-1)에 저장된 값을 최종적으로 출력하며, 만약 0일 경우 -1을 출력하도록 한다. q = deque() N = len(maps) M = len(ma..

문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 접근 나이트가 이동할 수..

문제 통로에 음식물들이 떨어져있고 근접한 음식물들이 모이면 큰 음식물 쓰레기가 된다. 음식물들이 떨어진 위치의 좌표가 주어질 때 가장 큰 음식물 쓰레기의 크기를 구하라. 어떤 음식물의 상하좌우에 음식물이 있을 때 근접한 음식물이라고 할 수 있다. 입력 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다. 좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 출력 첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라. 접근 뭉쳐있는 음식물끼리 같은 번호를 매기고 넘버링한 숫자의 개수를 카운트하여 가장 큰 수..

문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호..

문제 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다. 출력 각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다. 접근 그래프 내에서 순환하는 그래프를 어떻게 찾아야할지 고민했다. 다른 사람들의 풀이를 참고했을 때 현재 방문한 노드의 다음 노드도 방문 표시가 되어있을 때 순환하는 그래프라고 할 수 있다고한다. 이를 활용하여 순환하는 그래프를 찾아냈다. 구현 - 아래는 재귀호출로 DFS를 구현한 것이다. - 현재 방문한 노드를 방문 표시한다. - 현재 방문한 노드의 다음 노드를 next_node에 저장하고 - nex..

문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회..