뱀귤 블로그

문제 링크 : https://www.acmicpc.net/problem/1057

김지민, 임한수가 라운드 몇에서 대결하게 될 지 맞추는 문제입니다.

처음에 단순하게 Queue로 구현을 하였습니다.

1. 모든 토너먼트 멤버를 Queue에 넣은 뒤 두 개씩 poll 한다.

2. 두 값을 비교하여 김지민, 임한수라면 라운드를 출력하고 종료

2-1. 두 값 중 하나만 김지민 혹은 임한수라면 무조건 승리자

2-2. 둘 다 해당되지 않는다면 무조건 앞 번호가 승리자

이렇게 단순하게 구현하여 Queue에 계속 넣었다 빼며 구현하였습니다.

하지만 정답을 맞춘 후에 다른 정답자들 코드를 보니 굉장히 간단하게 구현하였습니다.

각 멤버가 같은 라운드에서 만난다는 것은 부모 노드가 같다고 볼 수 있습니다.

그래서 두 멤버의 부모 노드만을 계속 따라가며 같은 값이 될 때의 라운드를 출력하면 됩니다.

자식 노드가 최대 두 개로 고정되어 있기 때문에 부모 노드의 인덱스는

(now + 1) / 2

now/2 + now%2

이렇게 두 가지 방법으로 구할 수 있습니다.

코드는 처음에 구현했던 Queue를 이용한 방법과 두번째로 구현한 방법 모두 올리겠습니다.

문제 링크 : https://www.acmicpc.net/problem/2026

서로 좋아하는 친구들의 목록이 나열될 때 소풍에 보낼 수 있는 K 명의 학생을 출력하는 문제입니다.

예전에 굉장히 많이 틀려서 포기했던 문제인데 다시 푸는데도 굉장히 많은 시도를 하고 맞췄습니다..

제 기준에서 크게 두 가지의 함정이 있었는데 아래에서 설명드리겠습니다.

1. 첫번째로 주의할 점은 싸이클을 찾는 문제가 아니라는 사실입니다.

따라서 일반적인 DFS의 싸이클 검사나 유니온 파인드로는 해결할 수가 없습니다.

결국 백트래킹으로 완전 탐색을 하는데 단순하게 인접 행렬로 그래프를 구현해서 돌리면 O(n^3)으로 시간초과가 됩니다.

2. 그래서 탐색할 필요가 없는 노드를 생략하는게 두번째 핵심입니다.

탐색할 필요가 없는지는 어떻게 아는가?

소풍은 무조건 K 명이 가게 됩니다.

만약 K=4 일 때 1번 노드의 친구가 2번, 3번 밖에 없다면 그들이 모두 친구 관계여도 3이 됩니다.

결국 1번 노드는 탐색할 필요가 없어서 생략할 수 있게 됩니다.

예를 들어 K=62 일 때, 모든 노드가 60명의 친구만 가지고 있는 테스트 케이스가 주어집니다.

모든 노드들은 본인과 친구 60명을 포함해서 최대로 나올 수 있는 친구 관계가 61명이라 소풍에 가는 인원이 나올 수 없습니다.

하지만 불필요하게 모든 노드들을 탐색하고 있어야 하죠.

그래서 저는 indegree 배열을 만들어서 자신과 연결된 노드의 갯수가 몇 개인지 저장했습니다.

1번 노드의 친구가 2, 3 이면 indegree[1] = 2가 됩니다.

만약 indegree가 K-1보다 작은 노드들은 탐색할 필요 없이 생략하게 됩니다.

이렇게 두가지 예외처리를 해주면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/10809

간단한 문제지만 자바에서는 알파벳 순회를 이렇게도 할 수 있단걸 보여주기 위해 썼습니다.

문제 링크 : https://www.acmicpc.net/problem/8958

O가 연속될수록 점수가 커지는 문제입니다.

받은 String의 길이만큼 돌며 O 면 값을 더해주고 score을 1 증가시키고

X 면 계속 score을 1로 유지시킵니다.

테스트케이스가 얼마나 들어올 지 모르기 때문에 출력 형식으로 System.out.println 대신에 StringBuilder를 사용하였습니다.

