[하계 코딩테스트 특강] 2022.07.05 문자열 조작

# String 클래스 메서드

 

# HashMap 메서드

 

1) 문자열 압축

- java

import java.io.*;
import java.util.*;

public class Main {

    public String solution(String s){
        String ans = "";
        s += " ";

        int cnt = 1;
        for(int i=0; i < s.length()-1; i++){
            if(s.charAt(i) == s.charAt(i+1)){
                cnt++;
            }
            else {
                ans += s.charAt(i);
                if(cnt > 1) ans += String.valueOf(cnt);
                cnt = 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        System.out.println(T.solution("KKHSSSSSSSEEE"));
    }
}

- python

def solution(s):
    answer=""
    cnt=1
    s=s+" "
    n=len(s)
    for i in range(n-1):
        if s[i]==s[i+1]:
            cnt+=1
        else:
            answer+=s[i]
            if cnt>1:
                answer+=str(cnt)
            cnt=1
    return answer

print(solution("KKHSSSSSSSEEE"))

---

2) 회문 문자열

- java

import java.io.*;
import java.util.*;

public class Main {
	// 1
    public String solution(String s){
        String ans = "NO";
        String tmp = new StringBuilder(s).reverse().toString();
        if(tmp.equalsIgnoreCase(s)) ans = "YES"; // 대소문자 무시하고 비교
        return ans;
    }
	
    // 2
    public String solution(String s){
        String ans = "NO";
     // s = s.toUpperCase();
        int left = 0;
        int right = s.length()-1;
        while (left < right){
            char c1 = Character.toLowerCase(s.charAt(left)); // char 대문자 -> 소문자
            char c2 = Character.toLowerCase(s.charAt(right));
            if (c1 != c2) return ans;
            else {
                left++;
                right--;
            }
        }
        ans = "YES";
        return ans;
    }
    
    public static void main(String[] args) throws IOException {
        Main T = new Main();
        System.out.println(T.solution("gooG"));
    }
}

- python

def solution(s):
    answer="YES"
    s=s.upper()
    if s!=s[::-1]:
        return "NO"
    return answer

print(solution("sttS"))
print(solution("sktS"))


def solution(s):
    answer="YES"
    s=s.upper()
    lt=0
    rt=len(s)-1
    while(lt<rt):
        if s[lt]!=s[rt]:
            return "NO"
        else:
            lt+=1
            rt-=1
    return answer

print(solution("sttS"))
print(solution("sktS"))

---

3) 특정 문자 뒤집기

- java

import java.io.*;
import java.util.*;
import static java.lang.Character.isAlphabetic;

public class Main {

    public String solution(String s){
        String ans = "";
        char[] str = s.toCharArray();
        int left = 0;
        int right = s.length()-1;

        while (left < right){
            boolean b1 = isAlphabetic(str[left]);
            boolean b2 = isAlphabetic(str[right]);
            if(b1 && b2){
                char tmp = str[left];
                str[left] = str[right];
                str[right] = tmp;
                left++;
                right--;
            }
            else if(!b1) left++;
            else if(!b2) right--;
        }
        ans = String.valueOf(str);
        return ans;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        System.out.println(T.solution("a#b!GE*T@S"));
    }
}

- python

def solution(s):
    answer=list(s)
    lt=0
    rt=len(s)-1
    while(lt<rt):
        if not answer[lt].isalpha():
            lt+=1
        elif not answer[rt].isalpha():
            rt-=1
        else:
            tmp=answer[lt]
            answer[lt]=answer[rt]
            answer[rt]=tmp
            lt+=1
            rt-=1
    return "".join(answer)

print(solution("a#b!GE*T@S"))

---

4) 회문문자열 2

- java 1

import java.io.*;
import java.util.*;

public class Main {

    public String solution(String s){
        String ans = "NO";
        s = s.toLowerCase();

        int left = 0;
        int right = s.length()-1;
        int cnt = 0;
        while (left < right){
            if (s.charAt(left) != s.charAt(right)) {
                if(s.charAt(left+1) == s.charAt(right)) left++;
                else if(s.charAt(left) == s.charAt(right-1)) right--;
                else return ans;

                if(cnt == 1) return ans;
                else cnt++;
            }
            else {
                left++;
                right--;
            }
        }
        ans = "YES";
        return ans;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        System.out.println(T.solution("abcacbakcba"));
    }
}

