유에스비 어딨니?

1) 생각 알파벳이 각각 적혀있는 R행 C열이 주어졌을 때, (0,0)에서 출발하여 알파벳이 중복되지 않게 최대한 갈 수 있는 칸을 출력하라. 처음 생각칸을 나아가야 하므로 DFS를 풀이를 해야한다고 생각하였다. 지나간 길에있는 알파벳이 딱 한 번만 나와야 하므로 String 변수에 해당 알파벳을 더해가면서 contains 메소드를 통해 이번에 탐색한 알파벳이 이전에 있었는지 검사하였다.▶ String 객체를 넘겨주면 검사를 하다보니 시간과 메모리를 크게 잡아먹었다. ▶ 시간도 그렇고 메모리도 18배 정도 차이가 난다. 2) 방안 1) String으로 된 매개변수를 없애고 boolean형 visited 배열을 만들어 주어 해당 알파벳의 위치를 체크하였다.▶ 다음 탐색을 위해 해당 재귀가 종료될 시 fal..

1) 생각 가중치가 없는 방향 그래프가 주어졌을 때, 해당 Vertex에서 다른 Vertex로 갈 수 있는지 여부를 파악해서 갈 수 있다면 1로 표시 없다면 0으로 표시하여 출력하라. 처음 생각DFS를 통해 방문표시를 해가면서 탐색하면 되는 문제라고 생각하고 제출 하였지만... 시간 초과의 늪에 빠지고 말았다. 예제는 아주 잘되는데 머가 문제였을까... 정말 많이 고민했지만 계속되는 시간초과.. 2가지의 문제점이 있었다. 2) 방안 1) DFS 시작의 문제점. 모든 Vertex을 탐색하기 위해서 처음에는 2중 반복문을 통해 해당 Index가 1의 값을 가지고 있으면 거기서 부터 탐색을 시작하였다. => 결론은 해당 Vertex에서 다른 Vertex들을 갈 수 있냐의 문제로 일단 해당 Vertex를 집어넣..

1) 생각 4 x 4 격자 판이 주어졌을 때, 7개를 탐색했을 경우 나올 수 있는 숫자의 개수를 구하시오(중복 비허용)처음 생각우선 4 x 4이고 시간도 Java의 경우 4초를 주기때문에 충분히 완전탐색으로 해결할 수 있다고 생각하였다.따라서 DFS를 이용하여 탐색을 진행하였다. 다음 생각DFS를 진행하면서 7개의 탐색을 진행하면 방문 배열을 통하여 이미 온곳이면 return하고 방문하지 않았던 곳이면 방문표시를 한 뒤, 개수 변수를 result++ 해준 뒤, return 처리를 하였다. 알고리즘을 다 완성하고 나서 보니 HashSet 자료구조를 쓰는것이 더 좋을 것 같아 수정하였다. 다음 생각HashSet의 제너릭 타입을 String으로 해주었는데 아무래도 객체들을 다루다보니 속도가 느리고 메모리를 많..

1) 생각 이전 문제인 [SW Expert] 4579. 세상의 모든 팰린드롬 2 와 거의 비슷한 문제이다 답도 1줄만 추가하였다.팰린드롬을 만들 수 있나를 물어보는 문제이다. 이번엔 치트키로 '?'를 사용하고 있다. 첫 번째 생각이전 문제랑 거의 똑같지만 한 가지 차이가 있다면 '*'는 모든 문자를 넣을 있으므로 '*'가 있을 때는 강제로 맞춰줄 수 있었다.이번 문제에서 사용되는 치트키 '?'는 딱 한 글자만 넣을 수 있으므로 다른 점이다. 2) 방안 1) '?'는 한 글자만 넣을 수 있으므로 flag가 false를 가르키고 있다면 반복문을 바로 빠져나와준다.2) 이전 문제의 치트키 '*'는 문자를 넣을 수 있었기에 "ab*csdfba"와 같이 '?'를 넣었을 경우에는 틀린 문자에서 문장을 넣어주어서 '..

1) 생각 앞 뒤로 똑같은 문자를 팰린드롬이라고 한다. 이때 치트키 문자인 "*"는 어떤게 들어가도 상관이 없다.문자가 주어질 때, 그 문자가 팰린드롬이 될 수 있는지 판단해라. 첫 번째 생각앞 뒤가 똑같아야 하므로 문자열의 앞에서부터 그리고 뒤에서부터를 비교한다.만약 해당 Index 짝이 다르다면 그 짝중에 "*"가 있는지 판단해본다. 2) 방안 1) 반복문을 통해 변수 j를 늘리면서 앞쪽에서 진행하는 Index를 얻고, 해당 문자열 길이 - j - 1을 통해서 뒤에서 진행하는 Index를 얻어 비교한다. 2) 다르다면 우선 flag를 false로 바꾼다. 3) 해당 Index의 짝이 다르면 둘 중 *가 있는지 파악하여 있다면 flag를 다시 true로 바꿔준다. 123456789101112131415..

