문제
✔ 난이도 - Silver 3
설명
홀수개인건 무조건 하나여야 함. 만약 아니라면 바로 아임쏘리 출력하고 끝
홀수인거 갯수 하나 빼서 짝수로 만들자. 갯수 하나 뺀 거 그거는 무조건 가운데에 위치하게 함.
나머지는 다 짝수개여야 함!
짝수개인거를(이젠 나왔던 모든알파벳이겠죠) 알파벳순으로 1/2 개만큼 위치시킴 (str)
홀수개였던거 가운데에 위치시키고
그후 str을 리버스시켜서 뒤에 붙임
풀이1
hashmap을 사용하여 알파벳과 갯수를 저장하고
sb에 전체 문자열을 넣어주었다.
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String input = br.readLine();
Map<Character, Integer> hm = new HashMap<Character, Integer>();
for(char c: input.toCharArray()){
hm.put(c, hm.getOrDefault(c, 0) + 1);
}
List<Map.Entry<Character, Integer>> list = new ArrayList<>(hm.entrySet());
list.sort((a, b) -> a.getKey().compareTo(b.getKey()));
int count = 0;
char middle = 0;
for (Map.Entry<Character, Integer> entry : list){
if (entry.getValue() % 2 != 0){
count++;
middle = entry.getKey(); // 가운데 값 확보
entry.setValue(entry.getValue() - 1); //갯수 하나 빼서 짝수로 만듦
if (count > 1){
sb.append("I'm Sorry Hansoo");
System.out.print(sb);
return;
}
}
}
String str = "";
for (Map.Entry<Character, Integer> entry : list){
Character tmp = entry.getKey();
if (entry.getValue() == 0){
continue;
}
for (int i = 0; i < entry.getValue() / 2; i++){
str += tmp;
}
}
String str2= "";
for(int i = 1; i <= str.length(); i++){
str2 += str.charAt(str.length() - i);
}
sb.append(str);
if (middle != 0){
sb.append(middle);
}
sb.append(str2);
System.out.print(sb);
}
}
그런데 for문 안에서 str += tmp;를 사용하는게 비효율적인 것 같았다. String은 불변(immutable) 객체라서, += 연산을 할 때마다 매번 새로운 String 객체를 만들고 기존 내용을 복사하는데, 단어 길이가 길어지면 성능이 저하될 수 있다.
또한 알파벳 대문자(A-Z)로 입력 범위가 고정되어 있을 때는 HashMap보다 크기가 26인 int 배열을 쓰는 것이 훨씬 빠르고 간단하다. HashMap을 쓰면 List로 변환하고 정렬하는 과정(O(K log K), K=알파벳 개수)이 추가로 필요하지만, 배열을 쓰면 이 과정이 모두 생략된다.
⏰ 시간복잡도
N은 입력받은 문자열의 길이, K는 사용된 알파벳의 고유 개수(최대 26)
O(N)
- List 변환 및 정렬: O(K log K)
HashMap을 List로 변환하고(O(K)), 정렬(O(K log K))합니다. K는 최대 26이므로 사실상 O(1) (상수 시간)입니다. - str 만들기 (병목 지점 1): O(N²)
for문 안에서str += tmp;연산을 사용했습니다.
String 덧셈은 str의 길이가 1, 2, 3... N/2가 될 때까지 매번 새로운 문자열을 생성하고 복사하는 O(M) (M=현재 문자열 길이) 연산입니다.str에 추가되는 문자의 총개수는 N/2개입니다. ( K=N/2 라고 할게요)
1번째 문자 추가 (str 길이 0): 비용 ≈1
2번째 문자 추가 (str 길이 1): "A"를 새 가방에 복사. 비용 ≈1
3번째 문자 추가 (str 길이 2): "AA"를 새 가방에 복사. 비용 ≈2
4번째 문자 추가 (str 길이 3): "AAA"를 새 가방에 복사. 비용 ≈3
...
K번째 문자 추가 (str 길이 K−1): ... 비용 ≈K−1
이 str += tmp; 작업의 총비용은 이 모든 과정을 더한 것입니다.
총비용 ≈1+1+2+3+⋯+(K−1) (여기서 K=N/2)
총연산 횟수는 1 + 2 + 3 + ... + (N/2)가 되어(n(n+1)/2), O(N²)이 됩니다.
- str2 만들기 (병목 지점 2): O(N²)
str을 만들 때와 똑같은 이유로 str2 += ... 부분도 O(N²)입니다.
str += tmp; 부분 시간복잡도 잘 이해 안가서 다시 정리
for (Map.Entry<Character, Integer> entry : list){
Character tmp = entry.getKey();
if (entry.getValue() == 0){
continue;
}
for (int i = 0; i < entry.getValue() / 2; i++){
str += tmp;
}
}여기 부분이 O(N^2)이 나오는게 잘 이해가 안가서 다시 정리한다.
겉의 for문은 최대 26번만 돌기 때문에 상수 시간(O(1))으로 취급하며, 시간 복잡도에 영향을 주지 않음 은 맞다.
진짜 원인은 "안의 for문" 자체가 아니라, 그 안에서 실행되는 str += tmp; 작업의 누적 비용 때문
작업 횟수 vs 작업 비용
두 for문의 역할을 분리해서 생각해 보자
- 두 for문의 역할 (작업 횟수):
두 for문(겉+안)을 모두 합쳐서str += tmp;코드를 총 몇 번 호출하나요?
→ (A 개수/2) + (B 개수/2) + ... = (전체 개수/2) = 총 번 호출합니다. str += tmp;의 역할 (작업 비용):str += tmp;작업은 한 번 호출될 때마다 O(1)(일정한 시간)이 걸리지 않습니다.str의 길이가 길어질수록 (짐이 많아질수록)str += tmp;연산(새 가방에 짐 옮기기)은 점점 더 오래 걸립니다.- 이 작업은 평균적으로 의 비용이 든다고 볼 수 있습니다.
결론
- 겉의 for문: O(1) (영향 없음)
- 안의 for문: (겉의 for문과 합쳐서)
str += tmp;를 총 번 호출하는 역할을 합니다. str += tmp;: 이 작업의 평균 비용이 O(N)입니다.
따라서 이 코드의 총 시간 복잡도는 다음과 같이 계산됩니다.
총 시간 복잡도 = (총 작업 횟수) × (평균 작업 비용)≈O(N)×O(N)=O(N2)
즉, 안쪽 for문 하나가 이라서가 아니라, 번 실행되는 작업의 비용이 까지 비싸지기 때문에 둘을 곱해서 이 되는 것입니다.
풀이2
int형 배열을 선언하여 거기에 알파벳 별 갯수를 담았다.
sb에 앞부분 문자열을 담고, 그걸 reverse() 하여 뒷부분 문자열을 만들었다.
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String input = br.readLine();
// 알파벳 개수를 저장할 배열 (A-Z -> 0-25)
int[] alphaCount = new int[26];
for (char c: input.toCharArray()){
alphaCount[c - 'A']++;
}
//홀수개인 알파벳 갯수 세기
int count = 0;
char middle = 0;
for (int i = 0; i < alphaCount.length; i++){
if (alphaCount[i] % 2 != 0){
count++;
middle = (char) (i + 'A'); // 가운데 값 확보
alphaCount[i]--; //갯수 하나 빼서 짝수로 만듦
if (count > 1){
sb.append("I'm Sorry Hansoo");
System.out.print(sb);
return;
}
}
}
// 팰린드롬의 앞부분 만들기 (A부터 Z 순서대로)
for (int i = 0; i < alphaCount.length; i++){
if (alphaCount[i] == 0){
continue;
}
// 해당 알파벳 개수의 절반만큼만 sb에 추가
for (int j = 0; j < alphaCount[i] / 2; j++){
sb.append((char) (i + 'A'));
}
}
String firstHalf = sb.toString();
String lastHalf = sb.reverse().toString();
if (middle != 0){
System.out.print(firstHalf + middle + lastHalf);
} else{
System.out.print(firstHalf + lastHalf);
}
}
}
그런데 왜 풀이2가 더 메모리와 시간이 더 오래걸렸지?
N이 아주 작을 때는, HashMap을 만들고, List로 변환하고, 정렬하는 등의 오버헤드와 int[] 배열을 2번 순회하는 오버헤드가 거의 차이가 없게 된다. 4ms 차이는 채점할 때마다 뒤바뀔 수 있는 사실상 의미 없는 오차.
만약 문제의 N 제약이 50이 아니라 500,000이었다면, HashMap 풀이는
str += tmp;때문에 100% 시간 초과가 났을 것이고,배열 + StringBuilder풀이는 O(N) 이라 1초 안에 넉넉히 통과했을 것이다.
따라서 배열을 사용한 풀이는 더 좋은 확장성을 가진, 이론적으로 더 올바른 방식이다!
⏰ 시간복잡도
O(N)
TIL💡
StringBuilder의 reverse() 활용
현재 나는 String을 뒤집을때 그냥 정석대로 뒤집었는데 StringBuilder의 메서드를 활용하면 더 쉽게 뒤집을 수 있다
주요 메서드]
.setLength(0): 비워주기.append( ): StringBuffer 인스턴스가 저장하고 있는 문자열 뒤에 덧붙인다.delete(int start, int end): 시작위치(start) 부터 끝 위치(end) 사이에 있는 문자를 제거한다 (단, 끝 위치의 문자는 제외!).deleteCharAt(int index): 지정된 위치(index)의 문자를 제거한다..insert(int pos, String str): 두번째 매개변수로 받은 값을 문자열로 변환하여 지정된 위치(pos)에 추가한다. (pos는 0부터 시작).replace(int start, int end, string str): 지정된 범위(start ~ end)의 문자들을 주어진 문자열로 바꾼다. (end 위치의 문자는 범위에 포함 되지않는다!).reverse( ): 문자열의 순서를 거꾸로 나열한다..setCharAt(int index, char ch): 지정된 위치의 문자를 주어진 문자(ch)로 바꾼다.toString( ): StringBuffer 인스턴스의 문자열을 String으로 반환한다..subString(int start)or.subString(int start, int end)
: 지정된 범위 내의 문자열을 String으로 뽑아서 반환한다.
