Skip to main content

[Java] 12973 짝지어 제거하기

1. 문제

짝지어 제거하기

2. 접근방법

  1. 해시맵으로 알파벳별 빈도수 저장
  2. 모든 빈도수가 짝수라면 1, 아니라면 0 리턴

3. 오답코드

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = -1;
        // 해시맵으로 알파벳별 빈도수 저장하고
        // 모든 빈도수가 짝수라면 1 아니면 0 리턴
        
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        // 모든 빈도수가 짝수 ?
        for (int freq : map.values()) {
            if (freq % 2 != 0) {
                return 0; // 홀수가 하나라도 있으면 0
            } 
        }
        
        return 1; // 모두 짝수라면 1
    }
}

image.png

메서드

map.put(c, map.getOrDefault(c, 0) + 1);
  • map.getOrDefault(c, 0)
    → 맵에 문자 c가 있으면 그 값(빈도수)를 가져오고, 없으면 기본값 0을 가져온다.
  • +1
    → 지금 등장한 문자니까 기존 값에 1을 더한다
  • map.put(c, ...)
    → 계산된 값을 다시 c 키에 저장한다.
if (map.containsKey(c)) {
    map.put(c, map.get(c) + 1);
} else {
    map.put(c, 1);
}

이것을 한 줄로 줄여쓴 것이다.

틀린 이유

  • 개수가 짝수인데 짝지어서 제거 안 되는 반례 생가해보기
  • 예제에 cdcd처럼 문자열이 연속되지 않으면 제거가 안 되는 구나...
  • 그럼 문자열이 연속인지 판단하는 로직을 추가해야겠다 아니면 스택써야겠다

4. 정답코드

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) { // 스택이 비어있지 않고
                stack.pop(); // 같은 문자가 연속 2번 나오면 제거
            } else {
                stack.push(c);
            }
        }
        
        // 스택 비어 있으면 짝수쌍임
        return stack.isEmpty() ? 1 : 0;
        
    }
}
  1. s를 char 타입으로 쪼개서 배열에 집어 넣기
  2. 배열을 순회하며 스택이 비어있지 않고, 스택 맨 위에 있는 문자가 현재 문자와 같다면 스택 맨 위에 있는 문자 꺼내기
  3. 그렇지 않으면 해당 문자 스택에 추가하기
  4. 스택이 비어 있으면 모든 문자가 제거된 것이고, 스택에 남이있으면 그렇지 않은 것




Back to top