- java 2

import java.util.*;
class Main {
	public Boolean isPalindrome(String s){
		Boolean answer=true;
		int rt=s.length()-1;
		int lt=0;
		while(lt<rt){
			if(s.charAt(lt)!=s.charAt(rt)) return false;
			else{
				lt++;
				rt--;
			}
		}
		return answer;
	}
	public String solution(String s){
		String answer="YES";
		int rt=s.length()-1;
		int lt=0;
		while(lt<rt){
			if(s.charAt(lt)!=s.charAt(rt)){
				String s1=s.substring(lt, rt);
				String s2=s.substring(lt+1, rt+1);
				if(!isPalindrome(s1) && !isPalindrome(s2)) return "NO"; 
                else break;
			}
			lt++;
			rt--;
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		System.out.println(T.solution("abcabbakcba"));
		System.out.println(T.solution("abcacbakcba"));
	}
}

- python

def solution(s):
    answer="YES"
    lt=0
    rt=len(s)-1
    while(lt<rt):
        if s[lt]!=s[rt]:
            sub1=s[lt:rt]
            sub2=s[lt+1:rt+1]
            if sub1!=sub1[::-1] and sub2!=sub2[::-1]:
                answer="NO"
            break
        else:
            lt+=1
            rt-=1
    return answer
       
    
print(solution("abcacbakcba"))
print(solution("abcabbakcba"))

---

5) 학급 회장

- java

import java.io.*;
import java.util.*;

public class Main {

    public char solution(String s){
        char ans = ' ';
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();

        for(char c : s.toCharArray()){  // s 를 문자 배열형으로
            hm.put(c, hm.getOrDefault(c, 0) + 1); // 해당 문자가 처음이면 0으로 default

        }
        
        int max = Integer.MIN_VALUE;
        for(char key : hm.keySet()){  // hashmap 의 key 들의 모임
            if (max < hm.get(key)) {
                max = hm.get(key);
                ans = key;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        System.out.println(T.solution("BACBACCACCBDEDE"));
    }
}

- python

from collections import Counter
def solution(s):
    answer=""
    sH={}
    sH=Counter(s)
    largest=0
    for [key, val] in sH.items():
        if val>largest:
            largest=val
            answer=key
    
    return answer

print(solution("BACBACCACCBDEDE"))



import collections
def solution(s):
    answer=""
    sH=collections.defaultdict(int)
    for x in s:
        sH[x]+=1
    largest=0
    for key in sH:
        if sH[key]>largest:
            largest=sH[key]
            answer=key
    
    return answer


print(solution("BACBACCACCBDEDE"))

---

6) 한 번 사용한 최초 문자

- java

import java.io.*;
import java.util.*;

public class Main {

    public int solution(String s){
        int ans = -1;
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();

        for(char c : s.toCharArray())  // s 를 문자 배열형으로
            hm.put(c, hm.getOrDefault(c, 0) + 1); // 해당 문자가 처음이면 0으로 default

        for(int i=0; i < s.length(); i++)
            if(hm.get(s.charAt(i)) == 1) return i+1;

        return ans;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        System.out.println(T.solution("aabb"));
    }
}

- python

import collections
def solution(s):
    sH=collections.Counter(s)
    for index, val in enumerate(s):
        if sH[val]==1:
            return index+1
    return -1


print(solution("softbananas"))#2
print(solution("stringshowtime"))#3
print(solution("showshowmine"))#9
print(solution("statitsics"))#3
print(solution("aabb"))#8

---

7) 같은 빈도수 만들기

- java

import java.io.*;
import java.util.*;

public class Main {

    public ArrayList solution(String s){
        ArrayList<Integer> ans = new ArrayList<>();

        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();

        for(char c : s.toCharArray())  // s 를 문자 배열형으로
            hm.put(c, hm.getOrDefault(c, 0) + 1); // 해당 문자가 처음이면 0으로 default

        int max = Integer.MIN_VALUE;
        for(char key : hm.keySet())   // hashmap 의 key 들의 모임
            if (max < hm.get(key)) max = hm.get(key);

        String tmp = "abc";
        for(char x : tmp.toCharArray())
            ans.add(max - hm.getOrDefault(x, 0)); // aabb 시, c 가 없기 때문에 getOrDefault

        return ans;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        System.out.println(T.solution("aabb"));
    }
}

