투투

문제 주어진 문자열에서 연속 3개의 문자가 IOI 이거나 KOI인 문자열이 각각 몇 개 있는지 찾는 프로그램을 작성하라. 문자열은 알파벳의 대문자로만 이루어진다. 예를 들어 "KOIOIOI"라는 문자열은 KOI 1개 , IOI 2개가 포함되어있다. 입력 입력은 한 줄이며 10,000자 이하의 알파벳 대문자로 구성된다. 출력 출력은 2줄이며, 첫 번째 줄에는 KOI의 개수, 두 번째 줄에는 IOI의 개수를 각각 출력하라. 접근 찾아야하는 단어의 길이가 3으로 일정하다. 따라서 입력된 문자에서 첫 번째 인덱스부터 접근하고 길이가 3개만큼 잘라서 비교하도록 하였다. 구현 - 현재 인덱스부터 +3까지 되는 길이의 문자를 잘라서 "KOI"와 "IOI"를 비교한다. - 같을 경우 각각의 수를 증가시켜준다. for ..

문제 많은 공장에서 로봇이 이용되고 있다. 우리 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다. *명령 1. Go k - k 는 1 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k 칸만큼 움직인다. *명령 2. Turn dir - dir 은 left 또는 right 이며 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때 이 로봇을 ..

문제 재우는 중간계(middle-earth)에서 유명한 용사이다. 어느날 사람들에게 부탁 받은 마물 퇴치를 신속히 해결하고 집으로 돌아가려고 하는데, 마법의 숲에서 재우를 추적하고 있던 불의 마법사 무길이와 마주치게 되었다. 무길이는 재우를 잡기 위해서 화염 마법을 시전하였고 어느덧 숲은 화염으로 가득차고 있었다. 재우는 무길이가 화염을 풀어 놓은 숲에서 신속히 요새로 귀환하고자 한다! 숲의 지도는 R행과 C열로 이루어져있다. 비어있는 칸은 '.'로 표시되고, 불은 '*'로, 바위는 'X'로 표시되어있다. 용사의 집은 'D'로 표현되고, 재우가 처음에 서있는 위치는 'S'로 표시된다. 매 분마다 재우는 인접한 4개의 칸(상, 하, 좌, 우)으로 이동할 수 있다. 불은 매 분마다 인접한 4개의 칸에 불을 ..

문제 승훈이는 심심한 시간에 스타크래프트(Starcraft) 게임을 하며 놀고 있었다. 스타크래프트 유닛중 하나인 저글링을 한 곳에 몰아세운 뒤, 방사능 오염 공격으로 없애보려고 했다. 그런데 좀 더 재미있게 게임을 하기 위해서 게임을 개조하여 방사능 오염 공격을 가하면 방사능은 1초마다 이웃한 저글링에 오염된다. 그리고 방사능에 오염된 저글링은 3초 후에 죽게 된다. 저글링을 모아놓은 지도의 크기와 지도상에 저글링들이 놓여 있는 격자 위치가 주어질 때, 총 몇 초 만에 저글링들을 모두 없앨 수 있는지 알아보는 프로그램을 작성하시오. 입력 첫째 줄은 지도의 열의 크기와 행의 크기가 주어진다. 지도는 격자 구조로 이루어져 있으며 크기는 100×100칸을 넘지 않는다. 둘째 줄부터는 지도상에 저글링들이 놓여..

문제 히스토그램이란 보통 분포의 정도를 알기 위해 사각형의 서열을 기준선에 맞춰 늘어놓은 다각형을 말한다. 만약 임의의 수열이 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마..