투투

문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다. 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다. 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다. 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다. 5번 관리..

문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 접근 순서대로 탐색을 진행하여 특정한 조건에 따라 선택한 숫자는 스택에 push한다. 이후 스택의 top과 현재 숫자를 비교하는데 앞으로 선택해야할 개수보다 남아있는 수가 작을 때까지 크기를 비교한다. 선택해야할 개수보다 남아있는 수가 크다면 계속해서 스택의 top과 비교하여 현재 값이 크다면 교체를 해준다. 구현 - 문자열의 형태로 숫자를 입력받아 num..

문제 N개의 막대기를 왼쪽부터 일렬로 세운 후에 오른쪽에서 바라보았을 때 몇 개의 막대기를 볼 수 있는지 구해보자. 일렬로 세워진 막대기를 오른쪽에서 보면 보이는 막대기가 있고 보이지 않는 막대기가 있다. 입력 첫 번째 줄에는 막대기의 개수를 나타내는 정수 N (2 ≤ N ≤ 100,000)이 주어지고 이어지는 N줄 각각에는 막대기의 높이를 나타내는 정수 h(1 ≤ h ≤ 100,000)가 주어진다. 출력 오른쪽에서 N개의 막대기를 보았을 때, 보이는 막대기의 개수를 출력한다. 접근 오른쪽에서 보기 때문에 가장 오른쪽에 있는 막대기는 무조건 볼 수 있다. 이후 가장 오른쪽에 있는 막대기의 높이를 기준으로 최댓값을 갱신하여 볼 수 있는 막대기를 구한다. 구현 - 입력받은 막대기의 높이를 뒤집어서 순차적으로..

문제 히스토그램이란 보통 분포의 정도를 알기 위해 사각형의 서열을 기준선에 맞춰 늘어놓은 다각형을 말한다. 만약 임의의 수열이 2, 1, 4, 5, 1, 3, 3일 경우 사각형의 너비를 1로 맞추어 히스토그램으로 만들면 다음과 같다. 우리가 하고자 하는 것은 임의의 히스토그램이 주어졌을 때 히스토그램 내에서 사각형으로 이루어진 가장 큰 면적의 크기를 알고자 한다. 왼쪽 의 히스토그램에서 가장 큰 사각형의 영역은 오른쪽에 밑줄이 쳐진 영역과 같다 입력 입력 첫 번째는 히스토그램을 이루는 사각형의 개수 n(n≤100,000)이 입력되고 그 뒤로 히스토그램을 이루는 사각형의 높이가 순서대로 n개 입력이 된다. 사각형의 높이 k는 0 ≤ k ≤ 1,000,000,000 이다. 사각형의 너비는 모두 1이다. 출력..

문제 일직선 위에 N개의 서로 다른 탑을 왼쪽부터 오른쪽으로 세운다. 해당 탑의 꼭대기에 있는 레이저는 왼쪽 방향으로 발사하고 발사한 신호는 가장 먼저 만나는 자신보다 큰 탑에서 수신한다. 탑의 높이가 주어졌을 때 해당 탑에서 발사한 신호가 어떤 탑에서 수신하는지 알아보자. 입력 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다. 출력 첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으..

문제 N개의 빌딩이 있으며 빌딩은 1번부터 N번까지의 번호가 있다. 빌딩이 X 좌표 상에 위치해 있으며 i 좌표에 있는 빌딩은 Hi 만큼의 높이를 갖고있다. 만약 i < j 일 때 Hi < Hj면 i번 빌딩에서 j번 빌딩을 볼 수 있는 것이다. 각 좌표에 빌딩의 높이가 주어졌을 때 가장 가까이 보이는 빌딩을 찾아보자. 입력 첫 번째 줄에 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+0으로 총 5가되는데 첫 번째 소가 볼 수 있는 소들의 마리 수를 어떻게 3마..

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}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 접근 나이트가 이동할 수..