- python

import collections
def solution(s):
    answer=[]
    sH=collections.Counter(s)
    tmp="abc"
    maxN=float("-inf")
    for x in tmp:
        if sH[x]>maxN:
            maxN=sH[x]
    for x in tmp:
        answer.append(maxN-sH[x])
    return answer


print(solution("aaabc"))#[0, 2, 2]
print(solution("bbcaabccca"))#[1, 1, 0]
print(solution("caaabccbbccccccaaaaa"))#[1, 6, 0]
print(solution("bbbbbbbbbbbb"))#[12, 0, 12]
print(solution("abc"))#[0, 0, 0]

---

8) 팰린드롬 길이

- java

import java.io.*;
import java.util.*;

public class Main {

    public int solution(String s){
        int ans = 0;
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();

        for(char c : s.toCharArray())  // s 를 문자 배열형으로
            hm.put(c, hm.getOrDefault(c, 0) + 1); // 해당 문자가 처음이면 0으로 default

        int cnt = 0;
        for(char key : hm.keySet()){
            if(hm.get(key) % 2 == 0) ans += hm.get(key);
            else {
                ans += (hm.get(key)-1);
                cnt++;
            }
        }
        return cnt > 0 ? ans + 1 : ans;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        System.out.println(T.solution("aaaabbbbcccc"));
    }
}

- python

function solution(s){  
    let sH = new Map();
    for(let x of s){
        sH.set(x, (sH.get(x) || 0)+1);
    }
    let cnt=0;
    for(let val of sH.values()){
        if(val%2===1) cnt++;
    }
    return cnt>0 ? (s.length+1)-cnt : s.length;
}
console.log(solution("abccccdd"));
console.log(solution("ab"));
console.log(solution("bb"));
console.log(solution("ccc"));
console.log(solution("abcde"));

---

9) 음성 인식

i) abcabcdefabc 에서, abcabcdefbac 일 경우, a,b,c 가 각각의 패턴이 됨 (패턴은 길이가 1이상, 여러개 가능)

ii) ABCabcA 에서, a=3, b=2, b=2 이므로 max인 a 가 말버릇 패턴 -> BCbc 가 답이 됨

 

- java

import java.io.*;
import java.util.*;

public class Main {

    public String solution(String s){
        String ans = "";
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
        String tmp = s.toLowerCase();
        for(char x : tmp.toCharArray())
            hm.put(x, hm.getOrDefault(x, 0) + 1);
        int max = 0;
        for(char key : hm.keySet())
            if(hm.get(key) > max) max = hm.get(key);

        for(int i = 0; i < s.length(); i++)
            if(hm.get(tmp.charAt(i)) < max) ans += s.charAt(i);
			// 원본의 s 로 count 해야 대소문자 구분해서 출력됨
        return ans;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        System.out.println(T.solution("abxdeydeabz"));
    }
}

- python

import collections
def solution(call):
    answer=""
    tmp=call.lower()
    sH=collections.defaultdict(int)
    maxValue=-1
    for x in tmp:
        sH[x]+=1
        if sH[x]>maxValue:
            maxValue=sH[x]
    for i, x in enumerate(tmp):
        if maxValue>sH[x]:
            answer+=call[i]
    return answer

print(solution("Abcabcdefabc"))
print(solution("abxdeydeabz"))
print(solution("abcabca"))
print(solution("ABCabcA"))

---

10) 공통 문자 찾기 (**숙제)

- java

import java.io.*;
import java.util.*;

