https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWGsV8IaAXsDFAVW

오답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/swa_3503/Solution.java

정렬해서 나올 수 있는 모든 경우를 탐색하기 위해 DFS를 하였다. 원형이기 때문에, 시작점을 하나로 DFS 탐색을 시작해도 모든 경우가 커버 가능하다. 예를 들어, 2 4 5 7 9 의 경우에 2를 시작으로 DFS를 탐색한다. 탐색을 하며 높이 차를 계산한다. 시간 초과가 났다. 탐색으로 모든 케이스를 따져보는 것이 아닌 문제라는 것이다.

정답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/swa_3503_02/Solution.java

1. 오름 차순으로 정렬한다.
2. 가장 작은 값을 가운데에 둔다.
3. 맨 앞에, 다음으로 작은 값을 둔다.
4. 맨 뒤에, 다음으로 작은 값을 둔다.
5. 3,4를 반복한다.

이와 같이 하면, 가장 큰 높이 차가 최소가 되도록 정렬된다. 구현을 위해서, 두개의 큐를 사용하였다.

다음 그림을 보자.

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE

쉬웠다. 70분 소요되었다. 탐색문제이다.

풀이

selectionSort01

1. 각 row에 어떤 색으로 칠할지 DFS로 탐색하여 결정한다.

   i번째 row에 W를 칠했으면, i+1 번째에 W / B / R 색칠 가능

   i번째 row에 B를 칠했으면, i+1 번째에 B / R 색칠 가능

   i번째 row에 R를 칠했으면, i+1 번째에 R 색칠 가능

2. DFS로 깊이 들어갈때마다, 색칠할 칸을 카운트한다.

조건

1. R를 칠하려고 하면, 그 전에 B가 하나라도 나와야함

2. W만으로 칠해서는 안된다.

코드

https://github.com/KoJunHee/algorithm/blob/master/src/swa_4613/Solution.java

https://www.acmicpc.net/problem/16234

2018년 하반기 대졸 신입 삼성 코딩 테스트 오전 타임 2번 탐색 문제이다.

매우 쉬웠다. 55분 소요되었다.

풀이

1. 국경선 열기

   국가 각 지점에서 DFS을 실행하여 각 국가에 지역 번호를 매긴다.

   각 지점에서 동서남북으로 연결되어 있고, 인구 차가 l 이상 r 이하이면 같은 지역 번호가 매겨진다.

   DFS를 실행하고 리턴되었을 때, 지역 번호가 2개 이상 매겨졌으면 연합이 생성된 것이다.

   리스트에 지역번호와 함께 연합의 (인구합 / 연합을 이루는 국가수) 를 저장한다.

2. 인구 이동

   i,j 의 지역번호가 리스트에 저장되어 있는 지역 번호라면 해당 index의 리스트의 인구를 map에 저장한다.

코드

https://github.com/KoJunHee/algorithm/blob/master/src/bj_16234/Main.java

https://www.acmicpc.net/problem/1371

풀이

문장 단위로 읽어서 알파벳 개수 count.

여러 문장을 읽어오는 방법 : hasNextLine()으로 다음 문장이 있는지 체크

hasNextLine()

scanner의 input에 입력받을 line이 있다면 true를 반환한다.

https://docs.oracle.com/javase/7/docs/api/java/util/Scanner.html

코드

https://github.com/KoJunHee/algorithm/blob/master/src/bj_1371/Main.java

https://www.acmicpc.net/problem/1475

풀이

처음에 숫자 세트를 하나 갖고 있다고 시작한다. 숫자 부족할 때마다 숫자 세트를 늘려나간다.

코드

https://github.com/KoJunHee/algorithm/blob/master/src/bj_1475/Main.java