1) 생각 오셀로 게임을 시작한다. 초기 조건은 N x N에 상관없이 다음과 같은 중앙 4개의 형태로 동일하다.이제 오셀로를 두는 좌표를 준다. 이 좌표를 항상 둘 수있는 경우를 준다. 주어진 좌표들을 모두 두었을 때 흑과 백의 개수를 출력해라. 첫 번째 생각돌을 하나 두었을 때, (위 아래) (좌 우) (대각 4방향)을 판단해 주어야한다. 두 번째 생각예제의 답이 틀리게 나와 확인해보니 당연히 (x,y)로 주어질 줄 알았지만 (y,x) 로 주어지고 있었다.2) 방안 1) 모든 경우의 수를 다 탐색 해주었다.2) y와 x를 바꿔주었고, 배열의 크기를 N개로 생성하여서 x,y 각각 -1을 해주었다.3) 오셀로를 놓았을 때, 뒤집는 과정에서 빈 공간 체크를 하지 않아서 예제는 답이 잘 나왔지만 제출시에는 틀..

1) 생각 단어가 주어지고 '-'이 들어갈 Index가 주어졌을 때, 해당 Index에 '-'을 넣은 결과를 출력하라. 첫 번째 생각기존에 있던 문자열에 '-'을 넣게되면 기존 단어들의 Index가 변한다. 두 번째 생각'-'을 넣어줄 때마다 String을 생성하면 성능이 좋지 않을 것이다. 2) 방안 1) '-'의 위치 배열을 정렬하여 맨 뒤 Index 부터 '-'을 넣어주면 단어의 Index에 신경쓰지 않고 '-'을 넣어줄 수 있다.2) 주어진 문자열을 List로 만들어 '-'의 삽입을 용이하게 하였다. 123456789101112131415161718192021222324252627282930313233343536import java.io.IOException;import java.util.Arra..

1) 생각 문자가 주어지면 그 문자를 가지고 모양을 만들어라. Ex) APPLE 일 경우 첫 번째 생각문자를 가지고 만드는 패턴이 정형화되어있고, 세로의 길이는 무조건 5줄이다. 두 번째 생각(1,5) 줄과 (2,4) 줄이 쌍이므로 두 줄중 한 줄을 만든뒤 복사해주면 된다. 2) 방안 한 줄 한 줄 패턴에 맞춰서 만들어 준다. 중앙 줄을 미리 만들어주면 나머지는 중앙 줄과 비교해서 만들어 줄 수 있다.(2,4) 줄은 중앙 줄에서 '.'이 나오는 구간은 '#'이고 나머지는 '.'으로 표현된다.(1,5) 줄은 중앙 줄에서 문자가 나오는 구간은 '#'이고 나머지는 '.'으로 표현된다. 1234567891011121314151617181920212223242526272829303132333435363738394..

1) 생각 사람들은 대중의 흐름에 의해 움직인다! i 번째의 사람들은 i-1명이 기립박수를 치고 있어야지 기립박수를 같이 쳐준다. 문자열이 주어졌을 때 모든 사람이 기립박수를 치게하려면 몇 명의 알바를 고용해야할까? 첫 번째 생각i 번째 사람은 i-1 명이 박수를 치고 있어야 한다고 적혀있지만 배열로 따질 경우 Index가 0 부터 시작하기 때문에 Index i 번째 사람은 i명 이상이 박수를 치고 있어야지만 기립 박수를 치기 시작한다. 두 번째 생각예시가 모두 0과 1로 주어졌지만 0~9 까지의 숫자가 나올 수 있다.2) 방안 기립 박수를 치고있는 관객 수를 계속 더해가면서 현재 박수를 치고있는 사람 수와 Index 번호와 크기를 비교하여 현재 박수를 치고있는 사람 수가 적을경우 해당 Index 번호만..

1) 생각 A,B의 빵이 있으며 C금액을 가지고 빵을 사고 싶다.. 그것도 종류에 상관없이 제일 많이!C 금액을 가지고 있을 때 가장 많은 빵을 사고싶다면 가장 싼 빵을 많이 사면 될 것이다. 2) 방안 A,B 중 싼 빵을 찾아 C 금액으로 나눠준다. 12345678910111213141516171819import java.io.IOException;import java.util.Scanner; public class Solution { public static void main(String[] args) throws IOException{ Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for(int i=1;iB?B:A; System.out.p..