public class Main {
    public ArrayList<Character> solution(String[] words){
        ArrayList<Character> answer = new ArrayList<>();
        HashMap<Character, Integer> map=new HashMap<>();
        for(char x : words[0].toCharArray()){
            map.put(x, map.getOrDefault(x, 0)+1);
        }

        for(int i=1; i<words.length; i++){
            HashMap<Character, Integer> tmp=new HashMap<>();
            for(char x : words[i].toCharArray()){
                if(map.getOrDefault(x, 0)>0){
                    map.put(x, map.get(x)-1);
                    tmp.put(x, tmp.getOrDefault(x, 0)+1);
                }
            }
            map=new HashMap<Character, Integer>(tmp);
        }
        for(char key : map.keySet()){
            for(int i=0; i<map.get(key); i++){
                answer.add(key);
            }

        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        String[] tmp = new String[]{"steasue", "sasseysu", "kseseas"};
        System.out.println(T.solution(tmp));
        String[] tmp1 = new String[]{"longlong", "longtong", "longbig"};
        System.out.println(T.solution(tmp1));

    }
}

- python

import collections
def solution(words):
    answer=[]
    words.sort(key=lambda x : len(x))
    sH=collections.defaultdict(int)
    for x in words[0]:
        sH[x]+=1
    m=len(words)
    for i in range(1, m):
        tmp=collections.defaultdict(int)
        for x in words[i]:
            if sH[x]>0:
                sH[x]-=1
                tmp[x]+=1
        sH=tmp
    for [key, val] in sH.items():
        for _ in range(val):
            answer.append(key)
        
    return answer


print(solution(["a", "aaa", "aaaaa"])) #['a']
print(solution(["longlong", "longtong", "longbig"])) #['l', 'o', 'n', 'g', 'g']
print(solution(["abcde", "edcba", "cdeba", "debac", "acbed"])) #['a', 'c', 'b', 'e', 'd']
print(solution(["cool", "rock", "cook"])) #['c', 'o']
print(solution(["aabbss", "bbbss", "csc", "asb"])) #['s']

---

11) 가장 가까운 시간

- java

import java.io.*;
import java.util.*;

public class Main {
    public int getTime(String time){
        String[] tmp = time.split(":"); // 03, 07
        int h = Integer.parseInt(tmp[0]); // 3
        int m = Integer.parseInt(tmp[1]);  // 7

        return ((h * 60) + m);
    }

    public int solution(String[] s){
        ArrayList<Integer> tmp = new ArrayList<>();

        for(int i=0; i < s.length; i++) tmp.add(getTime(s[i]));
        Collections.sort(tmp);
        int ans = Integer.MAX_VALUE;
        for(int i=1; i < tmp.size(); i++){
            int x = tmp.get(i)-tmp.get(i-1);
            ans = ans > x ? x : ans;
        }
        ans = Math.min(ans, 60*24+tmp.get(0) - tmp.get(tmp.size()-1));
        return ans;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        String[] tmp = new String[]{"00:12", "00:00", "01:05", "00:57"};
        String[] tmp1 = new String[]{"00:00", "23:59", "23:57"};
        System.out.println(T.solution(tmp));
    }
}

- python

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
   
        times = [self.convert(time) for time in timePoints]
        
        times.sort()
        
        res = times[0] + 24*60 - times[-1]
        for i in range(1, len(times)):
            res = min(res, times[i] - times[i-1])
        return res
    
    def convert(self, time):
        hour, minutes = time.split(":")
        hour = int(hour)
        minutes = int(minutes)
        return hour*60 + minutes

---

12) 공부 시간

- java

import java.io.*;
import java.util.*;

public class Main {
    public int getTime(String time){
        String[] tmp = time.split(":"); // 03, 07
        int h = Integer.parseInt(tmp[0]); // 3
        int m = Integer.parseInt(tmp[1]);  // 7

        return ((h * 60) + m);
    }

    public String solution(String[] s){
        String ans = "";
        ArrayList<Integer> tmp = new ArrayList<>();

        for(int i=0; i < s.length; i++)
            tmp.add(getTime(s[i]));
        int sum = 0;
        for(int i=0; i < tmp.size(); i+=2){
            int time = tmp.get(i+1) - tmp.get(i);
            if (time >= 5 && time <= 105) sum += time;
            else if(time > 105) sum += 105;
        }
        int h = sum / 60;
        int m = sum % 60;

        if(h < 10) ans += "0";
        return ans + h + ":" + m;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        String[] tmp = new String[]{"08:30", "09:00", "14:00", "16:00", "16:01", "16:06", "16:07", "16:11"};
//        String[] tmp1 = new String[]{"00:00", "23:59", "23:57"};
        System.out.println(T.solution(tmp));
    }
}

---

2022. 07. 05

다음 시간 : 배열(array) 시뮬레이션

 

자료구조

정렬 & 그리디

시간복잡도 줄이기

트리, 그래프 탐색 (DFS, BFS)

DFS, BFS 활용

트리, 그래프 알고리즘