글 읽기 - [Java] 15% 시간초과입니다. 도움이 필요합니다.

(追記) (追記ここまで)

[Java] 15% 시간초과입니다. 도움이 필요합니다.

25614번 - 자리 바꾸기

dltkdcksqkqh 2년 전 0

안녕하세요!!

해당 문제를 여러 날 동안 풀고자 노력했던 사람입니다.

로직을 설명드리면 다음과 같습니다.

1. N 길이만큼 순회하며 cycle 생성

2. M을 해당 cycle의 길이로 나눠서 dp배열에 저장

3. cycle의 숫자를 돌면서 변화된 값을 ans배열에 저장

4. StringBuilder에 모아놓은 후 출력

큰 숫자인 M을 나눈 값을 저장해둔 점과 N만큼 순회하며 바로바로 값을 반환했다는 점에서 시간초과를 받지 않을 것이라 생각했습니다.

혹시 더 개선이 필요한 부분이 있을까요?

조언부탁드립니다.

감사합니다.

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
 static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 static StringTokenizer st;
 static StringBuilder sb;
 static int[] arr, dp, ans;
 static boolean[] visited;
 static ArrayList<Integer> cycle;
 public static void main(String[] args) throws IOException {
 st = new StringTokenizer(br.readLine());
 int N = Integer.parseInt(st.nextToken());
 BigInteger M = new BigInteger(st.nextToken());
 
 st = new StringTokenizer(br.readLine());
 arr = new int[N + 1];
 for (int i = 1; i < N + 1; i++) {
 arr[i] = Integer.parseInt(st.nextToken());
 }
 
 dp = new int[N + 1]; // M을 cycle의 길이만큼 나눴을 때 값을 저장해줄 배열
 ans = new int[N + 1];
 visited = new boolean[N + 1];
 cycle = new ArrayList<>(); // 해당 숫자의 cycle을 담을 배열
 sb = new StringBuilder();
 
 for (int i = 1; i < N + 1; i++) {
 if (visited[i]) { // cycle로 이미 찾았을 경우 sb에 저장
 sb.append(ans[i]).append(" ");
 continue;
 }
 else {
 // cycle 생성
 int start = arr[i];
 cycle = new ArrayList<>();
 while(!visited[start]) {
 visited[start] = true;
 cycle.add(start);
 start = arr[start];
 }
 }
 int size = cycle.size();
 // 해당 사이클 길이만큼 나눈 결과가 있었을 경우
 int rest = dp[size] > 0 ? dp[size] : M.remainder(new BigInteger(String.valueOf(size))).intValue();
 dp[size] = rest;
 // 사이클 내의 원소가 M만큼 이동했을 때 갖는 값 ans배열에 저장
 for (int j = 0; j < size; j++) {
 ans[cycle.get(j)] = cycle.get((j + rest) % size);
 }
 // 현재 사이클 시작점은 sb에 추가
 sb.append(ans[i]).append(" ");
 }
 // 출력
 System.out.println(sb);
 }
}

dltkdcksqkqh 2년 전 0

파이썬으로 동일하게 로직을 짰더니 통과했습니다...

자바로는 시간 초과가 나는 것 같네요

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

[Java] 15% 시간초과입니다. 도움이 필요합니다.

dltkdcksqkqh 2년 전 0

dltkdcksqkqh 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말