Java

문제https://www.acmicpc.net/problem/15662 풀이우선 바퀴는 LinkedList 에 저장함으로 회전이 쉽도록 구성했다. (가장 앞쪽에 있는걸 뒤로하거나, 그 반대로 함에 따라 시계방향, 반시계방향 회전 구현이 가능하다.) 이후 나는 현재 바퀴를 기준으로,  앞쪽에 돌아가야하는 바퀴들을 검사하고 뒤쪽에 돌아가야하는 바퀴들을 검사하는 방식으로 수행했다. 이 때 포인터를 두개둬서, 기준점하고 그 기준점 앞의 바퀴를 가리키도록 했다.그 다음에 극이 같은지 다른지 검사하고, 이 과정을 앞쪽으로 쭉 반복, 뒤쪽으로 쭉 반복하는 식으로 구성했다. 검사 결과에 따라 돌아가야하는 바퀴들은 Map에 방식으로 저장해서 한 번 회전이 끝났을때Map에서 값을 꺼내서 회전을 시키는 방식으로 구성했다...

문제https://www.acmicpc.net/problem/1043 풀이[* 먼저 말하자면 이 문제는 union - find 로 푸는게 정설인 거 같다.] 이 문제의 요점은, 진실을 알고 있는 사람을 통해 건너건너 거짓말쟁이에게 진실이 전해질 수 있다는 점이다. 만약 진실을 알고 있는 사람이 1이라고 가정했을 때, 파티 1 : 1 2파티 2 : 2 3파티 3 : 3 4 이런식으로 이루어져 있을 때 2번이 1번을 통해 진실을 듣게 된다. 다음에 3번은 2번을 통해 들을 수 있고, 4번은 3번을 통해서 들을 수 있다.  (파티의 순서는 상관없다) 따라서 건너건너까지 진실을 알고 있는 사람과의 파티에 엮여있는지 확인할 필요가 있다. 나는 스텝을 나눠서 코드를 구현했다. 1. 우선 진실을 아는 사람들을 저장한..

문제https://www.acmicpc.net/problem/1374  풀이아이디어를 말하자면 pq를 이용하면 된다. 진행중인 강의를 pq에 넣고, 끝나는 순이 빠른 강의를 확인한다. 가장 끝나는 시간이 빠른 강의의 "종료 시간이" 현재 내가 선택한 강의의 "시작시간" 보다 같거나 빠르다면, 해당 강의실을 그대로 사용할 수 있으므로 강의실을 추가할 필요 없다. (이 때 pq에서는 빼줘야 한다.) 그러나 그렇지 않은경우에는 강의실을 추가해야한다. (이 때는 pq에서 빼줄 필요가 없다.) 이 아이디어를 기반으로, 시작시간이 빠른 강의부터 하나씩 확인하고, pq에 넣어주는 방식으로 진행하면 된다.시작시간이 같을 경우에는 종료시간이 빠른 강의순으로 정렬한다. 코드import java.util.*;import j..

문제https://www.acmicpc.net/problem/5567 풀이문제는 단순하다. 나는 맵을 활용해서 풀었다. key 값으로 대상 동창을 넣고, value 로는 Set으로 친구 목록을 추가했다.친구는 양방향 관계니까 반대로도 넣어준다. 그런 다음 상근이(1번)의 친구들을 세어주고,그 친구들의 친구들을 세어주면 끝이다. 값을 넣어줄때 동창별로 친구 목록을 Set에 저장해뒀으니 이를 활용하면 된다. 정답도 Set을 이용해서 중복을 없애면 된다.단, 이럴 경우 상근이가 친구가 0명일때를 제외하고 답에 상근이 카운트도 들어가니,그 부분만 예외처리 해주면 된다. 코드import java.util.*;import java.io.*;public class Main { public void solutio..

문제https://www.acmicpc.net/problem/2564 풀이기본적으로 bfs, 그래프 탐색으로 문제를 접근했다. 우선 점 하나를 배열의 한 칸이라고 생각해서 2차원 배열을 선언해주었다.해당 2차원 배열에는 좌표에 맞게 상점들을 위치 시킨다.상점들의 숫자 번호를 그대로 사용해서 배열에 넣어주면 된다.( 상점들의 위치는 항상 테두리에 위치하는데, 들어온 값에 따라 동서남북을 분기해주고,  그 시작점에서 거리만큼 떨어진곳에 위치시켜주면 된다.) 상점들은 최대 100번까지 있기때문에 상점이 위치한곳 빼고는 모두 101을 넣어, 상점이 위치하지 않다고 표기한다. 방문 배열 같은 경우에는, 겉 테두리만 모두 방문하지 않게 선언한다.2차원 배열이지만 실제적으로는 끝 라인들만 사용하기 때문이다. 최종적으..

