[백준] S1 9519 졸려 (java)

https://www.acmicpc.net/problem/9519

9519번: 졸려

 

풀이

 

1) 단어가 홀수일 경우와 짝수일 경우로 나누어 단어를 섞는다. 섞을때 마다 list에 저장한다.

2) 섞은 결과가 map에 이미 존재할 경우 루프를 돈다는 의미이다.

3) 루프를 발견하면 해당 map의 value 가 주기가 된다.

4) list.get(N을 주기로 나눈 나머지) 가 정답이 된다.

 

주의사항

 

1) String 을 더하는 방식으로 하면 오래 걸린다. StringBuilder를 사용하자.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BJ_S1_9519_졸려 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static int X;
	static String word;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		X = Integer.parseInt(input.readLine());
		int temp = X;
		word = input.readLine();
		int N = word.length();
		String tempString = word;
		StringBuilder head = new StringBuilder();
		StringBuilder tail = new StringBuilder();
		Map<String, Integer> map = new HashMap<>();
		List<String> list = new ArrayList<>();
		list.add(word);
		int cnt = 0;
		while(temp>0) {
			head.setLength(0);
			tail.setLength(0);
			if(N%2 == 0) { // 짝
				for(int i=N-1; i>=0; i-=2) {
					tail.append(tempString.charAt(i));
				}
				for(int i=0; i<N; i+=2) {
					head.append(tempString.charAt(i));
				}
			}else { // 홀
				for(int i=N-2; i>=0; i-=2) {
					tail.append(tempString.charAt(i));
				}
				for(int i=0; i<N; i+=2) {
					head.append(tempString.charAt(i));
				}
			}
			head.append(tail);
			tempString = head.toString();
			list.add(tempString);
			if(map.get(tempString) == null) {
				map.put(tempString, cnt++);
			}else {
				break;
			}
			temp--;
		}
		if(temp>0) { // 주기를 발견할 경우
			temp = X % cnt;
			System.out.println(list.get(temp));
		}else {
			System.out.println(tempString);
		}
	}

	static String src =

			"11\r\n" + 
			"srama";
}

 

 

후기

 

조금 머리를 쓰게한 문제이다. String을 합치는 것, 루프를 어떻게 찾을지, 루프를 찾을경우 정답을 어떻게 얻을지 하나하나가 의미있는 좋은 문제였다.