문제 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 풀이 숫자야구는 일반적으로 세 자리나 네 자리의 숫자를 임의로 설정하여 상대방의 숫자를 맞추는 게임이다. 숫자를 맞추기 위해서는 서로에게 상대방의 숫자를 불러 결과를 확인한다. 결과는 숫자와 위치가 일치하면 스트라이크, 숫자는 맞지만 위치가 다르다면 볼로 판정하고 상대방에게 알려준다. 예를 들어 임의의 수가 456 이고 확인하는 수가 469 인 경우 1스트라이크 1볼이라고 상대방에게 알려준다. 만약 숫자가 하나도 맞지않는다면 아웃으로 처리하고, 3아웃이면 ..

문제 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 하노이의 탑 문제는 큰 부분을 작은 부분으로 나누어 해결하는 재귀적 접근으로 해결할 수 있다. 원판을 모두 목적지로 옮기기 위해서는 먼저 가장 큰 원판을 목적지로 옮겨야한다. 따라서 나머지 원판들을 목적지가 아닌 곳으로 옮긴다. 모두 옮기고 나면 가장 큰 원판을 목적지로 옮기고 그 후에 나머지 원판들을 목적지로 옮기면 된다. 위의 과정은 재귀를 이용해 해결할 수 있는데, 두번째로 큰 원판 또한 목적지로 옮기기위해 나머지 원판들을 목적지가 아..

문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 LectureTime 데이터 클래스를 정의하여 Comparable 인터페이스를 구현한다. 시작시간을 기준으로 오름차순 정렬하도록 고 만약 시작시간이 같다면 종료시간을 기준으로 정렬한다. 입력받은 시간을 LectureTime 배열에 저장하고 이 배열을 정렬해준다. 우선순위 큐를 선언하고 첫번째 수업의 종료 시간을 큐에 넣는다. 배열을 순회하면서 만약 현재 강의의 시작 시간이 우선순위 큐의 최상단의 강의의 종료 시간보다 작거나 같으면 해당 강의는 해당 강의실에서 진행 가능하므로 우선순위 큐에서 poll(..

문제 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 Boolean 배열 visited를 활용하여 초대 인원을 구하였다. 먼저, 인접리스트를 생성하고 입력받은 친구 관계를 기록한다. 그 후, 1번과 직접 연결된 리스트를 방문 표시하고, 이와 연결된 리스트들의 친구들도 방문 표시를 한다. 방문 배열에서 true로 표시된 개수에서 1(자기 자신)을 뺀 값이 초대할 친구의 수가 된다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw =..

문제 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net 풀이 처음에는 리스트를 이용해 큐스택을 직접 구현하여 해결하려 했지만, 당연하게도 시간 초과가 발생했다. 모든 요소에서 계산을 처리하면 시간복잡도가 O(NxM)이 되는데, 문제에서 주어진 범위에 따라 N = 10만, M이 10만일 때는 100억의 계산이 필요하기 때문이다. 대신 큐와 스택의 특성을 이용해 계산하는 방법을 생각해 보아야한다. 먼저 스택은 현재 삽입된 원소가 다시 ..