본문 바로가기

Algorithm43

[백준] BOJ 1541 잃어버린 괄호(자바) 오늘의 문제는 문자열을 파싱 하는 게 가장 중요한 포인트인 문제입니다. 문제 해결 방안 1. "-"를 기준으로 문자열을 파싱 하기 2. 각 분리된 문자 안에 있는 숫자를 전부 더해준 다음 뺄샘 해주기 다음과 같은 예시로 설명드리겠습니다. 10 - 50 + 30 + 20 - 10 + 100 이 문제에서 요구하는 최소를 구하기 위해서는 뺄샘을 기준으로 덧셈을 통해 큰 수를 먼저 만든 다음 뺄샘을 연산하면 최소를 구할 수 있습니다. 10 - (50 + 30 + 20) - (10 + 100) = 10 - 100 - 110 = -200 이렇게 뺄샘을 기준으로 덧셈 연산을 위해 저는 split 메서드를 사용하였습니다. split("\\-")을 기준으로 분리된 문자열은 다음과 같습니다. 10 50+30+20 10+1.. 2023. 1. 11.
[백준]BOJ 14719 빗물(자바) 백준 14719 빗물 문제는 구현, 시뮬레이션 문제입니다. 처음에 생각했을때 왼쪽->오른쪽, 오른쪽->왼쪽 이렇게 돌면서 왼쪽->오른쪽일때는 배열 0번 ~ W-1번 인덱스를 돌며 현재 블록 높이보다 큰 블록 높이를 찾아 이에 대한 차이를 계산하였고, 오른쪽->왼쪽 돌때도 배열 W-1 ~ 0번 인덱스를 돌며 현재 높이보다 큰 값을 찾아 차이를 계산해주었습니다. 이렇게 하니 문제 예시 테케 2개 정도는 맞았고, 1%에서 틀렸다라는 문구가 나왔습니다ㅠ 이후에 계속 생각해보았지만 도무지 모르겠어서, 결국 코드는 아니지만 어떤 로직으로 이루어졌는지 정답을 보았습니다ㅠ 로직 고인 빗물이 되기 위해서는 현재 인덱스를 기준으로 양쪽에 자신보다 큰 높이의 블록이 존재해야 합니다. 1. 현재 인덱스를 기준으로 왼쪽에 현재.. 2023. 1. 5.
[백준] BOJ 1316 그룹 단어 체커(자바) 오늘은 문자열 관련 문제를 풀어보았습니다. 문제를 풀면서 연속적으로 나오는 그룹 단어를 처리하는 방법에 대해 바로 해결 방법이 나오지 않아 이 부분에서 시간이 걸린 것 같습니다. aaabbbccb 다음을 예시로 들어 저의 풀이 방법을 설명하겠습니다. 일단 저는 각 문자에 대해 카운팅을 해주어야겠다고 생각했습니다. 저는 이때 Map을 이용하였습니다. map에 똑같은 문자가 없는 경우에 문자를 담아주었습니다. 만약 이미 똑같은 문자가 있다면 그룹 단어가 아니라고 판단하여 boolean 체크 변수를 true로 두고 break 하였습니다. 예시와 같이 aaa처럼 연속적인 문자를 처리하기 위해 연속적으로 나오는 문자 끝까지 for문을 진행합니다. 또한, 다음 탐색은 aaa 다음인 b부터 시작하기 위해 인덱스(j).. 2023. 1. 2.
[백준]BOJ 1012 유기농 배추(자바/BFS/메모리 초과) 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 위의 문제 조건을 처음 보았을때 BFS로 풀 수 있겠다고 생각했습니다. 서로 인접해있는 배추 그룹이 몇 그룹이 존재하는지를 알게되면 그건 곧 지렁이 개수를 구하는 것과 다름이 없다고 생각했습니다. 아래 그림과 같이 인접한 배추들을 그룹으로 묶어보면 총 5그룹이 나오는 것을 확인해볼 수 있었습니다. 저는 BFS로 탐색을 수행하며 인접한 배추들에 대해 방문처리를 진행했습니다. 그러나, 메모리 초과라는 문제가 발생했습니다. 결론부터 말씀드리자면 메모리 초과의 원인은 바로 방문처리 문제였습니다!!! 항상 습관처럼 방문체크는 큐에서 pop한뒤 수행했.. 2022. 12. 31.

티스토리툴바