01: 배열과 문자열
1. 해시테이블
연결리스트와 해시 코드 함수를 활용한다.
1. 키의 해시코드를 계산한다.
배열의 인덱스 구하기 -> hash(key) % array_length
키의 개수는 무한하지만 자료형의 개수는 유한하므로 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다.
2. 인덱스마다 키와 값으로 이루어진 연결리스트가 저장된다. 위와 같은 충돌 사항에 대해 방지하기 위함이다.
3. 키에 상응하는 값 찾는 과정
해시코드로 인덱스를 계산 -> 키에 상응하는 값을 연결리스트에서 탐색
2. ArrayList와 가변 크기 배열
자바의 경우 Array배열은 길이가 고정되어 있으므로 선언시에 크기를 함께 지정해야 한다.
String[] arr1 = new String[5];
int[] arr2 = {1, 2, 3};
int N = 3;
int[] arr3 = new int[N];
동적 가변 크기 배열 ArrayList는 배열이 가득 차는 순간 배열의 크기를 두 배로 늘리는 기능이 내재되어 있다.
두 배 크기의 새 배열을 만든 다음 원소들을 복사한다.
배열의 크기가 N인데 K로 늘리는 경우 늘어난 배열에는 K/2만큼의 원소가 복사되어야 한다.
(배열이 가득 차는 순간 크기가 두 배로 늘어나기 때문)
배열의 크기가 K인 배열에 대해서 반으로 쪼개가면서 생각해보면,
마지막 배열의 크기 증가의 경우: n/2개의 원소 복사 필요함
이전 배열의 크기 증가의 경우: n/4개의 원소 복사 필요함
이전 배열의 크기 증가의 경우: n/8개의 원소 복사 필요함
이전 배열의 크기 증가의 경우: n/16r개의 원소 복사 필요함
두 번째 배열 크기 증가의 경우: 2개의 원소 복사 필요함
첫 번째 배열 크기 증가의 경우: 1개의 원소 복사 필요함
따라서 N개의 원소를 삽입하기 위해 복사해야 할 원소의 총 개수는 N/2+N/4+...2+1인데, 이는 N보다 작은 값이 된다.
따라서 N개의 원소를 삽입할 때의 최악의 시간 복잡도는 O(N)이 된다.
그러나 배열의 크기가 두배 증가하는 작업은 ArrayList가 꽉 찼을 때에만 발생하기 때문에 평균 시간 복잡도는 O(1)이라고 할 수 있다. (접근, 삽입의 경우에도 평균적으로 O(1)이 소요된다.)
Arrays 관련 메서드
int arr[] = {10, 8, 11, 2, 3, 0};
// 오름차순 {0, 2, 3, 8, 10 ,11}
Arrays.sort(arr);
// 내림차순 {11, 10 , 8, 3, 2, 0}
Arrays.sort(arr, Collections.reverseOrder());
// int 타입 배열 내림차순(Integer로 변경 필요)
Integer arr2[] = Arrays.stream(arr).boxed().toArray(Integer::new);
Arrays.sort(arr2, Collections.reverseOrder());
// 일부 인덱스만 정렬 -> 0, 4까지 정렬 {2, 8, 11, 10, 3, 0}
Arrays.sort(arr, 0, 4);
// binary search(단, 오름차순 정렬 먼저 해야함)
Arrays.binarySearch(arr, 2);
// 배열을 ArrayList로 변환
List list = Arrays.asList(arr);
// 배열의 특정 범위 잘라서 다른 배열 변수에 할당
int tmp[] = Arrays.copyOfRange(arr, 0, 3);
// 배열 복사
int []tmp = arr.clone();
// 배열의 길이
System.out.println(arr.length);
List vs ArrayList
ArrayList <Object> list = new ArrayList<>();
List <Object> list = new ArrayList<>();List(인터페이스)가 ArrayList(클래스)보다 더 상위 개념이다.
List를 사용해 ArrayList를 선언하면 LinkedList 또는 Vector와 같은 List 인터페이스를 활용할 수 있다는 장점이 있다.
List <Object> list = new List <>();
List <Object> list = new LinkedList <>();따라서 삽입, 삭제, 탐색 등 다양한 기능을 한번에 활용하기 위해서는
List<Object> list = new ArrayList<>();로 선언하는 것이 합리적이다.
List<String> list = new ArrayList<>();
list.add("java"); // 단순 삽입 {"java"}
list.add(0, "c++"); // 특정 인덱스에 삽입 {"c++", "java"}
list.set(1, "c#"); // 특정 인덱스 값을 수정 {"c++", "c#"}
list.remove(1); // 특정 인덱스 값 삭제 {"c++"}
list.contains("java"); // 값 존재 확인 true/false
list.indexOf("java"); // 값에 해당하는 첫번째 인덱스를 반환.(특정 값이 중복되어 있을 경우 첫번째 인덱스만 반환) 없으면 -1 반환
// get(index)로 특정 인덱스 값 조회
for (int i = 0; i < list.size(); i++) System.out.println(list.get(i));
list.addAll(list2) // list 뒤에 list2 전체 값 삽입
list.removeAll(list2) // list에서 list2에 들어있는 모든 값 삭제
list.retainAll(list2) // list에서 list2에 들어있는 값 제외한 모든 값을 삭제
list.clear() // 전체 값 삭제
list.isEmpty() // 길이가 0이면 true, 아니면 false
list.size() // 길이
list.containsAll(list2) // list에 list2의 모든 값이 포함되어 있으면 true or false
List<String> list = new ArrayList<>();
list.add("서울");
list.add("대구");
list.add("부산");
list.add("대구");
System.out.println(list.indexOf("대구")); // 1 첫번째 인덱스
System.out.println(list.lastIndexOf("대구")); // 3 마지막 인덱스
list.removeIf(k -> k % 2 != 0) // 람다로 특정 조건 만족하는 수를 list에서 모두 제거 (홀수 제거)
List<String> list = new ArrayList<>(Arrays.asList("1", "2", "3"));
List<String> list2 = new ArrayList<>();
list2.addAll(list); // 깊은 복사 1, 2, 3
List<String> list3 = new ArrayList<>(list); // 깊은 복사
3. StringBuilder
String joinWords(String[] words) {
String sentence = "";
for (String w: words) {
sentence = sentence + w;
}
return sentence;
}위는 words 문자열 배열에 있는 모든 값을 sentence라는 이름의 문자열형 변수에 더하기 연산을 하고 return하는 코드이다.
String 자료형은 더하기 연산을 지원하지만 이어붙일 때 마다 새로운 문자열에 복사를 하는 문제점이 있다. 이때마다 새로운 객체가 생성된다. (자바는 문자열 변경이 원칙적으로 불가능하기 때문이다. 시간복잡도 또한 O(N)이나 걸린다.)
StringBuilder의 경우 단일 객체에 대해 연결된 문자열을 빌드할 수 있는 클래스를 제공한다.
위의 코드는 다음과 같이 개선할 수 있다.
String joinWords(String[] words) {
StringBuilder sentence = new StringBuilder();
for (String w : words) {
sentence.append(w);
}
return sentence.toString();
}StringBuilder sb = new StringBuilder();
sb.append("abc") // 문자열 추가
sb.insert(2, "kk") // 2 위치에 kk 삽입 "abkkc"
sb.delete(0, 2) // 0~1 위치의 문자열 삭제 "c"
sb.deleteCharAt(2) // 2 위치의 문자 삭제 "ac"
sb.setCharAt(0, 'h') // 0 위치의 문자를 h로 변경 "hbc"
sb.reverse() // 문자열 거꾸로 뒤집기 "cba"
sb.setLength(2) // 문자열 길이를 2로 줄임 "ab"
sb.setLength(4) // 문자열 길이를 4로 늘림. 모자란 부분이 공백으로 채워짐
.toString(); // String으로 형변환
4. 예시 문제 1
문자열을 편집하는 방법에는 문자의 삽입, 삭제, 교체의 세 가지 종류가 주어진다.
두 개의 문자열이 입력되었을 때, 두 문자열을 같게 만들기 위한 편집 횟수가 1회 이내이면 true, 아니면 false를 반환하는 코드를 작성하시오.
풀이
1) 교체의 경우
bale과 pale에 대해서 생각해보자.
위의 예제에서는 단 하나의 문자만 교체함으로써 두 값을 같아지도록 할 수 있다.
그러나 bare과 pale의 경우에서는 b->p r->l과 같이 두 번의 교체가 이루어져야 두 값이 같아진다.
결론적으로, 교체를 한 번 함으로써 같아지도록 하려면 두 문자열의 길이가 같고, 두 문자열이 단 하나의 문자만 달라야 한다.
2) 삽입의 경우
aple와 apple에 대해서 생각해보자.
ap까지는 서로 인덱스와 문자가 모두 동일하다.
세번째 인덱스에서 첫번째 문자열에는 l이, 두번째 문자열에는 p로 서로 다르다.
aple가 특정 값을 추가했을 때 apple가 될 수 있도록하기 위해서는
apple와의 비교에서 서로 값이 달라지는 인덱스 이후의 값들이 같아야 한다.
첫번째 문자열을 first, 두번째 문자열을 second라고 했을 때, 판별 규칙은 다음과 같다.
각 인덱스의 값이 다를 경우, second의 인덱스만 증가시킨다.
만약 두 인덱스가 다르면서 인덱스의 값까지 다를 경우에는 false를 리턴한다.
각 인덱스의 값이 같을 경우, first와 second의 인덱스 둘다 증가시킨다.
모든 문자에 대한 순회가 끝났을 경우 true를 리턴한다.
3) 삭제의 경우
apple에 대해 aple를 비교하는 것으로써, 위의 삽입의 경우에 대해 반대로 적용하면 구현할 수 있다.
반복문이 한번 순회 하는 동안 연산이 이루어지므로 시간복잡도는 O(N)이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
boolean oneEditAway(String first, String second) {
if (first.length() == second.length()) {
return oneEditReplace(first, second);
}
else if (first.length() + 1 == second.length()) { // first 길이가 하나 더 적은 경우
return oneEditInsert(first, second);
}
else if (first.length() -1 == second.length()) { // first 길이가 하나 더 많은 경우
return oneEditInsert(second, first);
}
return false;
}
boolean oneEditReplace(String s1, String s2) { // 문자열 길이 같은데 글자가 하나 이상 다르면 컷
boolean foundDifference = false;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) { // 문자 하나만 다르면 그냥 넘어감
if (foundDifference) { // 문자가 두 개 이상 다르다? 바로 컷
return false;
}
foundDifference = true;
}
}
return true;
}
boolean oneEditInsert(String s1, String s2) {
int index1 = 0;
int index2 = 0;
while (index2 < s2.length() && index1 < s1.length()) {
if (s1.charAt(index1) != s2.charAt(index2)) {
if (index1 != index2) {
return false;
}
index2++;
}
else {
index1++;
index2++;
}
}
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine().trim(); // 입력값 받기
String str2 = br.readLine().trim();
Main main = new Main();
System.out.println(main.oneEditAway(str1, str2));
}
}
5. 예시 문제 2
반복되는 문자의 개수를 세는 방식의 문자열 압축 메서드를 작성하라.
예를 들어 문자열 aabcccaaa를 압축하면 a2b1c5a3가 되어야 한다.
만약 압축된 문자열의 길이가 기존 문자열의 길이보다 길다면 기존 문자열을 반환해라.
문자열은 대소문자 알파벳으로만 이루어진다.
접근
단순하게 문자열을 순회하면서 연속되는 문자의 개수를 체크하고, 현재 문자와 다음 문자가 다를 경우 정답으로 출력될 문자열에 더하기 연산을 하는 방법.
기존 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
String compressBad(String str) {
String compressedStr = "";
int countConsecutive = 0;
for (int i = 0; i < str.length(); i++) {
countConsecutive++; // 문자 연속 개수 세기
// 문자열 범위 내에서 현재 문자와 다음 문자를 비교하여 같지 않다면 (현재 문자 + 연속 개수)를 결과 문자열에 추가
if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) {
compressedStr += "" + str.charAt(i) + countConsecutive; // 반복문 내부에서 문자열 연산하므로 O(n^2)이 걸린다.
countConsecutive = 0; // 문자 연속 개수 0으로 초기화
}
}
return compressedStr.length() < str.length() ? compressedStr : str;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine().trim(); // 입력값 받기
}
}주석에도 나타나 있듯, String 자료형의 연산 자체가 O(N)이 되기 때문에 반복문 내부에서 이를 사용하게 되어 O(N^2)이나 걸리는 비효율적인 코드가 되었다.
이를 StringBuilder를 활용하여 개선할 수 있다.
compressBad 메서드를 개선한 코드
String compressBad(String str) {
StringBuilder compressedStr = new StringBuilder();
int countConsecutive = 0;
for (int i = 0; i < str.length(); i++) {
countConsecutive++; // 문자 연속 개수 세기
// 문자열 범위 내에서 현재 문자와 다음 문자를 비교하여 같지 않다면 (현재 문자 + 연속 개수)를 결과 문자열에 추가
if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) {
compressedStr.append(str.charAt(i)); // append의 평균 시간복잡도는 O(1)이다.
compressedStr.append(countConsecutive);
countConsecutive = 0; // 문자 연속 개수 0으로 초기화
}
}
return compressedStr.length() < str.length() ? compressedStr.toString() : str;
}6. 백준 문제
https://www.acmicpc.net/problem/1541
1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다
www.acmicpc.net
문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
예제 입력 1 복사
55-50+40
예제 출력 1 복사
-35
예제 입력 2 복사
10+20+30+40
예제 출력 2 복사
100
예제 입력 3 복사
00009-00009
예제 출력 3 복사
0
접근
55+24+32-14+21-53+22... 와 같은 수를 생각해보자.
괄호를 쳐서 이 식의 값이 최소가 되게끔 하려면
55+24+32-(14+21-53+22...) 이렇게 되어야 한다.
위의 계산을 구현하는 방법은 다음과 같다.
1. -를 기준으로 항을 두개로 나눈다.
2. 각 항의 값을 전부 더하기 연산을 한다.
3. 첫번째 항은 죄다 더한채로 두고 두번째 항의 값을 빼버린다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] plusCal = br.readLine().split("-");
int answer = 0;
for (int i = 0; i < plusCal.length; i++) {
int sum = 0;
String[] minusCal = plusCal[i].split("\\+");
for (int j = 0; j < minusCal.length; j++) {
sum += Integer.parseInt(minusCal[j]);
}
if (i == 0) answer += sum;
else answer -= sum;
}
System.out.println(answer);
}
}
'알고리즘 스터디' 카테고리의 다른 글
| 05 : DFS, BFS (0) | 2023.07.13 |
|---|---|
| 04: 우선순위 큐 (0) | 2023.07.06 |
| 03: 큐, 덱 (0) | 2023.06.01 |
| 02: 연결리스트 (1) | 2023.05.18 |