문제https://www.acmicpc.net/problem/1068  풀이처음 생각한 기본 컨셉은 예시만 보고, 루트 노드에서 시작해서 식별된 "리프 노드" 들에서 지울노드에서 탐색 후 식별된 "리프 노드" 를 빼주는것이었다.  (지울노드도 포함) 하지만 이 방법으로 했을시,  1 - 2 - 3 과 같이 일직선 형태의 트리이고, (1이 root) 3를 지운다고 했을 때 루트노드에서 탐색시 리프노드는 1개이고,지울노드인 3에서도 탐색시 리프노드는 1개이다. 이 때 리프노드의 개수를 빼주면 최종적으로는 리프 노드 개수가 0개가 되는데 실상은 1 - 2 와 같이 형태가 되며, 2라는 리프노드가 하나 존재하게 된다. 이후 생각을 조금 거쳐서 실제 노드들을 삭제할까 하다가,그냥 플래그만 줘서 지우는 방식으로 분..

문제https://www.acmicpc.net/problem/2636 풀이문제의 핵심은 가장자리, 치즈의 테두리 부분을 어떻게 캐치할 것이냐이다. 문제에서 잘 보면 이미 힌트를 줬는데, 가장 끝쪽의 4면은 치즈가 존재하지 않는다. 이 말은 즉슨, 치즈 테두리 (녹을 치즈) 를 모두 탐색할 수 있다는 말이다. 가로 막힌부분이 없으니 말이다. 그렇기 때문에 끝 라인 아무곳에서  bfs 를 수행해서, 치즈의 테두리를 탐색하면 된다. 마지막의 경우 녹일 치즈가 없을것이다. 이를 대비하여 단계마다 녹일 치즈의 개수를 저장한다. -- 나는 배열 하나를 더 활용하여 녹일 치즈를 체크하고, bfs 방문 여부 모두를 체크했다. 그리고 난 후 녹일 치즈를 0 으로 바꿔주는 작업을 수행했다. 코드import java.uti..

문제https://www.acmicpc.net/problem/12891 풀이단순한 문제이다. 앞에서부터 부분문자열 만큼 range 를 잡고 그 구성에 최소한의 알파벳 개수가 있는지 체크하면 된다. 이후로 한칸씩 이동시키면서 알파벳 개수를 체크하면 된다. 투 포인터? 라고 해야할까, 앞 뒤 인덱스 각각 하나씩을 기억하고 이동시키면서 알파벳 개수 체크만 잘하면 되는 문제이다. 코드import java.util.*;import java.io.*;public class Main { public void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

문제https://www.acmicpc.net/problem/12919  풀이이 문제는 S를 T로 만들려고 하지 말고 T를 S로 만든다는 목표로 하면 풀 수 있다. 그러니까 연산을 역으로 해서 S로 갈 수 있는지 확인하는 것이다. 이유는, S에서 T로 만들 경우에는 두 연산 모든 경우의 수를 구현해봐야한다.그러나 이미 만들어진 문자열은 연산을 제한할 수 있다. 연산1 : 문자열의 뒤에 A를 추가한다.연산2 : 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. 위와 같이 있을 때문자열의 첫번째가 B 라면 연산2를 사용해서 만들었을 수 있다.문자열의 끝이 A 라면 연산1을 사용해서 만들었을 수 있다. 이렇게 조건을 준다면 경우의 수는 훨씬 줄어든다.예로, AAA 는 연산 1만 사용해서 만들 수 있다.BAB 는..

문제https://www.acmicpc.net/problem/2607  풀이총 3개의 경우로 나눠서 생각하면 편하다.  [들어오는 값이 기준값보다 짧은 경우]짧은 경우에는 문자를 새롭게 하나 더해주는 경우의 수 밖에 없기 때문에 길이 차이는 1만 나야한다.기준값이 ABC 일 때, AB 와 같이 새로 추가할 문자열 "C" 를 제외했을 때, 문자열의 구성이 모두 같아야 한다. [들어오는 값이 기준값보다 긴 경우]긴 경우에는 문자를 하나 저게하는 경우의 수 밖에 없기 때문에 길이 차이는 1만 나야한다.기준값이 ABC 일 때,  ABDC 와 같이 제거할 문자열 "D" 를 제외했을 때, 문자열의 구성이 모두 같아야 한다.[들어오는 값이 기준값과 길이가 같은 경우]완전 구성이 똑같은 경우한 알파벳만 다른 경우한 알..