2021/07/28 2

[PS/Golang] 회문 순열

Prologue 회문 순열 문제를 너무 바보같이 푼게 화가 나서 방금 올렸던 Python 이후에 Go로도 짜보았습니다.. ㅋㅋㅋㅋ 아으아!!!!!!! 이렇게 구현하면, 사실상 O(n) 만에 해결 가능합니다. 코드 package main import ( "bufio" "fmt" "os" "strings" ) var ( w = bufio.NewWriter(os.Stdout) sc = bufio.NewScanner(os.Stdin) ) func main() { defer w.Flush() words := scanWords() fmt.Fprintln(w, solution(words)) } func solution(words string) bool { wordsMap := make(map[rune]int) for..

PS 2021.07.28 (2)

[PS/Python] 회문 순열

Prologue 아... 회문 순열 문제를 풀고나서 영 찜찜해서 다시 생각해보니 딕셔너리만 쓰면 되는 문제였습니다. 바보같이 Permutation쓰고 is_palindrome 구현하고.. ㅋㅋㅋㅋㅋ 무슨 뻘짓을 한 거지! 딕셔너리만 쓰면 정말 쉬운 문제였는데, O(n)으로 끝날 걸, 거의 O(n^2 ~ n!) 수준으로 풀어놨으니..... 아이디어는 매우 단순합니다. 회문을 이루려면, 회문의 길이가 짝수인 경우엔, 모든 알파벳이 짝수개가 있으면 되고, 길이가 홀수라면, 하나 빼고 모두 짝수이면 됩니다. 따라서 홀수인 알파벳이 하나만 존재하는지 확인해주면 됩니다. 이걸 어떻게 그렇게 풀 수가 있을까요... ㅋㅋㅋㅋㅋㅋㅋㅋ 아무리 생각해도 웃음벨이 될 것 같습니다... ㅋㅋㅋ.. 코드 def solution(..

PS 2021.07.28
반응형