문제 링크 : https://www.acmicpc.net/problem/2839

배달 가능한 봉투 개수가 최소가 되는 값을 구하는 문제입니다.

간단하게 이전까지의 값을 저장하는 것으로 문제를 해결 할 수 있습니다.

봉투는 항상 3kg 또는 5kg 밖에 없다는 점을 이용합니다.

예를 들어 18 이라는 값이 들어오면 15kg + 3kg 또는 13kg + 5kg 라는 두 개의 경우가 있습니다.

15kg와 13kg에는 이전에 계산 해놓았기 때문에 이미 최소값이 들어가 있습니다.

그러므로 봉투 하나만 추가하면 됩니다.

이 중에서 더 작은 값을 저장하며 N까지 진행하면 됩니다.

** 딱 나누어 떨이지지 않는 값이 들어오면 -1을 출력해야 하기 때문에 아무런 값도 저장하지 않습니다.

7kg는 딱 나누어 떨어지지 않기 때문에 0이 들어있습니다.

10kg는 7kg + 3kg와 5kg + 5kg 중 더 작은 값이 들어가게 되는데 7kg가 0이라서 무조건 1이 들어가게 됩니다.

그러므로 i-3 또는 i-5 의 값이 0보다 클 때만 계산해줍니다.

문제 링크 : https://www.acmicpc.net/problem/15552

단순한 A+B 지만 빠른 입출력을 사용해야 합니다.

자바 입력에 대한 포스팅 https://bcp0109.tistory.com/37

자바 출력에 대한 포스팅 https://bcp0109.tistory.com/38

입력때 Scanner

출력때 System.out.print 

둘중 하나만 사용하더라도 시간 초과가 납니다.

입력엔 BufferedReader를 사용하고

출력엔 BufferedWriter나 StringBuilder를 사용하면 됩니다.

둘의 차이는 거의 나지 않으므로 편한걸 사용하시면 됩니다.

저는 개인적으로 BufferedReader와 비슷하게 생긴 BuffedWriter를 사용하는 편입니다.

연습 문제 : https://bcp0109.tistory.com/39

입력과 마찬가지로 출력에도 여러가지 방법이 있습니다.

가장 간단한 방법으로는 System.out.print가 있지만 굉장히 느립니다.

보통 알고리즘 답은 많은 출력을 필요로 하지 않지만 여러 개의 테스트케이스에 대해서 출력을 할 때는 시간 초과가 발생할 수 있습니다.

따라서 많은 출력이 필요할 땐 BufferedWriter나 StringBuilder를 사용하는 것을 권장합니다.

이 둘의 특징은 데이터를 모아두었다가 한번에 출력합니다.

BufferedWriter의 경우네는 flush()를 사용하고

StringBuilder의 경우에는 자체적으로 String들을 이어붙인 것이기 때문에 StringBuilder를 출력하면 됩니다.

BufferedWriter를 사용하는 경우에는 입력할 때와 마찬가지로 throws Exception 을 붙여주거나 try 내에서 사용하시면 됩니다.

** 간단한 비교를 위해 10만개의 데이터를 출력해보았습니다.

소요시간은 StringBuilder가 가장 빨랐지만 사실 큰 차이는 없으므로 편한 것을 사용하시면 됩니다.

출력하는 데이터가 적다면 System.out을 사용하여도 괜찮습니다.

연습 문제 : https://bcp0109.tistory.com/39

자바 입력 방법은 Scanner과 BufferedReader가 있습니다.

Scanner가 쉽고 간단하여 저도 처음 문제를 풀 때는 사용하였지만, 사실 알고리즘 문제풀이에는 적절하지 않습니다.

많은 입력을 받아야 하는 경우에는 시간초과가 날 수 있기 때문입니다.

따라서 BufferedReader를 사용하는 것에 익숙해지는 것을 추천합니다.

** BufferedReader를 사용하기 위해서는 try문 내에서 사용하거나 메소드 끝에 throws Exception 구문을 붙여주셔야 합니다!

한 줄에 여러 개의 입력을 받는 경우에는 StringTokenizer 를 사용하면 됩니다.