전반적인 주의 사항
- 투포인터 문제 풀 때 left하고 right 잘 확인해보자
자바에서 0과 1을 변경하는 방법
XOR을 사용하는 방법
int num = 1;
num = num ^ 1;
System.out.println(num); // 출력: 0
num = num ^ 1;
System.out.println(num); // 출력: 1산술 연산을 이용하는 방법
int num = 1;
num = 1 - num;
System.out.println(num); // 출력: 0
num = 1 - num;
System.out.println(num); // 출력: 1숫자 배열을 String으로 변환
stream과 mapToObj를 사용
int[] a = {1, 2, 3, 4};
String tp = Arrays.stream(a)
.mapToObj(String::valueOf)
.collect(Collectors.joining());
System.out.println(tp); // 출력: 1234StringBuilder를 사용
int[] a = {1, 2, 3, 4};
StringBuilder sb = new StringBuilder();
for (int num : a) {
sb.append(num);
}
String tp = sb.toString();
System.out.println(tp); // 출력: 1234문자열 교환에서 sliding window
문제링크
특정 문자열만을 일직선으로 만들기 위해서 최소한의 교환을 해야 한다고 했을 때 접근 하는 방법은 sliding window로 해당 window에 불순 알파벳이 얼마나 있는지 확인한다.
// 예시
// 아래와 같은 문자열이 있을 때
// abababababababa
// 슬라이딩 윈도우로 내부에 b가 얼마나 있는지 확인을 해준다.
for (int i = 1; i < s.length(); i++) {
// 앞에서 윈도우 크기만큼 이동
char delete = s.charAt(leftLoc - 1);
char add = s.charAt(rightLoc % s.length());
if (delete == 'b') {
middleBCount -= 1;
}
if (add == 'b') {
middleBCount += 1;
}
answer = Math.min(answer, middleBCount);
leftLoc += 1;
rightLoc += 1;
}
빗물 채우기를 위한 구현 문제
구현 중 실수 한 것
일정 기둥 사이에 물이 찰 수 있는 면적을 구하는 문제에서 처음에는 다음 칸이 더 낮아지는 부분 까지의 채우는 곳 까지 분할해서 구하는 방향을 진행을 하였다. 그렇게 진행했더니 아래와 같은 예제에서는 뒤에 더 높은 부분이 있는 경우 문제가 발생하는 것을 확인할 수 있었다.
잘못된 예제
8 8
7 2 3 4 6 1 1 9뒤에 수정한 방향
들어온 입력들의 숫자들을 확인 한 후 가장 높은 기둥들을 찾아서 진행한다.
// 이미 지나간 부분인지 확인하기 위한 HashMap
Map<Integer, Integer> store = new HashMap<>();
// 이후 목표를 찾기 위해서 저장하는 큐
Queue<Integer> dp = new PriorityQueue<>((o1, o2) -> o2 - o1);이미 지나간 부분이여서 0인경우에는 패스 하고 아니면 다음 목표를 설정한다.
static int findNextTarget(Queue<Integer> queue, Map<Integer, Integer> store) {
int output = 0;
while (!queue.isEmpty()) {
int peek = queue.peek();
if (store.getOrDefault(peek, 0) > 0) {
output = peek;
break;
}
queue.poll();
}
return output;
}지나간 경우에는 HashMap에서 해당 높이를 삭제해 준 다음
목표하는 Target에 도착했거나 오른쪽이 왼쪽 기준보다 높아진 경우에는 멈춘다.
// count 차감
store.put(rightSide, store.get(rightSide) - 1);
if (rightSide == nextTarget || rightSide >= leftSide) {
int gizun = Math.min(leftSide, rightSide);
...
}인덱스를 설정할 때 발생한 문제
문제
해당 스위치를 변환 시키는 문제로 짝수 부분에 있는 배열 값에 대해서 변환이 필요한 문제였다.
입력 받은 번호를 처리하기 위해서 입력받은 스위치를 배열의 0 부터 넣어줘서 처리를 진행하였다.
하지만 짝수를 처리함에 있어서 본래의 위치가 1 → 0으로 변하므로 정확한 위치를 처리하지 못하는 경우가 있었다.
이후 처리 방법
만약 1부터 데이터를 처리해야하는 경우에는 0부터 처리하는 것이 아니라 배열의 크기를 입력받은 크기의 +1 만큼 생성한 다음에 1부터 처리하도록 한다. 인덱스 0은 무시
배열간의 비교
문제 링크(빌런 호석) 이 문제는 주어진 숫자를 변형시켰을 때 나올 수 있는 경우의 수를 찾는 문제였다.
초기 접근
- 나올 수 있는 숫자의 범위가 0~9로 제한되어 있어, 각 변경 횟수마다 가능한 숫자들을 저장하려고 시도하였다
- 이 방식은 Map 안에 이차원 List가 들어가는 복잡한 자료구조를 필요로 하였고 데이터를 기록해두려고 했지만 나중에 조회시에도 순회를 해야해서 효율성이 떨어졌다.
이후 접근
- 각 숫자 쌍 사이의 차이를 이차원 배열에 저장하는 방식으로 전략을 변경했습니다
- 예를 들어 숫자1에서 2~9까지의 변할 수 있는 조건의 수를 미리 배열에 저장해놓는다.
- 나올 수 있는 숫자 경우의 수를 모두 순회하면서 기준값과의 차이가 주어신 숫자 이내인지 확인한다.
- 한 번 순회를 하므로 시간 복잡도가 O(n)이 나온다.
반복문의 조건 설정 문제
문제
아래의 코드와 같이 queue의 크기가 변화할 수 있음에도 queue의 크기를 반복문의 조건으로 사용하였다.
if (needServer > queue.size()) {
for (int j = 0; j < needServer - queue.size(); j++) {
answer += 1;
// System.out.println(i);
queue.add(i + k);
}
}어려운 문제는 아니지만 자각하지 못하고 실수로 적는 경우가 발생해서 주의할 수 있도록 메모해놓는다.
해결방법
처리할 크기를 미리 지역변수로 선언해서 내부의 크기 변화에 영향을 받지 않도록 한다.
if (needServif (needServer > queue.size()) {
int queueSize = queue.size();
for (int j = 0; j < needServer - queueSize; j++) {
answer += 1;
queue.add(i + k);
}
}