코테

문제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/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" 를 제외했을 때, 문자열의 구성이 모두 같아야 한다.[들어오는 값이 기준값과 길이가 같은 경우]완전 구성이 똑같은 경우한 알파벳만 다른 경우한 알..

문제https://www.acmicpc.net/problem/1922  풀이진짜 그냥 크루스칼 알고리즘만 구현하면 끝이다. 코드import java.util.*;import java.io.*;public class Main { public static int[] parent; public static int totalWeight = 0; public void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int m = Integer.parse..

문제https://www.acmicpc.net/problem/4889  풀이단순히 스택을 사용하여 풀 수 있는 문제이다. 유명한 괄호 문제랑 거의 똑같은 문제긴 하다. 여는 괄호가 나오면 무조건 스택에 넣어준다. 그리고 빈 경우에 닫는 괄호라면, 여는 괄호로 바꿔줘서 넣어준다.스택에 } 이런 값이 하나 있어봤자 이 값은 여는 괄호일때만 사용할 수 있다. 그렇기 때문에 바꿔준 상태로 넣어준다. 그 외에 비지 않았는데 닫는 괄호라면, 스택에는 무조건 여는 괄호가 있기 때문에 짝이 맞는다.그렇기 때문에 여는 괄호를 빼주면 된다. 이 과정을 다 수행후에도 스택에 값이 남아있다면 이는 모두 여는 괄호일것이다. 수는 무조건 짝수로, 짝이 맞을거니까 {{{{ 이런 경우나 {{ 이런 경우가 있을것이다.하나만 닫는 괄호..