Golang Algorithm - 백준 1015번 수열 정렬 알고리즘

백준에 있는 1015번 문제를 go언어로 풀어봤다. 문제와 입출력 예시는 백준에서 가져왔다.
예제 입출력은 통과했으나 아직 제출에서 통과하지 않았다.(원인은 파악 중이다..) 
go 공부할 때 참고하는 정도로만 보면 될 것 같다. 

 

 

문제

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

입력

첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.

 

예제 입력 1 

3
2 3 1

예제 출력 1 

1 2 0

예제 입력 2 

4
2 1 3 1

예제 출력 2 

2 0 3 1

예제 입력 3 

8
4 1 6 1 3 6 1 4

예제 출력 3 

4 0 6 1 3 7 2 5

 

go 소스코드

package main

import (
	"fmt"
	"sort"
)


func main(){

	// 수도코드
	// 첫 번째 줄 입력 받아서 n에 저장
	// 공백 기준으로 배열에 전부 삽입
	// 이후 배열을 복사하고 
	// 복사한 배열에서 정렬한 뒤 딕셔너리 같이 키와 밸류를 만듬
	// 이후 복사한 배열의 딕셔너리의 키를 출력함 

	var n int 
	fmt.Scanln(&n)
	
	//a를 배열로 초기화 후 입력받는 변수를 a에 담기 
	a := make([]int, n)
	for i := 0; i < n; i++{
		fmt.Scan(&a[i])
	}

	//p를 초기화 하고 p의 배열을 만들되 n의 숫자만큼 순차적으로 만듬 
	p := make([]int, n)
	for i := 0; i < n; i++{
		p[i]=i 
	}
	//fmt.Println("before a",a)
	//fmt.Println("before p",p)
	//2, 3, 1을 밸류로하고 0, 1, 2를 키로 한 뒤 
	//정렬했을 때 인덱스는 2, 0, 1이된다. 
	//다음은 a정렬을 기준으로 p로 오름차순 정렬했을 때 p의 키값? 인덱스로 정렬된 값이다. 
	sort.Slice(p, func(i, j int) bool { return a[p[i]] < a[p[j]]})
	//2, 3, 1 >>>>  2:0 / 3:1 / 1:2
	// 2 > 0 > 1  위의 밸류값으로 다시 인덱스를 잡으면 다음과 같음 
	

	//fmt.Println("after a",a)
	//fmt.Println("after p",p)

	//이후 p의 인덱스에 있는대로 b배열을 만들면 원래 배열의 인덱스별로 오름차순이 가능함
	b := make([]int, n)
	for i := 0; i < n; i++{
		b[p[i]] = i 
		//b[p[0]]=0 , b[2] = 0 
		//b[p[1]]=1 , b[0] = 1 
		//b[p[2]]=2 , b[1] = 2 
	}

	//다음과 같이 1 2 0 으로 출력이 가능함
	for i := 0; i < n; i++{
		fmt.Print(b[i], " ")
	}

	
}