BOJ - 20442 ㅋㅋ루ㅋㅋ

leehyunjon·2022년 5월 26일

Algorithm

목록 보기

45/162

20442 ㅋㅋ루ㅋㅋ : https://www.acmicpc.net/problem/20442

Problem

Solve

알고리즘은 국어문제라는 것을 다시 한번 느끼게 해준 문제.
'ㅋㅋ루ㅋㅋ'문자열을 타겟 문자열이라고 하자.
처음에는 타겟 문자열+타겟 문자열 = 타겟 문자열이 된다라는 고정관념이 잡혀 문제에 접근 조차 하지 못했었다. 친구 덕분에 부분 수열 중 가장 긴 타겟 문자열 길이를 출력하는 것의 의도를 파악할수 있었다.

예를 들어 KRKKRK은 타겟+타겟으로 이루어져있으니까 KRKKRK로 6이어야하지 않은가로 생각했었다.
하지만 타겟+타겟은 위 타겟 문자열이어야하는 조건을 만족하지 못한다. 오로지 R로만 이루어진 문자열 혹은 R로만 이루어진 문자열 양 옆에 K가 있어야 타겟 문자열인것이다.

문자열의 최대 길이가 3000000이므로 NlogN 밑으로 해결해야하기 때문에 투포인터를 사용했다.

첫번째로 알아야 할것은 각 R의 왼쪽과 오른쪽에 존재하는 K의 개수를 구해야하는 것이다.
부분 수열 중 가장 긴 타겟 문자열이라고 했기 때문에 K중간에 R이 있어도 무시하고 K의 개수를 저장한다.

두번째는 투포인터를 통해 두개 포인터(start, end)의 범위내에서 R의 개수를 찾고 start의 왼쪽 k개수와 end의 오른쪽 k개수를 비교해 공통으로 가질수 있는 개수를 R개수와 합해주면 타겟 문자열의 길이가 나오게 된다.

KRKKRK 문자열을 예시로 들어보자.

문자열에는 총 2개의 R이 존재하고 첫번째 R의 왼쪽k의 개수는 1개 오른쪽k의 개수는 3개이다.
두번째 R의 왼쪽은 3개 오른쪽은 1개의 k를 가지고 있다.
투포인터를 통해 start=0, end=1로 시작하여 end-start+1로 start와 end범위의 R개수를 구할수 있다.
그리고 lk[start]=1(왼쪽 k개수), rk[end]=1(오른쪽 k개수)를 통해 공통으로 가질수 있는 k는 1개 이므로 총 4의 타겟 문자열 길이를 가질 수 있다.

포인터를 이동해서 두번째 R이 가질수 있는 타겟 문자열 길이는 3이다.

Code

public class ㅋㅋ루ㅋㅋ {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String sequence = br.readLine();

		//각 R의 왼쪽 k 개수
		List<Integer> lk = new ArrayList<>();
        //각 R의 오른쪽 k 개수
		List<Integer> rk = new ArrayList<>();

		int kCount = 0;
		for (int i = 0; i < sequence.length(); i++) {
        	//R을 발견할때까지 k개수를 구하고 R을 발견했을때 왼쪽 k개수 저장
			if(sequence.charAt(i)=='K') kCount++;
			else lk.add(kCount);
		}

		kCount=0;
		for(int i=sequence.length()-1;i>=0;i--){
        	//R을 발견할때까지 k개수를 구하고 R을 발견했을때 오른쪽 k개수 저장
			if(sequence.charAt(i)=='K') kCount++;
			else rk.add(kCount);
		}

		//R의 index를 맞춰주기 위해 오른쪽 k개수 역전
		rk.sort(Comparator.reverseOrder());

		int left=0;
		int right=rk.size()-1;
		int answer = 0;
		while(left<=right){
        	//해당 범위의 R개수 : right-left+1
            //양 옆의 k개수 : Math.min(lk.get(left),rk.get(right))
			answer = Math.max(answer, (right-left+1)+2*(Math.min(lk.get(left),rk.get(right))));

			//왼쪽과 오른쪽 k개수가 같다면 어느쪽으로 움직이든 상관없다.
			if(lk.get(left)<=rk.get(right)){
				left++;
			}else{
				right--;
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();

	}
}